从hashmap说起

原创
2018/10/26 21:18
阅读数 130

说到hashmap我们能想到什么呢

hash

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

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

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

i = (n - 1) & hash

当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,值为一个强引用。

           for (Entry e = tab[i];
                 e != null;
                 e = tab[i = nextIndex(i, len)]) {

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

        private static int nextIndex(int i, int len) {
            return ((i + 1 < len) ? i + 1 : 0);
        }
展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部