1. HashMap底层的数据结构是什么？
1.8 数组+链表+红黑树
2. JDK 1.8中对hash算法和寻址算法是如何优化的？
hash算法优化
// JDK 1.8以后的HashMap里面hash源码
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
比如说：有一个key的hash值
1111 1111 1111 1111 1111 1010 0111 1100
0000 0000 0000 0000 1111 1111 1111 1111
1111 1111 1111 1111 0000 0101 1000 0011 -> int值，32位
hash值一样 -> 他们其实都会在数组里放在一个位置，进行复杂的hash冲突的处理
[16个元素] -> hash值对数组长度取模，定位到数组的一个位置，塞进去就ok了
高低16位都参与运算
寻址算法优化
(n - 1) & hash -> 数组里的一个位置
1111 1111 1111 1111 1111 1010 0111 1100（没有经过优化的hash值）
0000 0000 0000 0000 0000 0000 0000 1111
取模运算，他是性能比较差一些，为了优化这个数组寻址的过程
hash & (n - 1) -> 效果是跟hash对n取模，效果是一样的，但是与运算的性能要比hash对n取模要高很多，数学问题，数组的长度会一直是2的n次方，只要他保持数组长度是2的n次方
hash对n取模的效果 -> hash & (n - 1)，效果是一样的，后者的性能更高
1111 1111 1111 1111 1111 1010 0111 1100（没有经过优化的hash值）
0000 0000 0000 0000 0000 0000 0000 1111
相当于，你直接这么搞，高16位之间的与运算，是可以忽略的，核心点在于低16位的与运算，hash值的高16位没有参与到与运算里来啊
假设有两个hash值
1111 1111 1111 1111 1111 1010 0111 1100 -> 1111 1111 1111 1111 0000 0101 1000 0011
1111 1111 1111 1110 1111 1010 0111 1100 -> 1111 1111 1111 1110 0000 0101 1000 0010
1111 1111 1111 1111 0000 0101 1000 0011（经过优化和二进制位运算的新的hash值）
0000 0000 0000 0000 0000 0000 0000 1111
配合起来讲
hash算法的优化：对每个hash值，在他的低16位中，让高低16位进行了异或，让他的低16位同时保持了高低16位的特征，尽量避免一些hash值后续出现冲突，大家可能会进入数组的同一个位置。
寻址算法的优化：用与运算替代取模，提升性能
3. HashMap是如何解决hash碰撞问题的吗？
hash冲突问题，链表+红黑树，O(n)和O(logn)
map.put和map.get -> hash算法优化（避免hash冲突），寻址性能优化
算出key的hash值，到数组中寻址，找到一个位置，把key-value对放进数组，或者从数组里取出来
两个key，多个key，他们算出来的hash的值，与n-1，与运算之后，发现定位出来的数组的位置还是一样的，hash碰撞，hash冲突。
还有一个重要的原因是:hash值与n-1与运算，实际上高16为并没有参与运算，原因是n-1的高16为都是0,和hash的高16位进行与运算的时候，都为0.
[<> -> <> -> <>, ]
array[0]这个位置，就是一个链表
会在这个位置挂一个链表，这个链表里面放入多个元素，让多个key-value对，同时放在数组的一个位置里
get，如果定位到数组里发现这个位置挂了一个链表，此时遍历链表，从里面找到自己的要找的那个key-value对就可以了
假设你的链表很长，可能会导致遍历链表，性能会比较差，O(n)
优化，如果链表的长度达到了一定的长度之后，其实会把链表转换为红黑树，遍历一颗红黑树找一个元素，此时O(logn)，性能会比链表高一些。
说说HashMap是如何进行扩容的可以吗？
底层是一个数组，当这个数组满了之后，他就会自动进行扩容，变成一个更大的数组，让你在里面可以去放更多的元素
2倍扩容
[16位的数组，<> -> <> -> <>]
[32位的数组，<> -> <>, <>]
数组长度=16
n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash1 1111 1111 1111 1111 0000 1111 0000 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）
n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash2 1111 1111 1111 1111 0000 1111 0001 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）
在数组长度为16的时候，他们两个hash值的位置是一样的，用链表来处理，出现一个hash冲突的问题
如果数组的长度扩容之后 = 32，重新对每个hash值进行寻址，也就是用每个hash值跟新数组的length - 1进行与操作
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash1 1111 1111 1111 1111 0000 1111 0000 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash2 1111 1111 1111 1111 0000 1111 0001 0101
&结果 0000 0000 0000 0000 0000 0000 0001 0101 = 21（index = 21的位置）
判断二进制结果中是否多出一个bit的1，如果没多，那么就是原来的index，如果多了出来，那么就是index + oldCap，通过这个方式，就避免了rehash的时候，用每个hash对新数组.length取模，取模性能不高，位运算的性能比较高
网友评论