转载声明：文章链接：https://blog.csdn.net/xing123456jl/article/details/108044431
一、区别
1. 最重要的一点是底层结构不一样，1.7是数组+链表，1.8则是数组+链表+红黑树结构;
2. jdk1.7中当哈希表为空时，会先调用inflateTable()初始化一个数组；而1.8则是直接调用resize()扩容;
3. 插入键值对的put方法的区别，1.8中会将节点插入到链表尾部，而1.7中是采用头插；
4. jdk1.7中的hash函数对哈希值的计算直接使用key的hashCode值，而1.8中则是采用key的hashCode异或上key的hashCode进行无符号右移16位的结果，避免了只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，使元素分布更均匀；
5. 扩容时1.8会保持原链表的顺序，而1.7会颠倒链表的顺序；而且1.8是在元素插入后检测是否需要扩容，1.7则是在元素插入前；
6. jdk1.8是扩容时通过hash&cap==0将链表分散，无需改变hash值，而1.7是通过更新hashSeed来修改hash值达到分散的目的；
7. 扩容策略：1.7中是只要不小于阈值就直接扩容2倍；而1.8的扩容策略会更优化，当数组容量未达到64时，以2倍进行扩容，超过64之后若桶中元素个数不小于7就将链表转换为红黑树，但如果红黑树中的元素个数小于6就会还原为链表，当红黑树中元素不小于32的时候才会再次扩容。
二、JDK1.8 HashMap源码解读
1.桶的树形化 treeifyBin()
(1)根据哈希表容量以及元素个数确定是扩容还是树形化；
(2)如果是树形化则遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系；
(3)让桶第一个元素指向新建的树头结点，替换桶的链表内容为树形内容；
//将桶内所有的 链表节点 替换成 红黑树节点
1 final void treeifyBin(Node<K,V>[] tab, int hash) {
2 int n, index; Node<K,V> e;
3 //如果当前哈希表为空，或者哈希表中元素的个数小于 进行树形化的阈值(默认为 64)，就去新建/扩容
4 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
5 resize();
6 else if ((e = tab[index = (n - 1) & hash]) != null) {
7 //如果哈希表中的元素个数超过了 树形化阈值，进行树形化
8 // e 是哈希表中指定位置桶里的链表节点，从第一个开始
9 TreeNode<K,V> hd = null, tl = null; //红黑树的头、尾节点
10 do {
11 //新建一个树形节点，内容和当前链表节点 e 一致
12 TreeNode<K,V> p = replacementTreeNode(e, null);
13 if (tl == null) //确定树头节点
14 hd = p;
15 else {
16 p.prev = tl;
17 tl.next = p;
18 }
19 tl = p;
20 } while ((e = e.next) != null);
21 //让桶的第一个元素指向新建的红黑树头结点，以后这个桶里的元素就是红黑树而不是链表了
22 if ((tab[index] = hd) != null)
23 hd.treeify(tab);
24 }
25 }
26 TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
27 return new TreeNode<>(p.hash, p.key, p.value, next);
28 }2.put()
①.判断键值对数组table[i]是否为空，否则执行resize()扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否不小于7，不小于7就把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量是否超过阈值，如果超过了就进行扩容；
1 public V put(K key, V value) {
2 // 对key的hashCode()做hash
3 return putVal(hash(key), key, value, false, true);
4 }
5
6 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
7 boolean evict) {
8 Node<K,V>[] tab; Node<K,V> p; int n, i;
9 // 步骤①：tab为空则创建
10 if ((tab = table) == null || (n = tab.length) == 0)
11 n = (tab = resize()).length;
12 // 步骤②：计算index，并对null做处理
13 if ((p = tab[i = (n - 1) & hash]) == null)
14 tab[i] = newNode(hash, key, value, null);
15 else {
16 Node<K,V> e; K k;
17 // 步骤③：节点key存在，直接覆盖value
18 if (p.hash == hash &&
19 ((k = p.key) == key || (key != null && key.equals(k))))
20 e = p;
21 // 步骤④：判断该链为红黑树
22 else if (p instanceof TreeNode)
23 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
24 // 步骤⑤：该链为链表
25 else {
26 for (int binCount = 0; ; ++binCount) {
27 if ((e = p.next) == null) {
28 p.next = newNode(hash, key,value,null);
//链表长度大于8转换为红黑树进行处理
29 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
30 treeifyBin(tab, hash);
31 break;
32 }
// key已经存在直接覆盖value
33 if (e.hash == hash &&
34 ((k = e.key) == key || (key != null && key.equals(k))))
35 break;
36 p = e;
37 }
38 }
39
40 if (e != null) { // existing mapping for key
41 V oldValue = e.value;
42 if (!onlyIfAbsent || oldValue == null)
43 e.value = value;
44 afterNodeAccess(e);
45 return oldValue;
46 }
47 }
48 ++modCount;
49 // 步骤⑥：超过最大容量就扩容
50 if (++size > threshold)
51 resize();
52 afterNodeInsertion(evict);
53 return null;
54 }3.红黑树中查找元素 getTreeNode()
(1) HashMap的查找方法是get(),它通过计算指定key的哈希值后，调用内部方法 getNode()；
(2) getNode()方法中根据哈希表元素个数与哈希值计算出对应索引位置，找到key所在的桶的头结点，如果头节点恰好是红黑树节点，就调用红黑树节点的getTreeNode()方法，否则就遍历链表节点；
(3) getTreeNode()方法通过调用红黑树的find()方法进行查找即可；
(4) 由于之前添加时已经保证整个树是有序的，因此查找时基本就是折半查找，效率很高；
1 final Node<K,V> getNode(int hash, Object key) {
2 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
3 if ((tab = table) != null && (n = tab.length) > 0 &&
4 (first = tab[(n - 1) & hash]) != null) {
5 if (first.hash == hash && // always check first node
6 ((k = first.key) == key || (key != null && key.equals(k))))
7 return first;
8 if ((e = first.next) != null) {
9 if (first instanceof TreeNode)
10 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
11 do {
12 if (e.hash == hash &&
13 ((k = e.key) == key || (key != null && key.equals(k))))
14 return e;
15 } while ((e = e.next) != null);
16 }
17 }
18 return null;
19 }
20
21 final TreeNode<K,V> getTreeNode(int h, Object k) {
22 return ((parent != null) ? root() : this).find(h, k, null);
23 }
适合初学者