hashmap|JDK 经典操作之 HashMap 7、8 之间的差别数据结构|java

大家好，相信大家平时学习生活中HashMap肯定用的不少，反正在面试中你熟读其源码，了解其原理，知道其什么地方不合理，会导致什么样的问题
今天带大家看一看JDK1.7和JDK1.8的HashMap的源码
他们两个的差别随便抓一个还在上幼儿园的小盆友都说的头头是道
小朋友奶里奶气的说：1.7是数组+链表，1.8优化成了数组+链表（红黑树）
真的就这吗？
我们来看看其源码（每段源码前我用自己的话进行了一番描述，可能有点丑看不懂，就直接看源码吧，关键地方我也进行了注释）
先看1.7的
【hashmap|JDK 经典操作之 HashMap 7、8 之间的差别】属性：

/** 构造函数没传初始化容量就使用该默认容量 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/** 最大容量,构造函数传的初始容量也不能大于这个 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** 默认负载因子*/ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** table未初始化时的table实例 */ static final Entry[] EMPTY_TABLE = { }; /** 维护的一个table,根据需要调整大小,长度必须为2的幂*/ transient Entry[] table = (Entry[]) EMPTY_TABLE/** entry的数量*/ transient int size; /** 阈值,下一个需要调整大小的值,loadFactor * capacity */ // 当table未初始化时,这个就是initial capacity int threshold; /** 负载因子 */ final float loadFactor; /** hash值生成种子,目的是减少hash冲突*/ transient int hashSeed = 0;

put()方法会先判断当前table是否需要初始化
然后会判断待添加的key是否为null
接着会计算出当前key的hash，根据算出的hash值和当前table的长度算出应该存放在index为多少的bucket（bucket可以看作是指定下标的数组）里面
会去遍历该bucket，判断是否有key相同的（判断依据是先判断hash值，再判断地址值或者值是否相等）
有则覆盖之前的值，无则新增一个entry

public V put(K key, V value) {// 假如当前table为空的,根据threshold(initialCapacity)扩容 if (table == EMPTY_TABLE) {inflateTable(threshold); } if (key == null) // 当key为null时的put方法 return putForNullKey(value); int hash = hash(key); // 根据hash值和当前table的长度计算应该放在下标为多少的bucket里面 int i = indexFor(hash, table.length); // 这里去遍历指定下标的bucket,看key为当前key的entry有没有 for (Entry e = table[i]; e != null; e = e.next) {Object k; // 先判断hash值,再判断key是否==或者equals if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = https://www.it610.com/article/e.value; e.value = value; e.recordAccess(this); return oldValue; } }modCount++; // key相等的entry没有 addEntry(hash, key, value, i); return null; }

初始化table方法：
会将initialCapacity向上取整为2的幂作为当前的capacity，并更新当前threshold为capacity * loadFactor
还会初始化hashcode生成种子（注意，这个什么hash种子只存在于1.7，1.8就无了）

private void inflateTable(int toSize) {// toSize向上取整为2的幂 int capacity = roundUpToPowerOf2(toSize); // 更新当前阈值 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; // 懒加载hashcode种子 initHashSeedAsNeeded(capacity); }

当key为null时的put方法：
HashMap默认将key为null的放在index为0的bucket里面，所以这里会去遍历index为0的bucket里面是否有key为null的entry
有则替换，无则新增一个entry

private V putForNullKey(V value) {// key为null时,默认将entry放在index为0的bucket里面 // 这里会去遍历index为0的链表,如果找到key为null的会替换 for (Entry e = table[0]; e != null; e = e.next) {if (e.key == null) {V oldValue = https://www.it610.com/article/e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; // 没找到这里会新增一个key为null的entry addEntry(0, null, value, 0); return null; }

进行新增entry的一些前置工作：
这里涉及到一些扩容操作
如果当前size大于等于threshold并且指定index的bucket不为null时（也就是将要放入的bucket里一个元素都没有，不会进行扩容）
将bucket的长度扩大为现在的两倍，并将hash值和index值重新计算

void addEntry(int hash, K key, V value, int bucketIndex) {// 替换是不涉及扩容的,这里新增才会涉及 if ((size >= threshold) && (null != table[bucketIndex])) {// bucket长度扩大为现在的两倍 resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); }createEntry(hash, key, value, bucketIndex); }

扩容：
扩容方法，先对旧table进行容量判断，如果旧的容量已经最大了，那么不能再大了，直接不扩容
否则会生成一个新的table，将旧table里的entry全部转放到新的table里面，会重新生成hashcode种子，并判断是否需要重新hash
threshold设置为newCapacity * loadFactor

void resize(int newCapacity) {// 检查当前长度越界没有 Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE; return; }Entry[] newTable = new Entry[newCapacity]; // 重新生成hash种子会判断是否需要重新hash,再将现有的entry转移到new table里面 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }

将扩容后的entry从旧table 转移到 new table里面：
遍历每一个bucket，再遍历每一个bucket的链表，如果需要hash会重新hash，并重新计算该放入的bucket的index
注意：这里的操作会使链表反转（记住，要考的）

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length; for (Entry e : table) {// e是每一个bucket while(null != e) {Entry next = e.next; // 需要重新hash就会重新hash if (rehash) {e.hash = null == e.key ? 0 : hash(e.key); } // 重新计算bucket的下标 int i = indexFor(e.hash, newCapacity); // 经典将链表反转 e.next = newTable[i]; newTable[i] = e; e = next; } } }

真 - 添加entry方法：没什么好说的，只有一个头插法比较6（要考哦）

void createEntry(int hash, K key, V value, int bucketIndex) {Entry e = table[bucketIndex]; // 也是经典头插法 table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }

get()会先判断需要查找的key是否为null，感觉get()没什么好说的，相比put()来说简直太清爽，随便看一看就好

public V get(Object key) {if (key == null) return getForNullKey(); Entry entry = getEntry(key); return null == entry ? null : entry.getValue(); }

获取key为null的value的方法：

private V getForNullKey() {// 如果当前size为0,直接返回null if (size == 0) {return null; } // key为null会将其放在index为0的bucket里面 for (Entry e = table[0]; e != null; e = e.next) {if (e.key == null) return e.value; } return null; }

获取指定key的方法：

final Entry getEntry(Object key) {if (size == 0) {return null; } // 计算带查找key的hash值 int hash = (key == null) ? 0 : hash(key); // 根据当前table的长度和hash值计算bucket的index,并遍历 for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {Object k; // 判断依据还是和添加时一样的,先判断hash,再判断地址值或者值 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }

线程安全问题：在扩容时采用头插法，头插法会使元素顺序倒转，多线程情况（两个线程同时扩容，一个线程先扩容完成，另一个线程看到的链表就是被倒转的）下会产生环形链表导致死循环以及数据丢失的问题
看完清爽的1.7，接下来看1.8（不得不说，就算1.8优化的再6，思想再6，1.8的代码写的是真的臭，比1.7清爽的代码不知道差到天上去，自己写时爽，读时火葬场）
1.8的HashMap：
因为1.7在发生严重hash冲突时整个Map会退化成链表，导致效率会很低，1.8做了一些优化
1.8将内部的Entry改为Node（这个操作谁给我解释一下），除此之外好像没什么毛区别
1.8的属性与1.7相比基本变，只是新增了几个属性，还有就是没有了EMPTY_TABLE这个属性

/** list->tree的阈值,必须大于2且至少为8?*/ static final int TREEIFY_THRESHOLD = 8; /** tree->list的阈值,最多为6,*/ static final int UNTREEIFY_THRESHOLD = 6; /** 树化的最小容量至少为4 * TREEIFY_THRESHOLD*/ static final int MIN_TREEIFY_CAPACITY = 64;

1.8的hash()方法相比1.7的更简单了，1.7还有什么hash种子，1.8已经没有了
1.7的：

final int hash(Object k) {int h = hashSeed; if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k); }h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }

1.8的：

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

原因可能（我也不知道，猜的，抓作者过来问一问就知道了）是因为在1.7的时候，应该要尽量避免hash冲突，否则会导致整个表退化成为一个链表，而1.8引进了红黑树，相对而言，比1.7不那么怕了，所以整个hash值的运算变简单了
put()：put()方法就是一个玩具，下面才是正题

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

putVal()：
onlyIfAbsent如果为true的话，表示不覆盖key已经存在的值，evict为false，表示当前table处于创建模式
putVal()会先判断当前table是否需要初始化
接着会判断待插入节点应放在table的位置是否为null（也就是待插入节点应放在的数组位置，现在是不是为null），为null就直接放入了不需要后面的操作
不为null的话接着判断数组（链表）的第一个元素的key和待插入元素的key相同不，判断依据是hash值是否相同，以及内存地址或者值是否相同（与1.7好像无异）
不相同会判断是否为treeNode，假如是，会依据treeNode的方式去添加元素
以上都不成立，会遍历当前链表，找到最后一个空位置将其插入，或者是找到链表上是否有key相同的节点
假如找到了最后一个空位置会判断是否需要树化
之前找到的相同key的位置会放到现在来覆盖，最后会判断是否需要扩容

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node[] tab; Node p; int n, i; // 如果当前table还未初始化(为null或者长度为0) if ((tab = table) == null || (n = tab.length) == 0) // 初始化当前table n = (tab = resize()).length; // 当前数组元素是否为null // 这里顺便确定了一下当前entry应该放在index为多少的数组里面 if ((p = tab[i = (n - 1) & hash]) == null) // 为null直接新增一个node(list)放在链表头(也就是数组位置) tab[i] = newNode(hash, key, value, null); else {Node e; K k; // p是当前数组的元素(也就是链表的第一个元素) // 判断当前元素与待插入元素的key是否相同 // 依据是hash值是否相同,以及内存地址或者值是否相同 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) // 这里是tree版的putVal() e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else {for (int binCount = 0; ; ++binCount) {// 这里在遍历链表 if ((e = p.next) == null) {// 找到最后一个节点插入 p.next = newNode(hash, key, value, null); // 当前链表长度大于等于树化阈值就会树化 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 找到了key相同的节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // 迭代链表节点 p = e; } }// e不为null说明找到了key相同的节点 if (e != null) { // existing mapping for key V oldValue = https://www.it610.com/article/e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; // afterNodeAccess()是空实现,为LinkedHashMap准备的 afterNodeAccess(e); return oldValue; } } ++modCount; // 添加完新节点后size大于阈值需要resize if (++size> threshold) resize(); // afterNodeInsertion(),这个也是空实现,同上 afterNodeInsertion(evict); return null; }

resize()：
首先会判断当前容量是否大于0，大于0说明是扩容，则只要不超过最大容量的情况下将容量和阈值分别扩大两倍即可
如果不为扩容，会判断是否当前阈值大于0，当前阈值大于0说明从构造函数里面传入了初始容量，只是用阈值这个值来暂放一下，会把新容量设置为当前阈值
都不是（既不是扩容，构造函数也没传入初始容量），使用默认容量，配合默认负载因子确定阈值（其实也是默认的）
接着判断如果新容量是当前阈值，将当前阈值更新（根据老公式）
以上是确定新容量和新阈值，下面是将旧table里的元素放入新table，对应1.7里的transfer()
如果旧table不为null，说明是扩容，会去遍历没每一个数组元素，再遍历每一条链表（或许不为链表）
假如这个链表只有一个元素，直接计算其在新table里面的下标放入即可
如果是treeNode，则按照treeNode的方式转移
如果都不是，就会遍历当前链表，依据e.hash & oldCap是否为0，将原链表hash为高低位两个链表
低位的链表保留在与old table同一index的位置，高位的链表放在old table的index + old容量的位置，且这里与1.7不同点在于，注释里面都写了preserve order（保留顺序）

final Node[] resize() {Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 大于0说明是扩容 if (oldCap > 0) {// 不能扩大到MAXIMUM_CAPACITY之外 if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE; return oldTab; } // 将新容量新阈值扩大为两倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } // 初始化容量为0,阈值不为0,则初始化容量就为当前阈值 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // 使用的是空构造 else { // zero initial threshold signifies using defaults // 默认容量1 << 4 aka 16 newCap = DEFAULT_INITIAL_CAPACITY; // 默认阈值 0.75 * 16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); }// new阈值为0表示初始化容量使用了当前阈值 if (newThr == 0) {// 更新一下当前阈值,实则是缩小了 float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; // 创建一个新的table Node[] newTab = (Node[])new Node[newCap]; table = newTab; // 下面要将old table的entry转移到new table,相当于1.7的transfer() if (oldTab != null) {// 遍历每一个数组元素 for (int j = 0; j < oldCap; ++j) {Node e; if ((e = oldTab[j]) != null) {// 虽然他没写,我帮他写一个help GC oldTab[j] = null; // 这个链表只有一个元素 if (e.next == null) // 计算出新table的index并放入 newTab[e.hash & (newCap - 1)] = e; // 树节点的放入 else if (e instanceof TreeNode) // 这里也是将树拆分为高位和低位,如果树太小就变为list ((TreeNode)e).split(this, newTab, j, oldCap); // 不同于1.7,这里要保留当前顺序 else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do {next = e.next; // 这里根据e.hash & oldCap是否为0,将原链表hash为高低位两个链表 if ((e.hash & oldCap) == 0) {if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else {if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 低位的链表保留在与old table同一index的位置 if (loTail != null) {loTail.next = null; newTab[j] = loHead; } // 高位的链表放在old table的index + old容量的位置 if (hiTail != null) {hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

get()：get()方法好像还是继承了HashMap的老传统，没什么好说的

public V get(Object key) {Node e; return (e = getNode(hash(key), key)) == null ? null : e.value; }

getNode()：
首先会判断table是否为空，以及当前key对应的数组元素是否为null
不为null的话会检查第一个元素是否是要查找的元素，
如果第一个不是且有next元素的话，会遍历查找
treeNode按照tree的方式，链表按照链表的方式

final Node getNode(int hash, Object key) {Node[] tab; Node first, e; int n; K k; // table不为null且table的长度不为0且key对应的数组元素不为null if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {// 检查第一个元素是否是要找的元素 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 第一个不是且有next元素会遍历的找 if ((e = first.next) != null) {// 是treeNode会按照treeNode方式获取 if (first instanceof TreeNode) return ((TreeNode)first).getTreeNode(hash, key); // 遍历链表 do {if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }

线程安全问题：jdk1.8采用尾插法，解决了1.7存在的问题
又出现了新的问题：
1、多线程并发插入数据时，resize调用split()拆分树，接着会调用untreeify()将当前treeNode转为listNode，故原有的treeNode会被gc，但是并没有，会出现OOM
2、put时会覆盖掉一些值，导致数据丢失
3、多线程情况下，size()值也不准确
总结：1.8结构、思想、实现比1.7 6，代码写的是真臭，比如说下面这段代码