Entry中的hash属性为什么不直接使用key的hashCode()返回值呢?
不管是JDK1.7还是JDK1.8中,都不是直接用key的hashCode值直接与table.length-1计算求下标的,而是先对key的hashCode值进行了一个运算,JDK1.7和JDK1.8关于hash()的实现代码不一样,但是不管怎么样都是为了提高hash code值与 (table.length-1)的按位与完的结果,尽量的均匀分布。
JDK1.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);}
JDK1.8:
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
虽然算法不同,但是思路都是将hashCode值的高位二进制与低位二进制值进行了异或,然高位二进制参与到index的计算中。
为什么要hashCode值的二进制的高位参与到index计算呢?
因为一个HashMap的table数组一般不会特别大,至少在不断扩容之前,那么table.length-1的大部分高位都是0,直接用hashCode和table.length-1进行&运算的话,就会导致总是只有最低的几位是有效的,那么就算你的hashCode()实现的再好也难以避免发生碰撞,这时让高位参与进来的意义就体现出来了。它对hashcode的低位添加了随机性并且混合了高位的部分特征,显著减少了碰撞冲突的发生。
HashMap是如何决定某个key-value存在哪个桶的呢?
因为hash值是一个整数,而数组的长度也是一个整数,有两种思路:
①hash 值 % table.length会得到一个[0,table.length-1]范围的值,正好是下标范围,但是用%运算效率没有位运算符&高。
②hash 值 & (table.length-1),任何数 & (table.length-1)的结果也一定在[0, table.length-1]范围。
JDK1.7:
static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";return h & (length-1); //此处h就是hash
}
JDK1.8:
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) // i = (n - 1) & hashtab[i] = newNode(hash, key, value, null);//....省略大量代码
}
为什么要保持table数组一直是2的n次幂呢?
因为如果数组的长度为2的n次幂,那么table.length-1的二进制就是一个高位全是0,低位全是1的数字,这样才能保证每一个下标位置都有机会被用到。
举例1:
hashCode值是 ?
table.length是10
table.length-1是9? ????????
9 00001001
&_____________00000000 [0]00000001 [1]00001000 [8]00001001 [9]一定[0]~[9]
举例2:
hashCode值是 ?
table.length是16
table.length-1是15? ????????
15 00001111
&_____________00000000 [0]00000001 [1]00000010 [2]00000011 [3]...00001111 [15]范围是[0,15],一定在[0,table.length-1]范围内
解决[index]冲突问题
虽然从设计hashCode()到上面HashMap的hash()函数,都尽量减少冲突,但是仍然存在两个不同的对象返回的hashCode值相同,或者hashCode值就算不同,通过hash()函数计算后,得到的index也会存在大量的相同,因此key分布完全均匀的情况是不存在的。那么发生碰撞冲突时怎么办?
JDK1.8之间使用:数组+链表的结构。
JDK1.8之后使用:数组+链表/红黑树的结构。
即hash相同或hash&(table.lengt-1)的值相同,那么就存入同一个“桶”table[index]中,使用链表或红黑树连接起来。
为什么JDK1.8会出现红黑树和链表共存呢?
因为当冲突比较严重时,table[index]下面的链表就会很长,那么会导致查找效率大大降低,而如果此时选用二叉树可以大大提高查询效率。
但是二叉树的结构又过于复杂,占用内存也较多,如果结点个数比较少的时候,那么选择链表反而更简单。所以会出现红黑树和链表共存。
加载因子的值大小有什么关系?
如果太大,threshold就会很大,那么如果冲突比较严重的话,就会导致table[index]下面的结点个数很多,影响效率。
如果太小,threshold就会很小,那么数组扩容的频率就会提高,数组的使用率也会降低,那么会造成空间的浪费。
什么时候树化?什么时候反树化?
static final int TREEIFY_THRESHOLD = 8;//树化阈值
static final int UNTREEIFY_THRESHOLD = 6;//反树化阈值
static final int MIN_TREEIFY_CAPACITY = 64;//最小树化容量
-
当某table[index]下的链表的结点个数达到8,并且table.length>=64,那么如果新Entry对象还添加到该table[index]中,那么就会将table[index]的链表进行树化。
-
当某table[index]下的红黑树结点个数少于6个,此时,
- 当继续删除table[index]下的树结点,最后这个根结点的左右结点有null,或根结点的左结点的左结点为null,会反树化
- 当重新添加新的映射关系到map中,导致了map重新扩容了,这个时候如果table[index]下面还是小于等于6的个数,那么会反树化
package com.atguigu.map;public class MyKey{int num;public MyKey(int num) {super();this.num = num;}@Overridepublic int hashCode() {if(num<=20){return 1;}else{final int prime = 31;int result = 1;result = prime * result + num;return result;}}@Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;MyKey other = (MyKey) obj;if (num != other.num)return false;return true;}}
package com.atguigu.map;import org.junit.Test;import java.util.HashMap;public class TestHashMapMyKey {@Testpublic void test1(){//这里为了演示的效果,我们造一个特殊的类,这个类的hashCode()方法返回固定值1//因为这样就可以造成冲突问题,使得它们都存到table[1]中HashMap<MyKey, String> map = new HashMap<>();for (int i = 1; i <= 11; i++) {map.put(new MyKey(i), "value"+i);//树化演示}}@Testpublic void test2(){HashMap<MyKey, String> map = new HashMap<>();for (int i = 1; i <= 11; i++) {map.put(new MyKey(i), "value"+i);}for (int i = 1; i <=11; i++) {map.remove(new MyKey(i));//反树化演示}}@Testpublic void test3(){HashMap<MyKey, String> map = new HashMap<>();for (int i = 1; i <= 11; i++) {map.put(new MyKey(i), "value"+i);}for (int i = 1; i <=5; i++) {map.remove(new MyKey(i));}//table[1]下剩余6个结点for (int i = 21; i <= 100; i++) {map.put(new MyKey(i), "value"+i);//添加到扩容时,反树化}}
}
key-value中的key是否可以修改?
key-value存储到HashMap中会存储key的hash值,这样就不用在每次查找时重新计算每一个Entry或Node(TreeNode)的hash值了,因此如果已经put到Map中的key-value,再修改key的属性,而这个属性又参与hashcode值的计算,那么会导致匹配不上。 HUANGANHE
这个规则也同样适用于LinkedHashMap、HashSet、LinkedHashSet、Hashtable等所有散列存储结构的集合。
JDK1.7中HashMap的循环链表是怎么回事?如何解决?
避免HashMap发生死循环的常用解决方案:
- 多线程环境下,使用线程安全的ConcurrentHashMap替代HashMap,推荐
- 多线程环境下,使用synchronized或Lock加锁,但会影响性能,不推荐
- 多线程环境下,使用线程安全的Hashtable替代,性能低,不推荐
HashMap死循环只会发生在JDK1.7版本中,主要原因:头插法+链表+多线程并发+扩容。
在JDK1.8中,HashMap改用尾插法,解决了链表死循环的问题。
补:
- JDK7当插入数据达到容量*负载因子时,会对底层数组进行扩容,然后再通过头插法进行数据插入,在多线程的情况下,会出现循环链表的情况;
- JDK8则是在通过尾插法进行数据插入之后,再对底层数组进行扩容,在多线程的情况下,也能避免链表死循环的问题。