3秒种搞定HashMap

HashMap定位元素位置是通过键key经过扰动函数扰动后得到hash值，然后再通过hash(key) & (length - 1)代替取模的方式进行元素定位的。

HashMap的负载因子表示哈希表空间的使用程度（或者说是哈希表空间的利用率）。当负载因子越大，则HashMap的装载程度就越高。也就是能容纳更多的元素，元素多了，发生hash碰撞的几率就会加大，从而链表就会拉长，此时的查询效率就会降低。当负载因子越小，则链表中的数据量就越稀疏，此时会对空间造成浪费，但是此时查询效率高。

resize()主要做两件事：2倍扩容与拷贝



1.7

 头插法，多线程情况下会造成死循环

1.8

 尾插法，无法保证上一次put的值,下一秒还是原值

链表长度超过8

数组长度大于等于64

  原因：

  链表长度大于8的时候就会调用treeifyBin方法转化为红黑树，但是在treeifyBin方法内部却有一个判断，当只有数组长度大于64的时候，才会进行树形化，否则就只是resize扩容。因为链表过长而数组过短，会经常发生hash碰撞，这个时候树形化其实是治标不治本，因为引起链表过长的根本原因是数组过短。执行树形化之前，会先检查数组长度，如果长度小于 64，则对数组进行扩容，而不是进行树形化

0.75

  提高空间利用率和减少查询成本的折中，主要是泊松分布，0.75的话碰撞最小



16

  理论上2的幂都行，但是如果是2，4或者8会不会有点小，添加不了多少数据就会扩容，也就是会频繁扩容，这样岂不是影响性能，如果是32或者更大，浪费空间了空间,所以16就作为一个非常合适的经验值保留了下来



2的幂

 

 1.服务位运算

  如果length为2的次幂  则length-1 转化为二进制必定是11111……的形式,位运算要比算数运算快

 2.均匀散列

  奇数的最后一位为1，这样便保证了h&(length-1)的最后一位为0，也可能为1（这取决于h的值），即与后的结果可能为偶数也可能是奇数。这样便可以保证散列的均匀性，

  而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间。所以,length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。



8

          \* 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:    0.00000006

    如果 hashCode的分布离散良好的话，那么红黑树是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，注释中给我们展示了1-8长度的具体命中概率，当长度为8的时候，概率概率仅为0.00000006，这么小的概率，HashMap的红黑树转换几乎不会发生，因为我们日常使用不会存储那么多的数据，你会存上千万个数据到HashMap中吗？当然，这是理想的算法，但不妨某些用户使用HashMap过程导致hashCode分布离散很差的场景，这个时候再转换为红黑树就是一种很好的退让策略。



 64

 

   链表长度大于8的时候就会调用treeifyBin方法转化为红黑树，但是在treeifyBin方法内部却有一个判断，当只有数组长度大于64的时候，才会进行树形化，否则就只是resize扩容。因为链表过长而数组过短，会经常发生hash碰撞，这个时候树形化其实是治标不治本，因为引起链表过长的根本原因是数组过短。执行树形化之前，会先检查数组长度，如果长度小于 64，则对数组进行扩容，而不是进行树形化

  

    两个对象 equals() 返回 true 的时候，那它们的 hashCode() 值需要相等；

    如果两个对象的 hashCode() 值相等，那它们 equals() 不一定是 true；（哈希冲突）

    所以在这种情况下，如果要判断两个对象是否相等，除了要覆盖 equals() ，也要覆盖 hashCode()，否则就会发生意料之外的问题。