欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HashMap原理

程序员文章站 2022-06-04 18:51:07
...

1.HashMap原理

源码以JDK8为例,分析HashMap原理

以下是hashMap的put方法源码,直接从put方法开始

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
1.计算hash值

通过hashCode方法计算hash值

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

(h = key.hashCode()) ^ (h >>> 16)是因为通常情况 bucket 的槽位很少,用于参与运算的只有 hashCode 低位,为了让高位也可以参与运算,尽可能的在不影响性能的情况下避免冲突,所以做了一下高位右移 16 位然后亦或运算。

此处是引用,个人暂时认为这只是一种处理方式.

2.根据hash值和数组长度n计算index

通俗来讲就是对数组长度求余
------hash初始数组长度为16,默认负载系数0.75

(n - 1) & hash       //629行
3.putVal

4.1.判断该下标是否存在Entry,不存在直接将Entry放入该下标的数组(桶).如果存在,继续4.2步骤
4.2.判断新旧Entry的hash值是否相等,以及新旧key的equals是否相等.两者都一致,覆盖原来的Entry.否则,依次判断该桶上的链表,直至放到链表的最后或者覆盖链表Entry.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 初始化数组长度
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // index位置无值,直接放入
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 覆盖Entry
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // Entry是LinkedHashMap.Entry直接放
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            // 发生哈希碰撞
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //  链表长度大于等于8,转为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 自动扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

resize 就是自动扩容,当 size 达到阈值以后会扩容到原来的 2 倍,关键代码 newCap = oldCap << 1。但是这里有一个非常巧妙的解决方法,因为扩容是扩充的 2 倍,n-1 转换为二进制也就是高位变成了1,那么根据(n - 1) & hash 计算,如果 hash 高位是 1 那么新的 index 位置就是 oldIndex + 16,如果hash 的高位 是 0 ,那么 index 的位置就是原来的 oldIndex 的位置,这样直接判断高位就可以了,省去了重新计算hash。

2.从时间复杂度角度分析

2.1HashMap与TreeMap的O()区别

HashMap是一个key,value的数据结构,时间复杂度可以最快优化到O(1),当效果不好的时间复杂度O(logN)或者O(n),Hash不能保证key的顺序.而TreeMap可以保证key的有序性,它的查找,删除,更新的时间复杂度都是0(logN).

2.2HashMap与TreeMap底层分析

HashMap底层是通过数组(桶)和哈希的方式实现的,通过key的哈希值映射到数组中,这时候通过key获取value的时间复杂度是O(1).HashMap里面每个数组都相当于是个链表,当key发生哈希冲突时,key-value会追加到链表尾,这时候时间复杂度就变成了O(n).当然HashMap进行了优化,当链表长度等于大于8的时候,链表的结构会转变为红黑树,时间复杂度就成了O(logN).讲到红黑树,TreeMap底层就是通过红黑树实现的.

2.3红黑树分析

1、根节点是黑色的
2、红色节点的子节点必须是黑色并且父节点也是黑色,
3、任何一条路径的黑色节点个数相同。
它通过这些特性再重新插入的时候做着色处理,配合左旋,右旋来达到最终的平衡,并不是想平衡二叉树的完美平衡,只追求大致平衡。每次插入,最多旋转三次即可大致平衡,而平衡二叉树的旋转不可预计.

2.3ConcurrentHashMap

在HashMap的基础上面使用了synchronized锁机制.
在putVal(),replaceNode(),clear(),treeifyBin()转红黑树等方法中使用了synchronized锁机制.使用ConcurrentHashMap线程安全.

相关标签: java java