从hashmap说起

说到hashmap我们能想到什么呢

hash

hashmap的hash方法极大的避免了hash冲突。他通过高16位和低16位做异或操作。保证了32位都参加运算。

为了保证hashcode尽量的分散在数组中,再算位置的时候使用了容量-1

当hash冲突的时候,链会越来越长,所以解决冲突的时候可能造成链特别长,jdk8中做了改良,当链超过8时候,转化成红黑树。

hash的发散

数据库扩容

因为容量是2的次方,所以n-1后面的位数都是1。保证了在hashcode的值不冲突时,分散也不冲突。

在扩容的时候2次方的好处,就提现出来了,原来同一个槽的数据只会分布在原来的位置或者原来槽的位置+一个原来的距离。举个例子,1,2,3,4。和2取模,结果是1,0,1,0。现在和4取模,就变成了1,2,3,0。原来都在1号位置的数据,现在在1和3,原来在0号位置的,现在在0和2。数据都加了一个扩容的数量。

利用这个特性,可以做到数据库不停机在线扩容。

数据库有主备,当需要把2台机器扩容成4台的时候,就可以把主备都配上,让数据分散到4台机器上,位置就是如上的形式分配。然后解除主备,都成为主,于此同时加新的机器作为备,并且在合理的机会处理冗余数据。

hash冲突解决

hashmap使用的是拉链发解决hash冲突,jdk里还有一种hash冲突的实现,开放定址法。实现类是ThreadLocalMap。ThreadLocalMap是一个key为弱引用的ThreadLocal,值为一个强引用。

当发生hash冲突的时候就直接把位置往后移动一位。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181027G023C500?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券