简单介绍一下JDK1.8 HashMap的数据如下

讯享网

HashMap存放的是一个Node

1、 jdk1.8 HshMap.put()方法详解

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 

2、hash(key)源码如下：

设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)，就是把高16bit和低16bit异或了一下，返回一个掩码。设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞

讯享网// 计算hash值，hashcode值是32位，讲高16位和第16位做异或操作，返回一个掩码 // 一个简单的操作，不会影响效率 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } // 计算桶的下标（桶的长度-1与hash值） // 因为桶的长度n不会很长（默认长度DEFAULT_INITIAL_CAPACITY为16） // 因此：key的高位和地位都参与了桶的下标计算，减少了碰撞 (n - 1) & hash

3、putVal（）

put方法主要做了以下操作

1、判断数组（哈希桶）是否为空，如果为空，重新计算一下大小(初始化一个桶)
2、获取要插入元素在 哈希桶中的位置（tab[(n - 1) & hash]）
3、如果桶的这个位置没有数据，new一个节点，存放桶里面
4、如果有数据，判断这个位置的第一个节点是否相等（相等直接替换赋值，返回old值）
5、如果和第一个节点不相等，再判断第一个节点的下一个节点是否是红黑树，如果是，通过红黑树方式put
6、如果和第一个节点不相等，也不是红黑树，那么就按照链表结构处理。判断是否和链表的下一个相等，如果相等，直接复制替换。
7、如果链表里面没有，如果大于了阙值(大于等于TREEIFY_THRESHOLD，默认为8)， 需要扩容的大小，链表转换成红黑树；

具体源码如下：

// onlyIfAbsent在true的情况下不改变已有value值,evict(驱逐)在false的情况下table为创作模式. 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.判断数组（桶）是否为空，如果为空，重新计算一下大小(初始化一个桶) if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; / * 2. 获取要插入元素在 哈希桶中的位置,同时将值赋值给p(定位了桶的位置) * i = (n - 1) & hash:就是Node在哈希桶中tab的下标（位置） */ // 如果这个位置没有Node, if ((p = tab[i = (n - 1) & hash]) == null) // 直接创建一个新的Node tab[i] = newNode(hash, key, value, null); // 如果有这个位置的node不为null,原来这个桶的位置上有Node else { Node<K, V> e; K k; // 如果第一个位置和put的hash一致，直接替换 // 桶里面存放的Node，node是一个单向链表结构 if (p.hash == hash && ((k = p.key) == key || (key != null && ey.equals(k)))) e = p;// 讲值赋值给e（其实后面是做替换） // 如果p链表的类型是属于红黑树，用红黑树的方式进行put else if (p instanceof TreeNode) e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value); // 如果不是红黑树，就是链表，按链表方式处理 // 定位到这个hash桶了 但是这里面是链表（没有进行过树化） else { // 遍历链表 for (int binCount = 0; ; ++binCount) { // p节点的next为空 直接在后面插入，新建一个节点 // e是p节点的下一个节点 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 链表转变为红黑树。如果本来是链表 而且长度超过了8 那么就进行树化  if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果和下一个节点相等，且不为null，表明找到当前节点，结束循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // 讲e(p.next())赋值给p，继续下一次循环 p = e; } } // 如果找到了节点，说明关键字相同，进行覆盖操作，直接返回旧的关键字的值 // 注意e是p的下一个节点 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); //空实现，里面没有实现方法 return oldValue; } } // 没有找到相应的key执行下面操作 // 修改次数+1 和fastRemove()有关也和并发修改有关 ++modCount; // 容量hashmap存放node的个数+1，如果大于了阙值 需要扩容的大小 if (++size > threshold) resize(); afterNodeInsertion(evict); //空实现,里面没有实现方法 return null; }

4、put方法里面用到的函数

1、resize() 重新计算容量，或者是扩容方法
2、p.putTreeVal(this, tab, hash, key, value) 存放数据倒红黑树里面
3、treeifyBin(tab, hash) 将链表转换为红黑树

[4.1] resize()重新计算容量

源码：

讯享网final HashMap.Node<K, V>[] resize() { // oldTable:当前的数组（旧的hash桶） HashMap.Node<K, V>[] oldTab = table; // 如果你是新创建的话 表的大小就是0 否则就是原来的大小 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 第一次是为0的 代表DEFAULT_INITIAL_CAPACITY = 1 << 4; int oldThr = threshold; // 新的容量，新的阙值：扩容后存放数据的大小（及hashmap的size） int newCap, newThr = 0; //如果旧的容量大于0 if (oldCap > 0) { // 如果旧的容量大于等于最大容量，返回旧 if (oldCap >= MAXIMUM_CAPACITY) { // 扩容大小 = 最大范围 threshold = Integer.MAX_VALUE; // 直接返回就旧的数组 return oldTab; } // 将旧的数组（桶）扩容一倍赋值给newCap（数组） // 如果newCap小于最大容量，并且旧容量>=初始化16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 存放数据的size扩大一倍。左移1位，新size容量 = 旧size容量*2 newThr = oldThr << 1; } // 如果旧的存放数据的容量>0，那么新的桶大小=旧的容量 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // 说明是 threshold为0的时候的情况 else { // zero initial threshold signifies using defaults // 新的容量为默认容器的容量 newCap = DEFAULT_INITIAL_CAPACITY; // 新的阙值为 默认的容量 * 负载因子 newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 如果新的如果新的扩容为0 ，上面走的else if (oldThr > 0) // 计算新的阙值 if (newThr == 0) { // 计算得到新的阙值 float ft = (float) newCap * loadFactor; // 如果新的桶容量小于最大容量 并且 阙值小于最大容量，新的阙值=ft，否则新的阙值= int型最大值 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE); } // 阙值 = 新的阙值 threshold = newThr; @SuppressWarnings({ 
  
    
  "rawtypes", "unchecked"}) // 建一个新的哈希数组桶 大小为新的容量 HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap]; table = newTab; // 如果旧的数组(桶)，遍历数组 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { HashMap.Node<K, V> e; // 如果旧的hash桶的元素不为null e为旧的hash桶的元素 if ((e = oldTab[j]) != null) { oldTab[j] = null; // 如果hashmap就只有一个元素 if (e.next == null) // 那么在新的hash桶给你安排一个位置 // 位置是你的hash值&新的桶的容量（size）-1, // 这里是hashmap存放数据的一种算法， newTab[e.hash & (newCap - 1)] = e; // 如果不只一个元素并且是红黑树 else if (e instanceof HashMap.TreeNode) // 分割 将树中的节点 分割到高位或者地位上去  ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap); // 其他情况，就是一个普通的链表 else { // preserve order // 如果扩容后，元素的index依然与原来一样，那么使用这个低位head和tail指针 HashMap.Node<K, V> loHead = null, loTail = null; // 如果扩容后，元素的index=index+oldCap，那么使用这个高位head和tail指针 HashMap.Node<K, V> hiHead = null, hiTail = null; // 下一个节点 HashMap.Node<K, V> next; do { next = e.next; // 这个地方直接通过hash值与oldCap进行与操作得出元素在新数组的index // 看是否需要进行位置变化 新增位的值 不需要变化就放在原来的位置 // 这里的判断需要引出一些东西：oldCap 假如是16，那么二进制为 10000，扩容变成 ，也就是32. // 当旧的hash值 与运算 10000，结果是0的话，那么hash值的右起第五位肯定也是0，那么该于元素的下标位置也就不变。 if ((e.hash & oldCap) == 0) { // 第一次进来时给链头赋值 if (loTail == null) loHead = e; // 给链尾赋值 else loTail.next = e; // 重置该变量 loTail = e; } // 需要变化 就构建高位放置的链表 // 如果不是0，那么就是1，也就是说，如果原始容量是16，那么该元素新的下标就是：原下标 + 16（10000b） else { // 第一次进来时给链头赋值 if (hiTail == null) hiHead = e; // 给链尾赋值 else hiTail.next = e; // 重置该变量 hiTail = e; } } while ((e = next) != null); // 理想情况下，可将原有的链表拆成2组，提高查询性能。 if (loTail != null) { // 销毁实例，等待GC回收 loTail.next = null; // 置入数组（桶bucket）中 newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; // 在新链表的位置赋值 newTab[j + oldCap] = hiHead; } } } } } return newTab; }

[4.2] p.putTreeVal(this, tab, hash, key, value) 存放数据倒红黑树里面

下一节详细讲解红黑树
[4.3] treeifyBin(tab, hash)讲红黑树转换为链表

树化过程：
1、根据哈希表中元素个数确定是扩容还是树形化
2、树化
遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系
然后让桶第一个元素指向新建的树头结点，替换桶的链表内容为树形内容
但是我们发现，之前的操作并没有设置红黑树的颜色值，现在得到的只能算是个二叉树。在 最后调用树形节点 hd.treeify(tab) 方法进行塑造红黑树

/ * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */ // 大体意思：在给定的散列中，替换桶中的所有链接节点，除非表太小，在这种情况下，可以进行调整。 // 及树化 final void treeifyBin(HashMap.Node<K, V>[] tab, int hash) { int n, index; HashMap.Node<K, V> e; // 如果当前哈希表为空，或者哈希表中元素的个数小于 进行树形化的阈值(默认为 64)，就去新建/扩容 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); // hash表的元素个数大于MIN_TREEIFY_CAPACITY，树华操作 else if ((e = tab[index = (n - 1) & hash]) != null) { // 红黑树的头、尾节点 HashMap.TreeNode<K, V> hd = null, tl = null; do { // 新建一个树节点，存放数据为当前链表节点e一直 HashMap.TreeNode<K, V> p = replacementTreeNode(e, null); // 设置头节点 if (tl == null) hd = p; // 第二次循环后，设置上一个节点为tl，当链表节点e设置为tl的下一个节点 else { p.prev = tl; tl.next = p; } // 赋值，进行下一次循环 tl = p; } while ((e = e.next) != null); // 将树的头节点放到hash表中，然后给树标记颜色，将二叉树转变为红黑树 if ((tab[index] = hd) != null) // 二叉树转变为红黑树 hd.treeify(tab); } } // 树化 final void treeify(HashMap.Node<K, V>[] tab) { HashMap.TreeNode<K, V> root = null; for (HashMap.TreeNode<K, V> x = this, next; x != null; x = next) { next = (HashMap.TreeNode<K, V>) x.next; x.left = x.right = null; // 确定头结点，为黑色 if (root == null) { x.parent = null; x.red = false; root = x; } // 确定根节点后，设置子节点 else { K k = x.key; int h = x.hash; Class<?> kc = null; for (HashMap.TreeNode<K, V> p = root; ; ) { // ph存放根节点的hash（父节点的hash）， // dir是存放 比较当前节点和父节点的大小的一个变量 int dir, ph; K pk = p.key; // 如果父节点hash大于当前节点的hash，dir=-1 if ((ph = p.hash) > h) dir = -1; // 如果父节点hash小于当前节点的hash，dir=1 else if (ph < h) dir = 1; // kc = comparableClassFor(k)) == null)：kc的类型==null // dir = compareComparables(kc, k, pk)) == 0:比较kc的类型，当前key，父节点key是否相等 else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) // 比较k和pk的内存地址（0,-1,1） dir = tieBreakOrder(k, pk); // 如果左右节点为空的时候，设置子节点，结束循环 HashMap.TreeNode<K, V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; root = balanceInsertion(root, x); break; } } } } moveRootToFront(tab, root); }