• HashMap中的hash 方法

    HashMap中的hash方法为什么要右移 16 位异或？

    之所以要对 hashCode 无符号右移 16 位并且异或，核心目的是为了让 hash 值的散列度更高，尽可能减少 hash 表的 hash 冲突，从而提升数据查找的性能。

    HashMap 的 put 方法

    在 HashMap 的 put 方法里面，是通过 Key 的 hash 值与数组的长度取模计算 得到数组的位置。
    而在绝大部分的情况下，n 的值一般都会小于 2^16 次方，也就是 65536。所以也就意味着 i 的值 ， 始终是使用 hash 值的低 16 位与(n-1)进行取模运算，这个是由与运算符&的特性决定的。
    这样就会造成 key 的散列度不高，导致大量的 key 集中存储在固定的几个数组位置，很显然会影响到数据查找性能。 
    1.  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    2.                    boolean evict) {
    3.         Node[] tab; Node p; int n, i;
    4.         if ((tab = table) == null || (n = tab.length) == 0)
    5.             n = (tab = resize()).length;
    6.         if ((p = tab[i = (n - 1) & hash]) == null)
    7.             tab[i] = newNode(hash, key, value, null);
    8.         else {
    9.             Node e; K k;
    10.             if (p.hash == hash &&
    11.                 ((k = p.key) == key || (key != null && key.equals(k))))
    12.                 e = p;
    13.             else if (p instanceof TreeNode)
    14.                 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
    15.             else {
    16.                 for (int binCount = 0; ; ++binCount) {
    17.                     if ((e = p.next) == null) {
    18.                         p.next = newNode(hash, key, value, null);
    19.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    20.                             treeifyBin(tab, hash);
    21.                         break;
    22.                     }
    23.                     if (e.hash == hash &&
    24.                         ((k = e.key) == key || (key != null && key.equals(k))))
    25.                         break;
    26.                     p = e;
    27.                 }
    28.             }
    29.             if (e != null) { // existing mapping for key
    30.                 V oldValue = e.value;
    31.                 if (!onlyIfAbsent || oldValue == null)
    32.                     e.value = value;
    33.                 afterNodeAccess(e);
    34.                 return oldValue;
    35.             }
    36.         }
    37.         ++modCount;
    38.         if (++size > threshold)
    39.             resize();
    40.         afterNodeInsertion(evict);
    41.         return null;
    42.     }

    HashMap 的 hash 方法

    为了提升 key 的 hash 值的散列度，在 hash 方法里面，做了位移运算。首先使用 key 的 hashCode 无符号右移 16 位，意味着把 hashCode 的高位移动到了低位。然后再用 hashCode 与右移之后的值进行异或运算，就相当于把高位和低位的特征进行和组合。从而降低了 hash 冲突的概率。如下图: 
    1.  static final int hash(Object key) {
    2.         int h;
    3.         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    4. }

  • 相关阅读:
    常见的内网穿透代理工具
    QML的语法——样式表QSS
    R语言因子数据的表格和列联表（交叉表）生成：使用table函数将单个因子变量呈现为表格、两个因子变量呈现为列联表
    2022年，是危机还是新的机遇？
    SQL必会知识点（一）
    ReactDOM.render在react源码中执行之后发生了什么？
    索引的基本知识
    6.28日刷题题解
    [黑马程序员C++笔记]P168-P173模板-函数模板
    PX4飞行模式
  • 原文地址：https://blog.csdn.net/qq_63431773/article/details/133188287