JDK 源码对你最有触动的是哪一段#HashMap

​HashMap

链表长度>=8 转红黑树

HashMap 里针对链表长度>=8 转红黑树中“8”的选定原因的注释。

设计者首先说明了 hashmap 中使用红黑树的优点——树节点可以通过 instanceof 方法快速识别，并且查询的复杂度很低(logn)，在冲突很多的情况下，仍然能保证查询的效率。

接着，设计者又说明了树的弊端——树节点的空间大小是普通节点的 2 倍。所以为了节省空间，只有在足够多的节点发生冲突时（链表长度>=8 并且数组大小>=64），才会考虑去转换，并且当冲突减少时，会重新变化为链表。

设计者十分严谨，在注释中列出了链表长度为 0～8 时的泊松分布概率，还附上了泊松分布的公式以及 wiki 地址。冲突节点个数达到 8 个的概率为 0.00000006，不到千万分之一，这种概率是很小的。这个“8”是设计者对时间、空间损耗的权衡考量之下，所选取的转化边界值。

设计者的这种对代码高效以及严谨的追求触动了我

map 的容量算法

Map.putAll 中的初始化 map 的容量算法 ((float)s / loadFactor) + 1.0F

官方解释

 public void putAll(Map<? extends K, ? extends V> m) {        tryPresize(m.size());        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())            putVal(e.getKey(), e.getValue(), false);    }​​  final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {        int s = m.size();        if (s > 0) {            if (table == null) { // pre-size                float ft = ((float)s / loadFactor) + 1.0F;                int t = ((ft < (float)MAXIMUM_CAPACITY) ?                         (int)ft : MAXIMUM_CAPACITY);                if (t > threshold)                    threshold = tableSizeFor(t);            }            else if (s > threshold)                resize();            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {                K key = e.getKey();                V value = e.getValue();                putVal(hash(key), key, value, false, evict);            }        }    }

点击并拖拽以移动

当我们使用 HashMap(int initialCapacity)来初始化容量的时候，HashMap 并不会使用我们传进来的 initialCapacity 直接作为初始容量。 JDK 会默认帮我们计算一个相对合理的值当做初始容量。所谓合理值，其实是找到第一个比用户传入的值大的 2 的幂。 但是，这个值看似合理，实际上并不尽然。因为 HashMap 在根据用户传入的 capacity 计算得到的默认容量，并没有考虑到 loadFactor 这个因素，只是简单机械的计算出第一个大约这个数字的 2 的幂。 loadFactor 是负载因子，当 HashMap 中的元素个数（size）超过 threshold = loadFactor * capacity 时，就会进行扩容。 也就是说，如果我们设置的默认值是 7，经过 JDK 处理之后，HashMap 的容量会被设置成 8，但是，这个 HashMap 在元素个数达到 8*0.75 = 6 的时候就会进行一次扩容，这明显是我们不希望见到的, 并且而 rehash 的过程是比较耗费时间的 初始化容量要设置成 expectedSize/0.75 + 1 的话，可以有效的减少冲突也可以减小误差。

这个算法在 guava 中有实现

public static <K, V> HashMap<K, V> newHashMap(Map<? extends K, ? extends V> map) {    return new HashMap<>(map);  }   /**   * Creates a {@code HashMap} instance, with a high enough "initial capacity" that it <i>should</i>   * hold {@code expectedSize} elements without growth. This behavior cannot be broadly guaranteed,   * but it is observed to be true for OpenJDK 1.7. It also can't be guaranteed that the method   * isn't inadvertently <i>oversizing</i> the returned map.   *   * @param expectedSize the number of entries you expect to add to the returned map   * @return a new, empty {@code HashMap} with enough capacity to hold {@code expectedSize} entries   *     without resizing   * @throws IllegalArgumentException if {@code expectedSize} is negative   */  public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(int expectedSize) {    return new HashMap<>(capacity(expectedSize));  }   /**   * Returns a capacity that is sufficient to keep the map from being resized as long as it grows no   * larger than expectedSize and the load factor is ≥ its default (0.75).   */  static int capacity(int expectedSize) {    if (expectedSize < 3) {      checkNonnegative(expectedSize, "expectedSize");      return expectedSize + 1;    }    if (expectedSize < Ints.MAX_POWER_OF_TWO) {      // This is the calculation used in JDK8 to resize when a putAll      // happens; it seems to be the most conservative calculation we      // can make.  0.75 is the default load factor.      return (int) ((float) expectedSize / 0.75F + 1.0F);    }    return Integer.MAX_VALUE; // any large value  }

点击并拖拽以移动

java8 里 hashmap 计算 table 大小的方法

static final int tableSizeFor(int cap) {    int n = cap - 1;    n |= n >>> 1;    n |= n >>> 2;    n |= n >>> 4;    n |= n >>> 8;    n |= n >>> 16;    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}

因为传入参数减 1 后，为 1 的最高位的前一位算出的值就是我们要求得的 table 大小（比如 7-1 是 6，二进制 0110，为 1 的最高位对应十进制的 4，而 4 的上一位是 8，也就是我们要求的数组大小）。

作者将最高位 1 不断的往后移位操作，再与之前的数进行按位或运算就可以得到一串连续的 1，此时再加 1 就可以得到数组期望的大小（如 0110 最后得到 0111，再加 1 就是 1000 得到的 8 就是我们要的数组大小）。

作者利用移位运算和或运算都是计算机处理起来比较快的运算，很巧妙地得到了数组地大小。虽然这个方法在 jdk11 改成使用 Integer.numberOfLeadingZeros（应该是很小的数和很大数都要做一样多的操作，造成一定的浪费。

而 jdk11 里通过 if 判断大小可以减少移位操作的次数，个人认为是这个原因所以修改成 Integer.numberOfLeadingZeros），但是 Integer.numberOfLeadingZeros 的修改应该也是有借鉴到原来的这个方法（个人认为）。

jdk8 的这个计算方法还是设计的非常巧妙。

31 奇素数作为乘数来避免冲突

 public int hashCode() {        int h = hash;        if (h == 0 && value.length > 0) {            char val[] = value;            for (int i = 0; i < value.length; i++) {                h = 31 * h + val[i];            }            hash = h;        }        return h;}

代码中的 31 是怎么来的？为什么在众多数字中选择 31 而不是其它数值 注释中提到了 hashcode 的计算逻辑 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 参考网上部分科普文章及 Stack Overflow 上的一些解答 Why does Java's hashCode() in String use 31 as a multiplier? - Stack Overflow 主要原因有以下两个方面

1. 以 31 作为乘子参与乘法计算得出的 hashcode 值，在后面进行取模(实际上是与运算时)，得到相同 index 的概率会降低，即降低了哈希冲突的概率。但同时 37、41、43 等等，也都是不错的选择，为什么最终选择了 31 呢？这就要看第二个原因了

2. 31 有个很好的性能，即用移位和减法来代替乘法，可以得到更好的性能： 31 * i == (i << 5）- i， 现代的 VM 可以自动完成这种优化。

涉及到一个叫哈希算法冲突率的问题，举个例子 最常见的哈希算法是取模法 数组长度 4,有个数据 5 算 5％4，结果是 1,那么就把 5 放到数组下标是 1 的位置。 算 6％4，结果是 2,那么就把 6 放到数组下标是 2 的位置。 算 7％4，结果是 3,那么就把 7 放到数组下标是 3 的位置。 算 8％4，结果是 4,那么就把 8 放到数组下标是 4 的位置。 一直没有出现冲突 如果接下来算 9％4，结果是 1,那么就把 9 放到数组下标是 1 的位置。此时之前的数字 5 已经放在下标是 1 的位置，这时候数组下标为 1 的位置，就存储了两个值，这个就是哈希冲突，如果出现哈希冲突之后就只能按照顺序继续存放。 如果数组长度大，数据分布广泛，哈希冲突率就低，反之哈希冲突率就高

HashMap 源码中扰动函数 hash()

这里找了一下 JDK 1.8 中的源码，粘贴一下方便看：

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

理由： 这端代码是之前在学习 HashMap 源码的时候，留下深刻印象的一段代码，这段代码虽然很短，但是在我看来简洁而优雅的达到了作者想要达到的最终效果。

先说一下这段代码的意思，其实就是获取 HashMap 中的 key 的 hashCode，然后将这个值的高 16 和低 16 位做异或运算，最终返回的值，在后续确定这个 key 存储的 hash 桶的位置时，再与 hash 桶的个数做取模操作，不过 HashMap 中使用了更为高效的位运算的方式，因为 HashMap 的桶个数是 2 的 n 次幂（这里其实也是为了均匀分布），所以用了 & 运算即 hash & (n-1)，可以替代取模的操作，直接使用位运算，相比 % 运算，效率更高，可以说是细节控。

其次说回这个 hash() 函数，h >>> 16 这个动作是将 key 的 hashCode 右移 16 位，这样得到的 32 位二级制数的高 16 位就都会是 0，在与原来的 hashcode 做异或操作的时候，高位和低位的值就都会参与进来，这样做的好处是，当两个 key 的 hash 值的高 16 位不同，但是低 16 位相同的时候，避免了 hash 冲突，要知道 HashMap 的元素发生哈希冲突时，会开始链化，当数量到达阈值的时候，还会转为红黑树，所以要尽可能的让元素分布均匀，这就要求处理的时候要尽可能的降低冲突的概率，HashMap 这里的高低位异或运算，让高低位都参与了后续的取模，就是降低概率的一种方式。

当时看到这段代码的时候，还好好的研究了一番二级制的位运算，而且这段代码仅仅是增加的这一步异或操作，可能直接影响了结果，不仅巧妙，而且将性能和优化考虑到极致了，当时觉得这可能就是大神和我的差距，锱铢必较，一点点性能都不放过，不由得感叹，拍手叫好。现在想来，可能这就是程序员应该要有的专业素养吧！一个需求，堆砌垃圾代码也能完成，优化到极致也能完成，但是认真研读，就高下立判。很多时候我们的态度决定了高度，我个人以为程序员的进阶之路， 就是抛弃完成能跑就行的垃圾代码，而追求让后人看了拍手称绝的好代码。

​