HashMap对应1.7、1.8版本的区别
- 首先说一下HashMap
-
- JDK1.7链表用的是头插法、JDK1.8用的是尾插法
- HashMap的扩容方式在1.7与1.8中也存在差异
- 扩容后数据存储位置的计算方式也不一
首先说一下HashMap
JDK1.7链表用的是头插法、JDK1.8用的是尾插法
为什么要改变链表的插入方式，在1.7的时候采用的是链表的方式存储的相同hash值的元素，采用头插法速度相对较快（链表的存储空间与数组不同链表的存储空间是不连续的，需要先找到头节点在根据nextnode指向的地址找到下一个节点，尾插法相对较慢需要一个个节点去遍历直到找到尾节点将将尾节点的nextnode指向新插入的节点才能完成插入，而头插法只需找到头节点，将新插入的节点作为头节点nextnode指向原来的头节点即可完成节点的插入省去了遍历链表的时间），但是头插法会出现逆序且环形链表死循环问题 （这块后补），在JDK1.8之后加入了红黑树所以采用了尾插法避免了出现逆序且环形链表死循环问题
HashMap的扩容方式在1.7与1.8中也存在差异
在JDK1.7中的扩容方式是这样的
首先是put方法源码
//put方法源码
public V put(K key, V value) {
//数组为空就进行初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//key 进行哈希计算
int hash = hash(key);
//获取数组下标
int i = indexFor(hash, table.length);
//如果此下标有值，遍历链表上的元素，key 一致的话就替换 value 的值
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//新增一个key
addEntry(hash, key, value, i);
return null;
}
put方法调用了addEntry方法，看一下addEntry方法的源码
void addEntry(int hash, K key, V value, int bucketIndex) {
//1、判断当前个数是否大于等于阈值
//2、当前存放是否发生哈希碰撞
//如果上面两个条件否发生，那么就扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容，并且把原来数组中的元素重新放到新数组中
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
createEntry方法的源码
void createEntry(int hash, K key, V value, int bucketIndex) {
//此位置有元素，就在链表头部插入新元素（头插法）
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
扩容方法的源码
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];
// transfer()方法把原数组中的值放到新数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//设置hashmap扩容后为新的数组引用
table = newTable;
//设置hashmap扩容新的阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
transfer()在实际扩容时候把原来数组中的元素放入新的数组中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//通过key值的hash值和新数组的大小算出在当前数组中的存放位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
三、总结：
Hashmap的扩容需要满足两个条件：当前数据存储的数量（即size()）大小必须大于等于阈值；当前加入的数据是否发生了hash冲突。
因为上面这两个条件，所以存在下面这些情况
（1）、就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。
（2）、当然也有可能存储更多值（超多16个值，最多可以存26个值）都还没有扩容。原理：前11个值全部hash碰撞，存到数组的同一个位置（这时元素个数小于阈值12，不会扩容），后面所有存入的15个值全部分散到数组剩下的15个位置（这时元素个数大于等于阈值，但是每次存入的元素并没有发生hash碰撞，所以不会扩容），前面11+15=26，所以在存入第27个值的时候才同时满足上面两个条件，这时候才会发生扩容现象。
在JDK1.8中的扩容方式
看一下put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//数组为空就初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//当前下标为空，就直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//key 相同就覆盖原来的值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//树节点插入数据
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)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);
//链表长度超过8，就把链表转为红黑树
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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//数组长度大于阈值，就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
继续看下 treeifyBin 的源码
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//链表转为红黑树时，若此时数组长度小于64，扩容数组
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
//链表转为树结构
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
由此可以看到1.8中，数组有两种情况会发生扩容，一种是超过阈值，一种是链表转为红黑树且数组元素小于64时，由此在jdk1.8中，默认长度为16情况下，要么元素一直放在同一下标，数组长度为9时就会扩容，要么超过阈值12时才会扩容。
通过上面的分析，我们可以看到jdk1.7和1.8情况下 hashmap实现方式的主要区别
- 出现哈希冲突时，1.7把数据存放在链表，1.8是先放在链表，链表长度超过8就转成红黑树
- 1.7扩容条件是数组长度大于阈值且存在哈希冲突，1.8扩容条件是数组长度大于阈值或链表转为红黑树且数组元素小于64时
扩容后数据存储位置的计算方式也不一
1、在JDK1.7的时候是直接用hash值和需要扩容的二进制数进行&运算（这里就是为什么扩容的时候为啥一定必须是2的多少次幂的原因所在，因为如果只有2的n次幂的情况时最后一位二进制数才一定是1，这样能最大程度减少hash碰撞，为什么说能最大程度的减少hash碰撞，假设扩容不是2的n次幂的情况扩容值是15的时候，则length-1为14，14的二进制值为1110，在实现key的定位的时候（hash值&length-1），我们可以发现0001、0011、1001、1011、0111、1101这几个位置永远不可能存在值，这样就浪费了存储空间，同时也就降低了在相同容量时的位置可选择性，就是增加了hash冲突的几率，所以为2的n次幂的时候减少了hash冲突提高了hashmap的查找速率）
2、而在JDK1.8的时候直接用了JDK1.7的时候计算的规律，也就是扩容前的原始位置+扩容的大小值=JDK1.8的计算方式，而不再是JDK1.7的那种异或的方法。但是这种方式就相当于只需要判断Hash值的新增参与运算的位是0还是1就直接迅速计算出了扩容后的储存方式。如下图所示
未完待续
参考链接：
https://blog.csdn.net/qq_36520235/article/details/82417949
![Java String.format方法的简单使用[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)