HashMap 源码面试相关

痛定思痛。 2023-02-10 05:27 27阅读 0赞

### 文章目录 ###

*   *   *  Q1. 默认初始化大小为什么是 16 而不是 8 或者 32 ？ 为什么不直接写 16 ，而是写 1<<<4 ？
         *  Q2. 默认加载因子为什么是 0.75 ？
         *  Q3. 为什么有最小树形化容量阈值 64？
         *  Q4. HashMap 的 table 的容量如何确定？loadFactor 是什么？该容量如何变化？这种变化会带来什么问题？
         *  Q5. 为什么会扩容 ？ 什么时候会扩容 ？ 怎么扩容 ？
         *  Q6. 默认初始化大小为什么定义为2的幂 ？
         *  Q7. 为何 hashCode 值进行右移运算/异或运算 ？
         *  Q8. HashMap 中 put 方法的过程 ？
         *  Q9. HashMap 和 HashTable 有什么区别 ？
         *  Q10. Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是线程安全，它与 HashTable 在线程同步上有什么不同？
         *  Q11. HashMap & ConcurrentHashMap 的区别 ？

### Q1. 默认初始化大小为什么是 16 而不是 8 或者 32 ？ 为什么不直接写 16 ，而是写 1<<<4 ？ ###

/**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

如果太小，4或者8，扩容比较频繁；如果太大，32或者64甚至太大，又占用内存空间

位运算更快，不需十进制和二进制相互转换

### Q2. 默认加载因子为什么是 0.75 ？ ###

/**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

加载因子表示哈希表的填满程度，跟扩容息息相关。为什么不是0.5或者1呢？

如果是0.5，就是说哈希表填到一半就开始扩容了，这样会导致扩容频繁，并且空间利用率比较低。 如果是1，就是说哈希表完全填满才开始扩容，这样虽然空间利用提高了，但是哈希冲突机会却大了。

作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了良好的权衡。负载因子数值越大，空间开销越低，但是会提高查找成本（体现在大多数的HashMap类的操作，包括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。

简言之， 负载因子0.75就是冲突的机会 与空间利用率权衡的最后体现，也是一个程序员实验的经验值。

### Q3. 为什么有最小树形化容量阈值 64？ ###

/**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

如果数组长度小于 64, 这个时候树形化，治标不治本，因为引起链表过长的根本原因是数组过短。

所以在JDK1.8源码中，执行树形化之前，会先检查数组长度，如果长度小于64，则对数组进行扩容，而不是进行树形化。

### Q4. HashMap 的 table 的容量如何确定？loadFactor 是什么？该容量如何变化？这种变化会带来什么问题？ ###

1.  table 数组大小是由 capacity 这个参数确定的，默认是16，也可以构造时传入，最大限制是1<<30；
2.  loadFactor 是装载因子，主要目的是用来确认table 数组是否需要动态扩展，默认值是0.75，比如table 数组大小为 16，装载因子为 0.75 时，threshold 就是12，当 table 的实际大小超过 12 时，table就需要动态扩容；
3.  扩容时，调用 resize 方法，将 table 长度变为原来的两倍（注意是 table 长度，而不是 threshold）
4.  如果数据很大的情况下，扩展时将会带来性能的损失，在性能要求很高的地方，这种损失很可能很致命。

### Q5. 为什么会扩容 ？ 什么时候会扩容 ？ 怎么扩容 ？ ###

why ?

当HashMap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

when ?

当hashmap中的元素个数超过数组大小 \* loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16 \* 0.75=12的时候，就把数组的大小扩展为2 \* 16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。

1.  元素达到阈值；
2.  HashMap 准备树形化但又发现数组太短。

what ?

创建一个新的数组，其容量为旧数组的两倍，并重新计算旧数组中结点的存储位置。结点在新数组中的位置只有两种，原下标位置或原下标+旧数组的大小。

### Q6. 默认初始化大小为什么定义为2的幂 ？ ###

数组下标索引的定位公式是：i = (n - 1)&hash

if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

（HashMap 中的 hash 算法）

核心概念： HashMap 是根据 Key 的 hash 值和数组的长度取模得到一个值，从而定位到桶的位置。  
取模可以改为 hashCode & (length - 1)

当初始化大小 n 是2的倍数时， (n - 1)&hash 等价于 n%hash：n - 1意味着比 n 最高位小的位都为1，而高的位都为0，因此通过与可以剔除位数比 n 最高位更高的部分，只保留比n最高位小的部分，也就是取余了。

HashMap 底层：数组+链表+红黑树

定位数组下标用的是与运算&，为什么不用取余呢？

位运算直接对内存数据进行操作，不需要转成十进制，因此位运算要比取模运算的效率更高，所以 HashMap 在计算元素要存放在数组中的 index 的时候，使用位运算代替了取模运算。之所以可以做等价代替，前提是要求 HashMap 的容量一定要是 2^n 。

因此，默认初始化大定义为2的幂，就是为了使用更高效的与运算。

### Q7. 为何 hashCode 值进行右移运算/异或运算 ？ ###

JDK8 中的 hash 算法：

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

首先是取 key 的 hashCode 算法，然后把它右移16位，然后取异或

int是4个字节，也就是32位，我们右移16位也即是把高位的数据右移到低位的16位，然后做异或，那就是把高位和低位的数据进行重合，同时保留了低位和高位的信息

举个例子:

首先，假设有一种情况，对象 A 的 hashCode 为 1000010001110001000001111000000，对象 B 的 hashCode 为 0111011100111000101000010100000。

如果数组长度是16，也就是 15 与运算这两个数（前面说的hashCode & （length - 1））， 你会发现结果都是0。这样的散列结果太让人失望了。很明显不是一个好的散列算法。

但是如果我们将 hashCode 值右移 16 位，也就是取 int 类型的一半，刚好将该二进制数对半切开。并且使用位异或运算（如果两个数对应的位置相反，则结果为1，反之为0），这样的话，就能避免我们上面的情况的发生。简而言之就是尽量打乱hashCode的低16位，因为真正参与运算的还是低16位。

不知道这种解释是否是简单明了，经过自己的思考和分析后 也明白了 这段代码设计的初衷，也会感叹设计者的精妙。

### Q8. HashMap 中 put 方法的过程 ？ ###

“调用哈希函数获取Key对应的hash值，再计算其数组下标；

如果没有出现哈希冲突，则直接放入数组；如果出现哈希冲突，则以链表的方式放在链表后面；

如果链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表;

如果结点的key已经存在，则替换其value即可；

如果集合中的键值对大于12，调用resize方法进行数组扩容。”

### Q9. HashMap 和 HashTable 有什么区别 ？ ###

*  HashMap 是线程不安全的，HashTable 是线程安全的；
 *  由于线程安全，所以 HashTable 的效率比不上 HashMap；
 *  HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而 HashTable不允许；
 *  HashMap 默认初始化数组的大小为16，HashTable 为 11，前者扩容时，扩大两倍，后者扩大两倍+1；
 *  HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode

### Q10. Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是线程安全，它与 HashTable 在线程同步上有什么不同？ ###

ConcurrentHashMap 类（是 Java并发包 java.util.concurrent 中提供的一个线程安全且高效的 HashMap 实现）。

HashTable 是使用 synchronize 关键字加锁的原理（就是对对象加锁）；

而针对 ConcurrentHashMap，在 JDK 1.7 中采用 分段锁的方式；JDK 1.8 中直接采用了CAS（无锁算法）+ synchronized。

### Q11. HashMap & ConcurrentHashMap 的区别 ？ ###

除了加锁，原理上无太大区别。

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

/** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        ......
    }

HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而 ConcurrentHashMap 不允许；

因为hashtable,concurrenthashmap它们是用于多线程的，并发的 ，如果map.get(key)得到了null，不能判断到底是映射的value是null,还是因为没有找到对应的key而为空，而用于单线程状态的hashmap却可以用containKey（key） 去判断到底是否包含了这个null。

hashtable为什么就不能containKey(key)

一个线程先get(key)再containKey(key)，这两个方法的中间时刻，其他线程怎么操作这个key都会可能发生，例如删掉这个key

说明：网上搜集整理后作了部分修改而来，小部分散装内容原文出处找不到链接了。

参考链接： https://baijiahao.baidu.com/s?id=1664890257742088649&wfr=spider&for=pc