《面试1v1》Map-Toy模板网

这篇具有很好参考价值的文章主要介绍了《面试1v1》Map。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

我是 javapub，一名 Markdown 程序员从👨‍💻，八股文种子选手。

《面试1v1》连载中…

面试官：小伙子,又来挑战你了。听说你对Java集合中的Map也很在行?

候选人： 谢谢夸奖,Map这个接口的确非常重要且强大。但和List一样,它有许多实现类,而我对它们的理解还远未充分,只能算入门。我仍需不断学习与总结。

面试官：那好,简单介绍下Map这个接口及常用实现类。它在开发中有何作用?

候选人： Map接口表示一个键值对集合,它的主要作用是根据键快速获取值。常用实现类有:

HashMap:基于哈希表实现,支持快速查找、插入和删除,但迭代顺序不定。

HashMap<String, Integer> map = new HashMap<>();

LinkedHashMap:保留插入顺序,除了查找效率高于LinkedHashMap外,其他方面与HashMap相同。

LinkedHashMap<String, Integer> map = new LinkedHashMap<>();

TreeMap:基于红黑树实现,键有序,增删慢但查找快,特别适合排序需求。

TreeMap<String, Integer> map = new TreeMap<>();

Hashtable:和HashMap类似,但它是线程安全的,效率略低。

Hashtable<String, Integer> map = new Hashtable<>();

Map在日常开发中用途广泛,例如缓存、查询表等。我最常用的当属HashMap,由于其查询效率高且适用于大容量场景。但我对其扩容、碰撞处理等机制还需进一步理解。

面试官：不错,你对Map有比较扎实的认知基础。那么你对HashMap的源码熟悉吗?能否解析一下?

候选人： HashMap的源码实现较复杂,我这里仅解析其基本结构与重要流程。主要包括:

HashMap底层采用数组+链表实现,数组是主干,链表在碰撞场景下使用。
字段包括:数组table,容量capacity,加载因子loadFactor等。

// 默认初始容量16,必须是2的n次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   

// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认加载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

put方法将键值对添加到表中。先计算键的hash值得到数组下标,然后将新键值对添加到该位置或链表中。
如果键所在的链表过长或超过加载因子,则触发rehash,即扩容与重新哈希,容量加倍。

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 保存旧表
    Entry<K,V> old = table[bucketIndex];
    
    // 创建新键值对,next指向旧表
    Entry<K,V> newEntry = new Entry<>(hash, key, value, old);
    
    // 更新数组对应位置
    table[bucketIndex] = newEntry;
    
    // 如果旧表不为空且旧表的键与新键hash值相同,则发生哈希碰撞
    if (old != null && hash == old.hash && 
        (old.getKey() == key || old.getKey().equals(key))) 
        old = newEntry;
            
    if (size++ >= threshold) 
        resize(2 * table.length);   // 扩容
}