【硬核】HashMap最全⾯试题（附答案）
⽂章⽬录
hashmap基础
hashmap的node
hashmap类有⼀个⾮常重要的属性Node<K,V> 是hashmap的⼀个内部类，实现Entry接⼝，本质上是⼀个映射
可以看到，Node类的基本属性有：
hash：key的哈希值
key：节点的key，类型和定义HashMap时的key相同李真案
value：节点的value，类型和定义HashMap时的value相同
next：该节点的下⼀节点
值得注意的是其中的next属性，记录的是下⼀个节点本⾝，也是⼀个Node节点，这个Node节点也有next属性，记录了下⼀个节点，于是，只要不断的调⽤ext……，就可以得到：
Node–>下个Node–>下下个Node……–>null
这样的⼀个链表结构，⽽对于⼀个HashMap来说，只要明确记录每个链表的第⼀个节点，就能顺序遍历链表上的所有节点。hashmap的容量 HashMap的容量，默认是16
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY =1<<4;// aka 16
HashMap的加载因⼦，默认是0.75
hashmap的负载因⼦
HashMap的加载因⼦，默认是0.75
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR =0.75f;
当HashMap中元素数超过容量*加载因⼦时，HashMap会进⾏扩容。
所以要注意，如果要往HashMap中放1000个元素，⼜不想让HashMap不停的扩容，最好⼀开始就把容量设为2048，设为1024不⾏，因为元素添加到七百多的时候还是会扩容。
hashmap的hash()算法
HashMap⾥⾯的hash()返回值
问题：HashMap⾥⾯的hash()返回值为什么不是key.hashCode()的返回值，⽽是key.hashCode() ^ (key.hashCode() >>> 16)的返回值呢？
源码：
static final int hash(Object key){
int h;
return(key ==null)?0:(h = key.hashCode())^(h >>>16);
}
这样做的⽬的是为了减少hash的冲突概率。
hashmap再put()的时候，hash冲突是不可避免的，所以如何尽量避免hash冲突，或者在hash冲突时如何⾼效定位到数据的真实存储位置就是HashMap中最核⼼的部分。 higgs粒子
key.hashCode() ^ (key.hashCode() >>> 16)的逻辑就是先获得key的hashCode的值 h，然后 h 和 h右移16位 做异或运算。实质上就是把⼀个数的低16位与他的⾼16位做异或运算如果不这样的话，那么就只有hash()返回值的末x位参与到运算，这样就会造成hash冲突的概率⾼⼀些。如果先把key的hashCode()返回值的⾼16位和低16位进⾏异或运算，这样⾼16位也参与到hash()的运算逻辑了，这样就能减少冲突。
实例讲解
⽐如有两个key的hashCode()⽅法返回值分别如下
key1.hashCode():
1111 1111 1111 1111 0101 0101 0111 0101
key2.hashCode():
1111 1111 1110 1111 0101 0101 0111 0101
如果没有^ (h >>> 16)，那么15 & hash就分别是
11111111111111110101010101110101
00000000000000000000000000001111
key2在底层的数组索引值是：5
11111111111011110101010101110101
00000000000000000000000000001111
这是因为key1.hashCode()和key2.hashCode()的低16位完全相同，然后15 & hash的时候，15的⼆进制0000 0000 0000 0000 0000 0000 0000 1111的⾼位⼏乎都是0，这就造成15 & hash的时候，只有hash的低16位起了作⽤，⽽key1.hashCode()和key2.hashCode()的低16位完全相同，所以底层索引值也就相同了，这样很容易造成hash冲突。 但是如果有^ (h >>> 16)
就⽐如key.hashCode的值，也就是h变量如下所⽰：
1111 1111 1110 1111 0101 0101 0111 0101
然后呢，h ^ (h >>> 16)就是：
1111 1111 1110 1111 0101 0101 0111 0101
^
0000 0000 0000 0000 1111 1111 1110 1111
计算结果是：这⾥可以看出来，最终的结果值(叫他finalHash)和key.hashCode()值(叫他hash)⽐较就是finalHash的⾼16位没有
变，finalHash的低16位是hash的⾼16位和低16位^运算的结果。这样做的好处就是finalHash的低16位具有了hash的低16位和⾼16位的都有的特征，这样就减少了hash冲突的概率
1111 1111 1110 1111 1010 1010 1001 1010
hashmap的数组+链表/树问题
hashmap为什么引⼊链表
hashmap的底层是数组，当map进⾏put()操作时候，会进⾏hash计算，判定这个对象属于数组的那个位置。当多个对象的值再同⼀个数组位置上⾯的时候，就会有hash冲突。这个时候就引⼊了链表
为什么jdk1.8会引⼊红⿊树呢
当链表长度⼤于8时，遍历查效率较慢，故引⼊红⿊树
并不是只需要链表长度⼤于8，同时需要满⾜条件数组长度⼤于64的时候变成红⿊树
还有如果红⿊树的节点个数⼩于6的时候，红⿊树还会变成链表
hashmap为什么⼀开始不就使⽤红⿊树？
这是因为红⿊树相对于链表维护成本⼤，红⿊树在插⼊新数据之后，可能会通过左旋、右旋、变⾊来保持平衡，造成维护成本过⾼，故链路较短时，不适合⽤红⿊树。
HashMap的底层数组取值的时候，为什么不⽤取模，⽽是&
tab[i = (n - 1) & hash]
这是因为在计算机运算的时候，使⽤&⽐取模的性能更快。
数组的长度为什么是2的次幂
总共有三个好处：
为了减少hash冲突，就是为了让数据均匀分布。此时我们⼀般使⽤公式(hashCode%size），这样可以达到最⼤的平均分配。⽽(n - 1) & hash，当n为2次幂时，会满⾜⼀个公式：(n - 1) & hash = hash
% n
&运算速度快，⽐%取模运算块，根据计算，Java的%、/操作⽐&慢10倍左右
能保证 索引值 肯定在 capacity 中，不会超出数组长度
具体的想要了解看下⾯的知识点
hashMap的底层数据结构是数组+链表的结构，所以hashMap每次保存的数据都是分散保存在数组的各个index位置，⽽为了存取效率达到最⾼，要求hashMap每次保存的时候尽量平均分散到数组的各个位置，这样可以避免每次存取都要遍历链表造成额外的时间成本开销。
所以就通过hashMap对数组长度取余运算（hashCode%size），这样可以达到最⼤的平均分配；但是hashMap的作者想到了如果通过位运算来计算取余的话效率会⽐10进制的取余运算来的快，因为我们知道计算机的底层运算都是转化位⼆进制运算的；
所以为了位运算的取余效果能到10进制的效果，作者推算出了如果容量为2的N次⽅的话，那么hash&(length-1) ==
hash%length;length转为⼆进制位⼀个1+N个0，length-1转为⼆进制位⼀个0+N个1；则任意的hash值
和length-1做位运算，结构都是后⾯N个位的的⼆进制，因为length-1的⼆进制前⾯都是0，位运算后都是0，相当于舍弃了⾼位，保留了后⾯的N位，后⾯的N位刚好在0-length之间，也就是等于hash%length取余；具体推算过程：
假设hash值为20，hashMap的容量为length=16
⼗进制取余算法：20%16 = 4；所以任何的hash值得取余都在0-15之间，达到了最有可能得平均分配；
⼆进制算法：20转为⼆进制位10100，length-1=15 = 01111；所以⼆进制算法为10100 & 01111 = 0100 = 4，⾼位和length-1的0相与后全部舍弃，直接保留了hash值最后N位，⽽最后N位刚好就是⼗进制的取余运算的结果；任何hash值都是这样；
再⽐如随便的⼆进制的hash值位101010101010111，假设容量length依旧位2的4（N=4）次⽅16，所以length-1的hash值还是0111，101010101010111和0111相与后结果为0111，⼗进制为7，相当于⾼位全部被舍弃，实际上就是保留了hash值的低N位；读者可以将101010101010111转为10进制在对16取余，验证余数是否为7；就是验证公式：hash&(length-1) == hash%length；价值工程
假如不是按2的幂次⽅，随便假设为length = 15，hash= 17，则10进制取余运算为2，⼆进制位运算为
10001&01110 =0，不会等于10进制的的运算结果；⽽实际上length-1 = 14 = 01110和任何的hash相与，最后的⼀位的0都会被舍弃，所以任何的hash值和01110相与的结果都不会出现1101（13），1001（9）等数据，所以相当于table的数组中index =13或者9的位置永远不会保存到数据，造成空间浪费；所以就不能⽤位运算计算key对应的value的值，就要⽤10进制计算，速度就⽐不上⼆进制算法；
所以总结出：如果既要达到最可能的平均分配hashMap的value的在table的各个index，⼜要⽤⼆进制计算实现存取效率，就要要求hashMap的容量必须为2的幂次⽅；
所以如果不考虑性能问题，我们可以不设置数组的长度是2次幂倍数，此时也没有必要使⽤h & (length-1)，⽽是换成h % length。
如果指定数组的长度不为 2次幂，就破坏了数组的长度是2次幂的这个规则吗？
不会的，HashMap 的tableSizeFor⽅法做了处理，能保证n永远都是2次幂。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap){
//cap-1后，n的⼆进制最右⼀位肯定和cap的最右⼀位不同，即⼀个为0，⼀个为1，例如cap=17（00010001），n=cap-1=16（00010000）
int n = cap -1;诺顿磁盘医生怎么用
//n = (00010000 | 00001000) = 00011000
n |= n >>>1;
//n = (00011000 | 00000110) = 00011110
n |= n >>>2;
//n = (00011110 | 00000001) = 00011111
n |= n >>>4;
//n = (00011111 | 00000000) = 00011111
n |= n >>>8;
//n = (00011111 | 00000000) = 00011111
n |= n >>>16;
//n = 00011111 = 31
//n = 31 + 1 = 32, 即最终的cap = 32 = 2 的 (n=5)次⽅
return(n <0)?1:(n >= MAXIMUM_CAPACITY)? MAXIMUM_CAPACITY : n +1;
}
hashmap⾥⾯的源码
HashMap的put()
1.8的put()⽅法
1. 如果key对应的索引位置是null，那么直接插⼊
2. 数组⾥⾯key对应的索引值位置的值不为null，判断这个⽼值的key是否和新put的key是否相同，如果相同，就把⽼的值返回，并且记录这个位置
3. 数组⾥⾯key对应的索引值位置的值不为null，判断这个索引位置的值是不是树结构，如果是树结构，调⽤树结构putTreeVal⽅法添加数据
4. 数组⾥⾯key对应的索引值位置的值不为null，然后这个索引位置的值就是⼀个链表结构，然后遍历所有的链表(当遍历的长度⼤于8的时候，就会
转成树结构)，如果链表结构⾥⾯有key值和新key值相同，就把⽼的值给返回，并且记录这个位置，如果遍历到尾部还不相同，那么就使⽤尾插⼊把数据给添加进去。
5. 对2步骤和4步骤记录的位置进⾏处理，⼀是把标记的位置的⽼值给返回，⼆是把新插⼊的值放到标记的位置上⾯。
底层源码：
final V putVal(int hash, K key, V value,boolean onlyIfAbsent,boolean evict){
Node<K,V>[] tab; Node<K,V> p;int n, i;
// 如果table为空，或者还没有元素时，则扩容
if((tab = table)==null||(n = tab.length)==0)
n =(tab =resize()).length;
dmo
// 如果⾸结点值为空，则创建⼀个新的⾸结点。
// 注意：(n - 1) & hash才是真正的hash值，也就是存储在table位置的index。在1.6中是封装成indexFor函数。
if((p = tab[i =(n -1)& hash])==null)
tab[i]=newNode(hash, key, value,null);
else{// 到这⼉了，就说明碰撞了，那么就要开始处理碰撞。
Node<K,V> e; K k;
// 如果在⾸结点与我们待插⼊的元素有相同的hash和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){
< =newNode(hash, key, value,null);
// 当遍历的结点数⽬⼤于8时，则采取树化结构。
if(binCount >= TREEIFY_THRESHOLD -1)// -1 for 1st
treeifyBin(tab, hash);
孙荣章break;
}
/
/ 如果到与我们待插⼊的元素具有相同的hash和key值的结点，则停⽌遍历。此时e已经记录了该结点
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;
// onlyIfAbsent表⽰如果当前位置已存在⼀个值，是否替换，false是替换，true是不替换
if(!onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);// 这个是空函数，可以由⽤户根据需要覆盖
return oldValue;
}
}
++modCount;
// 当结点数+1⼤于threshold时，则进⾏扩容
if(++size > threshold)
resize();
afterNodeInsertion(evict);// 这个是空函数，可以由⽤户根据需要覆盖
return null;
}
HashMap在put()的时候，如果put⼀个已经存在的key，那么会把⽼的key对应的value值返回
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议