01_HashMap实现原理

  • 基于Java8
    HashMap的doc中写道:

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

HashMap 是基于Hashtable的实现,The HashMap class is roughly equivalent to Hashtable,但是和Hashtable不同的是,HashMap支持null键和null value,另外HashMap是非线程安全的类。

在整体结构上,HashMap和Hashtable是一致的,即为数组和链表的合成结构,恰好利用了二者的优势:数组易于寻址而不易于插入和删除元素,链表不易于寻址但易于插入和删除元素。

接下来看看实现上的某些有意思的细节。

  1. 低层数组初始化
    和Hashtable不同的是,HashMap的无参构造器没有初始化Node数组(Hashtable中是Entry数组),而是把初始化延迟到了第一次put数据的时候,如代码:
/**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

只是初始化了loadFactor,table对象为null。

然后在put方法中,resize()才开始初始化Node数组:

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 无参构造器初始化后table是null,就会进入resize()方法进行动态扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 这个取余的方法很有意思 在这里(n - 1) & hash是等价于hash % n的 ,因为在这里n必定是2的n次方。
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            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);
                        // 这里有一个将链表转换成红黑树的方法,这样可以提高查询的效率
                        //  配置了一个转换成树的阈值,所以它比hashtable要复杂一些
                        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方法:

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            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;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • To Solve: 什么时候会使用HashMap?有什么特点? HashMap的工作原理? get和put的原理?...
    糜糜糜糜人阅读 2,839评论 2 3
  • 上篇文章我们通过部分源码和结构图了解了HashMap的数据结构,感兴趣的小伙伴看这里HashMap实现原理基础篇。...
    Shmily鱼阅读 6,516评论 0 5
  • 目的:java中为实现能够从一个数量庞大的容器中取出某一个容器(快速查找),做了这个容器Map,而HashMap是...
    4ea0af17fd67阅读 1,365评论 0 1
  • 漫长的比赛结束了,带了两周的训练,很幸苦,前几天都需要一两个小时来备课。第四名。
    songdear阅读 676评论 0 0
  • 上午九点多来到这,也是很冷的。 货车大吊车太高,进不来。又找了个叉车把压滤机挑了过去,才装上车,相当费劲。 中午在...
    巳哖阅读 838评论 0 0