2019-06-042的幂次方减1后每一位都是1，让数组每一个位置都能添加到元素。
例如十进制8，对应二进制1000，减1是0111，这样在&hash值使数组每个位置都是可以添加到元素的，如果有一个位置为0，那么无论hash值是多少那一位总是0，例如0101，&hash后第二位总是0，也就是说数组中下标为2的位置总是空的。
如果初始化大小设置的不是2的幂次方，hashmap也会调整到比初始化值大且最近的一个2的幂作为capacity。作者回复: 回答正确，就是减少哈希冲突，均匀分布元素。
45
2019-06-041）通过将 Key 的 hash 值与 length-1 进行 & 运算，实现了当前 Key 的定位，2 的幂次方可以减少冲突（碰撞）的次数，提高 HashMap 查询效率；
2）如果 length 为 2 的次幂，则 length-1 转化为二进制必定是 11111…… 的形式，在于 h 的二进制与操作效率会非常的快，而且空间不浪费；如果 length 不是 2 的次幂，比如 length 为 15，则 length-1 为 14，对应的二进制为 1110，在于 h 与操作，最后一位都为 0，而 0001，0011，0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。作者回复: 回答非常到位
1 23
2019-06-13加载因子那块儿，感觉有点跳跃，为什么加载因子越大，对空间利用越充分呢？作者回复: 加载因子是扩容的参考标准，如果加载因子越大，例如默认数组初始化大小为16，加载因子由0.75改成1.0，原来数组长度到了12就扩容，变成数组大小为16，也就是说被占满了，才会进行扩容，这也可能意味着已经发生了很多哈希冲突，这样导致某些数组中的链表长度增加，影响查询效率。
1 15
2019-06-04老师您好，能解答下，为什么JDK1.8之前，链表元素增加采用的是头插法，1.8之后改成尾插法了。1.8之前采用头插法是基于什么设计思路呢？作者回复: 你好，JDK1.7是考虑新增数据大多数是热点数据，所以考虑放在链表头位置，也就是数组中，这样可以提高查询效率，但这种方式会出现插入数据是逆序的。在JDK1.8开始hashmap链表在节点长度达到8之后会变成红黑树，这样一来在数组后节点长度不断增加时，遍历一次的次数就会少很多，相比头插法而言，尾插法操作额外的遍历消耗已经小很多了。
也有很多人说避免多线程情况下hashmap扩容时的死循环问题，我个人觉得避免死循环的关键不在尾插法的改变，而是扩容时，用了首尾两个指针来避免死循环。这个我会在后面的多线程中讲到hashmap扩容导致死循环的问题。 7
2019-06-05老师，您好，请教一个问题，为什么 HashMap 的容量等于数组长度？但是扩容的时候却是根据 Map 里的所有元素总数去扩容，这样会不会导致数组中的某一个 node 有很长的链表或红黑树，数组中的其他位置都没有元素？谢谢作者回复: 这种数据倾斜的可能性比较小
1 6
2019-06-050 的话索引不变，1 的话索引变成原索引加上扩容前数组。 这句有点不理解 老师作者回复: 以下是resize中判断是否位移的部分代码，我们可以看到元素的hash值与原数组容量运算，如果运算结果为0，保持原位，如果运算结果为1，则意向扩容的高位。
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
假设链表中有4、8、12，他们的二进制位00000100、00001000、00001100，而原来数组容量为4，则是 00000100，以下与运算：
00000100 & 00000100 = 0 保持原位
00001000 & 00000100 = 1 移动到高位
00001100 & 00000100 = 1 移动到高位 7 5
2019-06-04老师好。hashmap的put和get的时间复杂度算多少啊?最好O(1)。最坏复杂度是O(log(n))平均是O(1)么?。。。treeMap的,treeMap，putO(n)，getO(1)?之前面试被问了，不晓得哪错了作者回复:
面试的时候，问到时间复杂度，大部分是考察你对数据结构的了解程度。建议可以多复习下数据结构的知识。
hashmap的最优时间复杂度是O（1），而最坏时间复杂度是O(n)。
在没有产生hash冲突的情况下，查询和插入的时间复杂度是O(1)；
而产生hash冲突的情况下，如果是最终插入到链表，链表的插入时间复杂度为O(1)，而查询的时候，时间复杂度为O(n)；
在产生hash冲突的情况下，如果最终插入的是红黑树，插入和查询的平均时间复杂度是O（logn）。
而TreeMap是基于红黑树实现的，所以时间复杂度你也清楚了吧。 1 5
2019-10-12装载因子0.75是怎么算出来了，是经验值还是什么？ 另外为什么链表长度8就要转红黑树呢作者回复: 加载因子过高，虽然提高了空间的利用率，但增加了查询时间的成本；加载因子过低，虽然减少查询时间的成本，但是空间利用率又很低了。所以0.75是一个折中的选择。
链表长度为8转为红黑树的原因是，官方根据泊松分布实验发现，假设hashmap长度length为16，假设放入12（0.75*16）个数据到hashmap中，链表中存放8个节点的概率仅为0.00000006，而链表中存放1~7节点的概率为：
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
从以上可知，实际上一个链表被放满8个节点的概率非常小，实际上链表转红黑树是非常耗性能的，而链表在8个节点以内的平均查询时间复杂度与黑红树相差无几，超过8个节点，黑红树的查询复杂度会好一些。所以，当链表的节点大于等于8个的时候，转为红黑树的性价比比较合适。 4
2019-06-05初始容量2的n次方是偶数，在计算key的索引位置时，是通过(n-1)&hash计算的，这样n-1得到的奇数，那么通过在进行与操作时，如果hash的第一位是0，那么(n-1)&hash得到的是偶数，如果hash的第一位是1，那么(n-1)&hash得到的是奇数，因此可以让数据分布更加均匀，减少hash冲突，相反如果n-1是偶数，那无论hash的第一位是偶数还是奇数，(n-1)&hash得到的都是偶数，不利于数据的分布 4
2019-06-28使用2的次幂是因为进行&运算的时候，每次都能落到tables数组内，并且2的次幂进行&运算和直接模运算（%）的值是一样的，也就是说（n-1）&hash==hash%n，如果直接使用（%）模运算最终也会转换成二进制的去计算性能不如&运算，还有就是&计算分布均匀，减少哈希冲突，如果是2的次幂,假设n=16，（16-1）&0==0、（16-1）&1==1、16-1)&2==2、........、（16-1)&19==3、（16-1)&20==4、（16-1)&21==5、。如果不是2的次幂的话，假设是n=15，（15-1）&1==0、（15-1）&1==2、（15-1)&3==2、......、（15-1)&4==4、（15-1)&5==4. 哈哈、不知道我回答的沾不沾边？望老师您点评一下哈作者回复: 理解正确，赞
2
2019-06-10编程中有遇到这种情况,当判断一个数n 是否为偶数使用n%2 == 0 ,计算机语言已经做了优化为 n&(2-1) = n & 1 == 0,对于二进制来说与操作只需要一个电路即可完成比取余速度快多了,相同的对于hash扩容,只需要判断前一位hash值是0还是1,如果是0保持数组位置不变,如果为1增加原来扩容前数组长度即可,而且由于hash值计算每一位都是平均分配0或者1,所以保持均匀分布 2
2019-06-05以前看源码，我记得好像链表转换红黑树不光链表元素大于8个，好像还有一个表的大小大于64作者回复: 对的，有这样一个条件。
2
2019-06-04一下子追到最新了。老师集合这块讲得是真不错。弱弱补个小点。空集合或空map返回不要new，走常量不可变集合或map。尽量减少对象的创建。毕竟创建和回收都是有开销的。 2
2019-06-04因为选择下标和扩容的时候都依赖和(n-1）按位与，2的幂次方满足n-1都是1的情况，因此必须选择2的幂次方，且如果使用时传入的参数不是2的幂次方，HashMap会自动转成大于传入参数的最小的2的幂次方来确保下标和扩容机制的正常运行 2
2019-06-05主要是为了减少hash冲突，hash & (n-1) n为2的n次幂，n-1换成比特位都是1 1
2019-06-05Hash字典发生扩容时，需要复制元素，请问这个过程是一次完成的吗？redis里的字典是准备了两个字典，一个原始字典，一个rehash字典，扩容后，不是一次完成数据迁移的，每次操作字典都考虑两个数组并复制数据，扩容完毕后交换两个数组指针作者回复: HashMap的扩容是一次性完成的。
1
2019-06-04最主要的原因是位运算替代%取模操作，提高运算性能，说什么降低冲突的，是否比较过质数和偶数冲突概率呢？作者回复: 用与运算是提高了运算性能，而容量大小为2的幂次方是为了降低哈希冲突。
1
2019-06-04hashmap在多线程情况下数据丢失，大师，能不能分析分析原因作者回复: 你好，这个在后面多线程中会讲到，可以留意关注下。
1
2019-06-04要是早一天发这个就好了，昨天面试被问到哈希函数给问懵了。老师很棒！这几乎是我在极客跟的最紧的课。作者回复: 哈希表在面试中是出现较频繁的，不仅因为它在平时工作中用的比较多，还由于它优秀的设计和优化思想。
1
2019-12-23很棒
1.就是被hashmap中链表的 头部 和 尾部搞晕了，老师，是数组里的元素是链表头部还是尾部啊？
2.扩容方法，呜呜呜… 有点想老师也能贴一下扩容源码分析。作者回复: 1、只是一个首尾数据调换的过程；
2、后面补上，评论里面字数有限，无法将完整源码贴上。