目录
1、HashMap简介
2、HashMap数据结构
3、HashMap源码分析
3.1、HashMap继承结构和层次关系
3.2、类中属性
3.3、构造方法
3.4、定位哈希桶数组索引位置
3.5、常用方法
3.5.1、get()
3.5.2、红黑树获取节点
3.5.3、链表获取节点
3.5.4、put 方法
3.5.5、红黑树put值，putTreeVal()
3.5.6、treeifyBin(): 将链表节点转为红黑树节点
3.5.7、 treeify()树化，构建红黑树
3.5.8、moveRootToFront
3.5.9、 checkInvariants
3.5.10、resize
4、相关介绍
4.1、负载因子
4.2、如何确定元素在数组中的索引下标?
1、先使用hash方法
2. 索引下标取值为：(n - 1) & hash
5、总结
HashMap是基于哈希表的Map接口的实现，提供所有可选的映射操作，允许使用null值和null键。JDK 1.8 对 HashMap 进行了比较大的优化，底层实现由之前的 “数组+链表” 改为 “数组+链表+红黑树”。
当链表节点较少时仍然是以链表存在，当链表节点较多时（大于8）会转为红黑树
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
}transient Node<K,V>[] table：这是一个Node类型的数组（也有称作Hash桶），可以从下面源码中看到静态内部类Node在这边可以看做就是一个节点，多个Node节点构成链表，当链表长度大于8的时候转换为红黑树。
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {// 默认容量16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量static final int MAXIMUM_CAPACITY = 1 << 30; final float loadFactor;//负载因子，用于扩容// 默认负载因子0.75static final float DEFAULT_LOAD_FACTOR = 0.75f; // 链表节点转换红黑树节点的阈值, 9个节点转static final int TREEIFY_THRESHOLD = 8; // 红黑树节点转换链表节点的阈值, 6个节点转static final int UNTREEIFY_THRESHOLD = 6; // 转红黑树时, table的最小长度static final int MIN_TREEIFY_CAPACITY = 64; transient Node<K,V>[] table;// 链表节点, 继承自Entrystatic class Node<K,V> implements Map.Entry<K,V> { final int hash;final K key;V value;Node<K,V> next;// ... ...}// 红黑树节点static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // needed to unlink next upon deletionboolean red;// ...}
}总共有4个构造方法，与初始容量（16）和负载因子（0.75）有关。
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);}public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。因为HashMap 的数据结构是“数组+链表+红黑树”的结合，所以我们当然希望这个 HashMap 里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用 hash 算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表/红黑树，大大优化了查询的效率。HashMap 定位数组索引位置，直接决定了 hash 方法的离散性能。下面是定位哈希桶数组的源码：
// 代码1
static final int hash(Object key) { // 计算key的hash值int h;// 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算//高16位与16位0值异或，低16位与高16位异或return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 代码2
int n = tab.length;
// 将(tab.length - 1) 与 hash值进行&运算
int index = (n - 1) & hash;整个过程本质上就是三步：
方法解读：
1、& 比 % 具有更高的效率：对于任意给定的对象，只要它的 hashCode() 返回值相同，那么计算得到的 hash 值总是相同的。我们首先想到的就是把 hash 值对 table 长度取模运算，这样一来，元素的分布相对来说是比较均匀的。
但是模运算消耗还是比较大的，我们知道计算机比较快的运算为位运算，因此 JDK 团队对取模运算进行了优化，使用上面代码2的位与运算来代替模运算。这个方法非常巧妙，它通过 “(table.length -1) & h” 来得到该对象的索引位置，这个优化是基于以下公式：x mod 2^n = x & (2^n - 1)。我们知道 HashMap 底层数组的长度总是 2 的 n 次方，并且取模运算为 “h mod table.length”，对应上面的公式，可以得到该运算等同于“h & (table.length - 1)”。这是 HashMap 在速度上的优化，因为 & 比 % 具有更高的效率。
2、让高位也参与运算增强散列：在 JDK1.8 的实现中，还优化了高位运算的算法，将 hashCode 的高 16 位与 hashCode 进行异或运算，主要是为了在 table 的 length 较小的时候，让高位也参与运算，并且不会有太大的开销。
public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 1.对table进行校验：table不为空 && table长度大于0 && // table索引位置(使用table.length - 1和hash值进行位与运算)的节点不为空if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 2.检查first节点的hash值和key是否和入参的一样，如果一样则first即为目标节点，直接返回first节点if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;// 3.如果first不是目标节点，并且first的next节点不为空则继续遍历if ((e = ) != null) {if (first instanceof TreeNode)//判断当前节点不是下一个节点// 4.如果是红黑树节点，则调用红黑树的查找目标节点方法getTreeNodereturn ((TreeNode<K,V>)first).getTreeNode(hash, key);do {// 5.执行链表节点的查找，向下遍历链表, 直至找到节点的key和入参的key相等时,返回该节点if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}// 6.找不到符合的返回空return null;
}get过程总结：由于map底层存储节点内部都是(hash、key、value、next)，故首先获取key的hash，得到（hash、key）。然后根据（hash、key）获取node，最后取值。
获取node：首先确保node数组不为空、有值且索引处有值。然后根据（hash、key）判断。接着判断下一个值时红黑树则走红黑树，是链表则循环链表。
如果是红黑树节点，则调用红黑树的查找目标节点方法 getTreeNode
final TreeNode<K,V> getTreeNode(int h, Object k) {// 1.首先找到红黑树的根节点；2.使用根节点调用find方法return ((parent != null) ? root() : this).find(h, k, null);
}//this代表调用getTreeNode的对象，即node数组中的first对象final TreeNode<K,V> root() {for (TreeNode<K,V> r = this, p;;) {if ((p = r.parent) == null)return r;r = p;}}使用根节点调用find()
将 p 节点与 k 进行比较。如果传入的 key（即代码中的参数 k）所属的类实现了 Comparable 接口（kc 不为空），则将 k 跟 p 节点的 key 进行比较（kc 实现了 Comparable 接口，因此通过 kc 的比较方法进行比较），并将比较结果赋值给 dir，如果 dir<0 则代表 k<pk，则向 p 节点的左边遍历（pl）；否则，向 p 节点的右边遍历（pr）。
/*** 从调用此方法的节点开始查找, 通过hash值和key找到对应的节点* 此方法是红黑树节点的查找, 红黑树是特殊的自平衡二叉查找树* 平衡二叉查找树的特点：左节点<根节点<右节点*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {// 1.将p节点赋值为调用此方法的节点，即为红黑树根节点TreeNode<K,V> p = this;// 2.从p节点开始向下遍历do {int ph, dir; K pk;TreeNode<K,V> pl = p.left, pr = p.right, q;// 3.如果传入的hash值小于p节点的hash值，则往p节点的左边遍历if ((ph = p.hash) > h)p = pl;else if (ph < h) // 4.如果传入的hash值大于p节点的hash值，则往p节点的右边遍历p = pr;// 5.如果传入的hash值和key值等于p节点的hash值和key值,则p节点为目标节点,返回p节点else if ((pk = p.key) == k || (k != null && k.equals(pk)))return p;else if (pl == null) // 6.p节点的左节点为空则将向右遍历p = pr;else if (pr == null) // 7.p节点的右节点为空则向左遍历p = pl;// 8.将p节点与k进行比较else if ((kc != null ||(kc = comparableClassFor(k)) != null) && // 8.1 kc不为空代表k实现了Comparable(dir = compareComparables(kc, k, pk)) != 0)// 8.2 k<pk则dir<0, k>pk则dir>0// 8.3 k<pk则向左遍历(p赋值为p的左节点), 否则向右遍历p = (dir < 0) ? pl : pr;// 9.代码走到此处, 代表key所属类没有实现Comparable, 直接指定向p的右边遍历else if ((q = pr.find(h, k, kc)) != null) return q;// 10.代码走到此处代表“pr.find(h, k, kc)”为空, 因此直接向左遍历elsep = pl;} while (p != null);return null;
}find()过程总结：从红黑树根节点开始遍历，先比较hash值，依据树的左子树<根<右子树原则向下遍历，如果hash值相等则比较key，key比较时需要判断是否可比（是否实现Comparable<X>），可比较时判断为null和类型不同的情况。一直向左或右遍历，直到匹配到或不存在为止。
comparableClassFor详解见：Java集合(五二): comparableClassFor(Object x)方法解读_mingyuli的博客-CSDN博客
直接遍历链表比较hash和key即可。
do {if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null); public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 1.校验table是否为空或者length等于0，如果是则调用resize方法进行初始化if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 2.通过hash值计算索引位置，将该索引位置的头节点赋值给p，如果p为空则直接在该索引位置新增一个节点即可if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {// table表该索引位置不为空，则进行查找Node<K,V> e; K k;// 3.判断p节点的key和hash值是否跟传入的相等，如果相等, 则p节点即为要查找的目标节点，将p节点赋值给e节点if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 4.判断p节点是否为TreeNode, 如果是则调用红黑树的putTreeVal方法查找目标节点else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 5.走到这代表p节点为普通链表节点，则调用普通的链表方法进行查找，使用binCount统计链表的节点数for (int binCount = 0; ; ++binCount) {// 6.如果p的next节点为空时，则代表找不到目标节点，则新增一个节点并插入链表尾部if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 7.校验节点数是否超过8个，如果超过则调用treeifyBin方法将链表节点转为红黑树节点，// 减一是因为循环是从p节点的下一个节点开始的if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);break;}// 8.如果e节点存在hash值和key值都与传入的相同，则e节点即为目标节点，跳出循环if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e; // 将p指向下一个节点}}// 9.如果e节点不为空，则代表目标节点存在，使用传入的value覆盖该节点的value，并返回oldValueif (e != null) {V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e); // 用于LinkedHashMapreturn oldValue;}}++modCount;// 10.如果插入节点后节点数超过阈值，则调用resize方法进行扩容if (++size > threshold)resize();afterNodeInsertion(evict); // 用于LinkedHashMapreturn null;
}红黑树操作版的putVal。那么它的逻辑应该与putVal函数的里的for (int binCount = 0; ; ++binCount)差不多，即：如果能找到相同节点，那么返回该节点，不会做替换处理；如果不能找到相同节点，那么new一个新的TreeNode实例，把它放在应该放置的位置，并返回null（返回null代表没有找到相同节点）。
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {Class<?> kc = null;boolean searched = false;//一定需要这个变量？TreeNode<K,V> root = (parent != null) ? root() : this;//parent是被调动putTreeVal成员函数的那个节点的父节点（成员）for (TreeNode<K,V> p = root;;) {int dir, ph; K pk; //dir代表传入节点与当前循环节点的比较大小if ((ph = p.hash) > h) //如果传入节点的hash比当前处理节点小dir = -1;else if (ph < h) //如果传入节点的hash比当前处理节点大dir = 1;//如果传入节点的hash跟当前处理节点一样大，传入key与当前key判定相等，那么返回相同节点else if ((pk = p.key) == k || (k != null && k.equals(pk)))return p;//如果传入节点的hash跟当前处理节点一样大，传入key与当前key判定不相等，但又必须比出个大小来//所以要么使用comparable接口，要么使用tieBreakOrder，最终dir会被赋值一个非0值//分支进入条件1：如果类型参数K的类定义不是comparable接口的自限定//分支进入条件2：虽然类型参数K的类定义是comparable接口的自限定，但传入节点和当前节点比较后为0//总之这两种情况都没有比出大小else if ((kc == null && (kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0) {if (!searched) {//这个分支只会进入一次，因为searched马上被置为true了TreeNode<K,V> q, ch;searched = true;if (((ch = p.left) != null &&(q = ch.find(h, k, kc)) != null) || //先去左子树找((ch = p.right) != null &&(q = ch.find(h, k, kc)) != null)) //先去右子树找//如果能找到就返回相同节点，如果不能找到那说明整个红黑树里面没有相同节点，因为都找遍了//所以if (!searched)只能进入一次，当然if (!searched)分支也可能一次都不进入，//当传入节点与红黑树内所有节点都能比较出大小时return q;}//执行到这里说明if (!searched)分支已经执行过了，且没有整棵树都没有找到相同节点//但还是必须从左右子树挑一条路走，那么使用tieBreakOrderdir = tieBreakOrder(k, pk); //为保持一致，它与treeify里tieBreakOrder的实参顺序一样}//至此，dir已得到一个非0值TreeNode<K,V> xp = p; //xp暂存p引用，以备不时之需//p根据dir更新为它自己的左孩子或右孩子，更新后不为null则继续循环，为null则代表找到了最终插入位置if ((p = (dir <= 0) ? p.left : p.right) == null) {Node<K,V> xpn = xp.next; //注意还需要维护双链表结构TreeNode<K,V> x = wTreeNode(h, k, v, xpn); //new一个TreeNode实例//赋值父节点的孩子指针if (dir <= 0)xp.left = x;elsexp.right = = x; //赋值链表结构的后继指针x.parent = x.prev = xp;if (xpn != null)((TreeNode<K,V>)xpn).prev = x;//执行到这里，只是按照二叉查找的过程暂时放置了传入节点，为保持红黑树性质，//需调用balanceInsertion，调用后返回新root（如果root发生了改变），//再调用moveRootToFront，使得数组下标能指向红黑树的root节点moveRootToFront(tab, balanceInsertion(root, x));return null;//既然已经新增了节点，所以返回null}}}
整个流程在for循环里，将p节点按照二叉查找的过程往下移动（每次循环会更新p），移动的方向根据变量dir的正负来往下走，如果整棵树里都没有与传入节点相同的既存节点，那么最终肯定会找到新节点的插入位置（if ((p = (dir <= 0) ? p.left : p.right) == null)分支）：进入分支后，先new出一个TreeNode实例，再与周围节点重塑好双链表结构和红黑树结构，最后再做红黑树的自我调整以保持保持红黑树性质。
tieBreakOrder
如果两者不具有compare的资格，或者compare之后仍然没有比较出大小。那么就要通过一个决胜局再比一次，这个决胜局就是tieBreakOrder方法。
/**
* 用这个方法来比较两个对象，返回值要么大于0，要么小于0，不会为0
* 也就是说这一步一定能确定要插入的节点要么是树的左节点，要么是右节点，不然就无法继续满足二叉树结构了
*
* 先比较两个对象的类名，类名是字符串对象，就按字符串的比较规则
* 如果两个对象是同一个类型，那么调用本地方法为两个对象生成hashCode值，再进行比较，hashCode相等的* 话返回-1
* 用于不可比较或者hashCode相同时进行比较的方法, 只是一个一致的插入规则，用来维护重定位的等价性。
* /
static int tieBreakOrder(Object a, Object b) { int d;if (a == null || b == null ||(d = a.getClass().getName()Class().getName())) == 0)d = (System.identityHashCode(a) <= System.identityHashCode(b) ?-1 : 1);return d;
} final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;//如果size是小于MIN_TREEIFY_CAPACITY，那么不会进行树化，只是resizeif (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {//e指向首元素TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);//用e来new一个TreeNode实例if (tl == null)//如果head和tail都还没有赋值过hd = p;else {//如果head和tail已经赋值过，那么把p和tail相互连起来（p作为新tail放在后面）p.prev = = p;}tl = p;//更新tail} while ((e = e.next) != null); //如果e的后继不为空，让e往后移动//现在执行完，只是让原链表元素保持原来顺序全部替换为TreeNode实例，然后将它们之间的前驱后继连起来，成为双向链表if ((tab[index] = hd) != ify(tab); //调用首元素的treeify方法}}TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {return new TreeNode<>(p.hash, p.key, p.value, next);}总结：首先判断是否可以树化；然后将单链表转为以TreeNode为节点的双链表，最后转为红黑树。
final void treeify(Node<K,V>[] tab) {TreeNode<K,V> root = null;for (TreeNode<K,V> x = this, next; x != null; x = next) { //循环最后会让x指向next，然后在下一次循环里处理新xnext = (TreeNode<K,V>)x.next; //先把x的后继保存到next，这里转型是因为Node父类的next引用为Node，所以要转回来x.left = x.right = null;//x就是当前循环处理的节点。如果此时根节点还没分配，那么将x作为rootif (root == null) {x.parent = d = false; //root为黑色root = x;}// 进入else说明root已经有了// 下面的x肯定是第二个元素或更后面的元素else {K k = x.key;int h = x.hash;Class<?> kc = null; //key的Class对象for (TreeNode<K,V> p = root;;) { //初始让p指向rootint dir, ph;K pk = p.key;if ((ph = p.hash) > h)dir = -1; //代表当前处理节点x，比p小else if (ph < h)dir = 1; //代表当前处理节点x，比p大// 如果hash值一样，则只能通过别的方式分出个大小else if ((kc == null && //如果kc之前没有被赋值过，注意它与下一排在一个括号里(kc = comparableClassFor(k)) == null) || //如果的k的类定义是Comparable的泛型自限定，那么赋值给kc(dir = compareComparables(kc, k, pk)) == 0) //执行到这里说明k的类定义是Comparable的泛型自限定，且kc已经赋值为其Class对象//如果pk与k类型一样，那么返回kpareTo(x)；否则返回0，所以返回0既可能代表k和pk一样大，也可能是二者没法比dir = tieBreakOrder(k, pk); //返回-1或者1TreeNode<K,V> xp = p;//让xp指向p，因为p引用马上要被替换掉了// 根据dir的正负让p指向p的左孩子或右孩子，如果孩子不为null，继续下一次循环；否则进入分支// 只有进入if分支才能退出循环（里面有break），整个循环过程就是二叉查找的过程，直到找到叶子节点// 循环过程中，p会根据与x的比较结果一直向下移动if ((p = (dir <= 0) ? p.left : p.right) == null) {//通过二叉查找找到了x的最终位置，然后将xp（x的parent）与x连接起来x.parent = xp;if (dir <= 0)xp.left = x;elsexp.right = x;//注意x并没有给red变量赋过值root = balanceInsertion(root, x);break;}}}}moveRootToFront(tab, root);}
总结：就是将双向链表转为红黑树的过程：首先确定根节点，然后遍历下一个节点与根节点比较hash/key确定插入位置，最后做结构调整满足红黑树结构。
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {int n;if (root != null && tab != null && (n = tab.length) > 0) {int index = (n - 1) & root.hash;TreeNode<K,V> first = (TreeNode<K,V>)tab[index];//得到当前table下标指向的节点if (root != first) {//如果该table下标的第一个节点都已经是入参root了，就不用进分支了Node<K,V> rn;//r的nexttab[index] = root;//将table下标指向rootTreeNode<K,V> rp = root.prev; //因为root不是first，所以它的prev肯定不为空if ((rn = ) != null) //那么root也不是双向链表的尾节点((TreeNode<K,V>)rn).prev = rp;if (rp != = rn;if (first != null) first.prev = = first;root.prev = null;}assert checkInvariants(root);}}
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,tb = t.prev, tn = (TreeNode<K,V>)t.next;//检查双向链表的结构是否正确if (tb != null && tb.next != t)return false;if (tn != null && tn.prev != t)return false;//检查红黑树的结构是否正确if (tp != null && t != tp.left && t != tp.right)return false;if (tl != null && (tl.parent != t || tl.hash > t.hash))return false;if (tr != null && (tr.parent != t || tr.hash < t.hash))return false;//检查红黑树的颜色是否正确if (t.red && tl != null && tl.red && tr != null && tr.red)return false;//递归调用自身，检查左右孩子if (tl != null && !checkInvariants(tl))return false;if (tr != null && !checkInvariants(tr))return false;return true;}
JDK8 HashMap源码行级解析 史上最全最详细解析_anlian523的博客-CSDN博客
负载因子（loadFactor）：源码中有个公式为 threshold = loadFactor * 容量。HashMap和HashSet都允许你指定负载因子的构造器，表示当负载情况达到负载因子水平的时候，容器会自动扩容，HashMap默认使用的负载因子值为0.75f（当容量达到四分之三进行再散列（扩容）），即表示不会等到容器满时才扩容。
当负载因子越大的时候能够容纳的键值对就越多但是查找的代价也会越高。所以如果知道将要在HashMap中存储多少数据，那么你可以创建一个具有恰当大小的初始容量这可以减少扩容时候的开销（优化手段）。但是大多数情况下0.75在时间跟空间代价上达到了平衡所以不建议修改。
为什么不直接返回key.hashCode()呢？还要与 (h >>> 16)异或？
一共有两个步骤
hash方法中将key的hashcode与他的高16位进行一次亦或运算（hashcode本身的低16位与高16位进行 ^ 运算）。
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}为什么获取key的hashcode之后还需要和hashcode右移16位进行亦或运算？
0000 0100 1011 0011 1101 1111 1110 0001 >>> 16 (无符号右移16位)0000 0000 0000 0000 0000 0100 1011 0011 hashcode为int类型，4个字节32位，为了确保散列性，肯定是32位都能进行散列算法计算最好。
1.1、为什么用亦或计算？
二进制位计算，a 只可能为0、1，b只可能为0、1。a中0出现几率为1/2，1也是1/2，b同理。
平时用的运算符有三种，或(｜)，与（&），异或（^）。
a、b进行位运算，有4种可能 00，01,10,11
所以，进行异或（^）计算，得到的结果肯定更为平均，不会偏向0或者偏向1，更为散列。
1.2、右移16位进行亦或计算
我将其拆分为两部分，前16位的亦或运算，和后16位的亦或运算。
1.3、结论：
jdk1.8中，hashMap获取某个key值，通过
(n - 1) & hash
去得到索引下标，其中,n为当前map容量，hash为key通过hash方法得到的值。
参考：
HashMap中hash(Object key)原理，为什么(hashcode ＞＞＞ 16)。_杨涛的博客的博客-CSDN博客
hashMap1.8 resize（）个人解读_io.ke的博客-CSDN博客
原文：史上最详细的 JDK 1.8 HashMap 源码解析_程序员囧辉-CSDN博客_hashmap详解
JDK8 HashMap源码行级解析 红黑树操作 史上最全最详细图解_anlian523的博客-CSDN博客treeifyBinJDK8 HashMap源码行级解析 红黑树操作 史上最全最详细图解_anlian523的博客-CSDN博客
本文发布于:2024-01-31 00:38:18，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170663368624117.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
