03 | 数组与链表：存储设计的基石有哪些？

问题1 网上找寻资料学习了一下: (1) 开放定址法 ①线性探测法 实现过程：当我们的所需要存放值的位置被占了，我们就往后面一直加1并对m取模直到存在一个空余的地址供我们存放值，取模是为了保证找到的位置在0~m-1的有效空间之中。 公式：h(x)=(Hash(x)+i)mod (Hashtable.length);（i会逐渐递增加1） 存在问题：出现非同义词冲突（两个不相同的哈希值，抢占同一个后续的哈希地址）被称为堆积（聚集）现象 ②平方探测法（二次探测） 实现过程： 当我们的所需要存放值的位置被占了，会前后寻找而不是单独方向的寻找 公式：h(x)=(Hash(x) +i)mod (Hashtable.length);（i依次为+(i^2)和-(i^2)） 存在问题：相比线性探测减少找寻时间，但不会减少堆积（聚集）现象 （2）再哈希法 实现过程：同时构造多个不同的哈希函数，等发生哈希冲突时就使用第二个、第三个……等其他的哈希函数计算地址，直到不发生冲突为止 存在问题：不易发生聚集，但是增加了计算时间 （3）建立公共溢出区 实现过程：将哈希表分为基本表和溢出表，将发生冲突的都存放在溢出表中 存在问题：需要实时动态维护两张哈希表

HashMap 中哈希槽的容量为什么必须为 2 的倍数？ 当我们计算key的索引下标时， 通过会对key的哈希码对数组取模运算来计算出下标值。 而JAVA中的大神对取模运算又进行了一次优化。 将取模运算优化为与运算。 为什么能被优化为与运算呢？ 举个简单的例子： hashcode为11,数组容量为4。 我们知道对于2的n次方一定能整除2的n-1次方。 11对8取模，获取它的余数,也就是它的下标值。 转化为二进制1011 % 0100, 也就是1011/0100, 因为2的n次方一定能整除2的n-1次方的缘故，高位直接舍弃。 其余的无法被整数的也就是它的余数，它的低位就是它的余数， 获取它的低位就可以通过x011&(0100-1)=>也就是hash & (n-1),能推导出这个公式是建立在数组的容量是2的倍数的前提上。 为什么要优化为与运算呢？ 我的猜想，计算机对于与运算的指令比取模运算的指令要少的多， 故与运算要高效的多。 最后，我还想再说一个key获取哈希值的优化。 我们知道，生成哈希值的原则就是要尽量让所有的元素都参与到计算。 key获取哈希值， 并不是简单的直接获取哈希码， 而是该key的哈希值高低16位再一次又进行了异或运算，这样就可以让哈希值再次变化。 其实也可以不变化的，但是对于起始容量比较小，大量的元素如果低位都相同，就可能会造成大量的哈希冲突。 而再一次进行异或运算， 即使相同的低位也可以再次变化， 减小hash冲突。

hashmap，容量设计成2的整数幂，我理解有两点： 1.就是设计成2整数幂可以利用位运算的高效，快速找到下标。 2.为了扩容搬运元素方便，小于之前size的元素，可以直接搬运到新size的原始位置，而超过原始size的元素，只需要下标加上原始size即可，实战了高效的扩容元素迁移。

RocketMQ这块的分析还可以

分析到位 图标很棒

https://time.geekbang.org/column/article/64586 数据结构与算法之美 对照着学习～～

hashmap1.8之前采用头插法的解释很牵强啊！通过复杂度比较的话头尾不都是O(1)