HashMap源码分析

HashMap是一个很经典的键值对集合,从它的广泛应用程度和源码的学习角度上我们不得不去解析它。 我们先看一下HashMap的存储结构((图片均来源于网络)),这有助于我们阅读源码

HashMap的主干是一个Entry数组EntryHashMap的基本组成单元,每一个Entry包含一个key-value键值对以及指引的下一个Entry

/** @hide */  // Android added.
   static class HashMapEntry<K,V> implements Map.Entry<K,V> {
       final K key;
       V value;
       HashMapEntry<K,V> next;
       int hash;

       /**
        * Creates new entry.
        */
       HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
           value = v;
           next = n;
           key = k;
           hash = h;
       }

       public final K getKey() {
           return key;
       }

       public final V getValue() {
           return value;
       }

       public final V setValue(V newValue) {
           V oldValue = value;
           value = newValue;
           return oldValue;
       }

       public final boolean equals(Object o) {
           if (!(o instanceof Map.Entry))
               return false;
           Map.Entry e = (Map.Entry)o;
           Object k1 = getKey();
           Object k2 = e.getKey();
           if (k1 == k2 || (k1 != null && k1.equals(k2))) {
               Object v1 = getValue();
               Object v2 = e.getValue();
               if (v1 == v2 || (v1 != null && v1.equals(v2)))
                   return true;
           }
           return false;
       }

       public final int hashCode() {
           return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
       }

       public final String toString() {
           return getKey() + "=" + getValue();
       }

       /**
        * This method is invoked whenever the value in an entry is
        * overwritten by an invocation of put(k,v) for a key k that's already
        * in the HashMap.
        */
       void recordAccess(HashMap<K,V> m) {
       }

       /**
        * This method is invoked whenever the entry is
        * removed from the table.
        */
       void recordRemoval(HashMap<K,V> m) {
       }
   }

初始化过程

/**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        } else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
            initialCapacity = DEFAULT_INITIAL_CAPACITY;
        }

        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // Android-Note: We always use the default load factor of 0.75f.

        // This might appear wrong but it's just awkward design. We always call
        // inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
        // to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
        // the load factor).
        threshold = initialCapacity;
        init();
    }

/**
     * Initialization hook for subclasses. This method is called
     * in all constructors and pseudo-constructors (clone, readObject)
     * after HashMap has been initialized but before any entries have
     * been inserted.  (In the absence of this method, readObject would
     * require explicit knowledge of subclasses.)
     */
    void init() {
    }

主要就是进行一个赋值 put过程:

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            //初始化table
            inflateTable(threshold);
        }
        if (key == null)//put key==null的值
            return putForNullKey(value);
        //根据key得到hash
        int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
        //根据hash得到下标
        int i = indexFor(hash, table.length);
        //进行next链表检测key是否已经存在
        for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //如果key已经存在  将重新赋值
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        //添加新的值
        addEntry(hash, key, value, i);
        return null;
    }

首先检测是否是空的装HashMapEntry数组table,如果是空的将调用inflateTable进行初始化

/**
     * Inflates the table.
     */
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);

        // Android-changed: Replace usage of Math.min() here because this method is
        // called from the <clinit> of runtime, at which point the native libraries
        // needed by Float.* might not be loaded.
        float thresholdFloat = capacity * loadFactor;
        if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
            thresholdFloat = MAXIMUM_CAPACITY + 1;
        }
        threshold = (int) thresholdFloat;
        table = new HashMapEntry[capacity];
    }

接着检测key==null,如果为null,将调用putForNullKey函数给key==nullkey赋值

/**
     * Offloaded version of put for null keys
     */
    private V putForNullKey(V value) {
        for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

从这就可以看出 HashMapkey可以为null 接下来就到了HashMap的关键地方,HashMap自己实现了一个keyHash值计算,然后根据计算出的hash值和当前容器的table的长度进行&运算得到index,然后根据这个index确定需要放置的位置。

 int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
 int i = indexFor(hash, table.length);
/**
    * Returns index for hash code h.
    */
   static int indexFor(int h, int length) {
       // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
       return h & (length-1);
   }

这样计算的目的是为了根据hash值和table.length进行分组,也就是上面图示那样,然后通过链式的结构链接,这样的话就缩短了大量的查询时间。 拿到了所在的组,也就是下标位置,就拿到这个下标的HashMapEntry,然后进行next遍历,如果有存在的key就重新赋值返回即可。

for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
           Object k;
           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue;
           }
       }

如果没有存在的key,那么先判断是否扩容

/**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
           //判断扩容
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);//扩容以及数据重组
            hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
      //创建一个新的Entry添加
        createEntry(hash, key, value, bucketIndex);
    }

扩容的方式为当前容量的两倍

/**
     * Rehashes the contents of this map into a new array with a
     * larger capacity.  This method is called automatically when the
     * number of keys in this map reaches its threshold.
     *
     * If current capacity is MAXIMUM_CAPACITY, this method does not
     * resize the map, but sets threshold to Integer.MAX_VALUE.
     * This has the effect of preventing future calls.
     *
     * @param newCapacity the new capacity, MUST be a power of two;
     *        must be greater than current capacity unless current
     *        capacity is MAXIMUM_CAPACITY (in which case value
     *        is irrelevant).
     */
    void resize(int newCapacity) {
        HashMapEntry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        HashMapEntry[] newTable = new HashMapEntry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

我们分组(下标)是根据table.lengthkeyhash值来决定的,所以在扩容之后,table.length变化了对应的分组(下标)就变化了,所以这时候需要重新组装数据

/**
     * Transfers all entries from current table to newTable.
     */
    void transfer(HashMapEntry[] newTable) {
        int newCapacity = newTable.length;
        for (HashMapEntry<K,V> e : table) {
            while(null != e) {
                HashMapEntry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

组装的方式如下图所示

最后根据hash key value index得到一个新的HashMapEntry对象,将原来组(下标)的HashMapEntry作为这个新的对象的next指向即可。

/**
     * Like addEntry except that this version is used when creating entries
     * as part of Map construction or "pseudo-construction" (cloning,
     * deserialization).  This version needn't worry about resizing the table.
     *
     * Subclass overrides this to alter the behavior of HashMap(Map),
     * clone, and readObject.
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMapEntry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
        size++;
    }

/**
         * Creates new entry.
         */
        HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

有了put的分析,get过程理解就比较轻松了

/**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

/**
     * Offloaded version of get() to look up null keys.  Null keys map
     * to index 0.  This null case is split out into separate methods
     * for the sake of performance in the two most commonly used
     * operations (get and put), but incorporated with conditionals in
     * others.
     */
    private V getForNullKey() {
        if (size == 0) {
            return null;
        }
        for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

/**
     * Returns the entry associated with the specified key in the
     * HashMap.  Returns null if the HashMap contains no mapping
     * for the key.
     */
    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
        for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

先判断key值是否是null,如果是null的话那么将在第0组(下标)查找,如果不是的话就通过keyhashtable.length得到对应的组(下标)查找,查找的过程就是对其HashMapEntry进行next遍历查找判断即可。

remove过程

/**
     * Removes the mapping for the specified key from this map if present.
     *
     * @param  key key whose mapping is to be removed from the map
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.getValue());
    }
 /**
     * Removes and returns the entry associated with the specified key
     * in the HashMap.  Returns null if the HashMap contains no mapping
     * for this key.
     */
    final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
        int i = indexFor(hash, table.length);
        HashMapEntry<K,V> prev = table[i];
        HashMapEntry<K,V> e = prev;

        while (e != null) {
            HashMapEntry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

remove过程也是先得到对应的组(下标),然后申明一个HashMapEntry零时变量prev记录上一个指标,对当前组的HashMapEntry进行next遍历,在遍历过程中将值赋予prev,然后判断key相同重新将其prevnext指向接下来的哪个HashMapEntry即可。 如图所示:


参考链接: HashMap实现原理及源码分析 HashMap的扩容机制—resize()

水平有限,文中有什么不对或者有什么建议希望大家能够指出,谢谢!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(一)No.47

hello哈,大家是不是好久没见到我啦?我也是一直在摸索小伙伴们喜欢看到什么东西,不喜欢看什么东西,还请大家多多支持。为了表示感谢。小蕉在这给你们一鞠躬,二鞠躬...

2275
来自专栏闵开慧

曾经做过的40道程序设计课后习题总结(二)

曾经做过的40道程序设计课后习题总结(二) 课后习题目录 1 斐波那契数列 2 判断素数 3 水仙花数 4 分解质因数 5 杨辉三角 6 学习成绩查询 7 求最...

3737
来自专栏趣谈编程

二分查找

面试官:写个二分热热身 我心想:不用热身,热的手已经出汗了 二分查找有着查找速度快,平均性能好等优点,但必须要求待查表为有序表,且插入删除困难,面试比较常考,今...

2036
来自专栏逸鹏说道

Python3 与 C# 面向对象之~继承与多态

当听到老师说:“私有的属性方法 不会被子类继承 ”的时候,小明心里一颤,联想到之前讲的 类属性、实例属性、实例方法、类方法、静态方法,于是赶紧写个Demo验证一...

1223
来自专栏逸鹏说道

Python3 与 C# 面向对象之~继承与多态

文章汇总:https://www.cnblogs.com/dotnetcrazy/p/9160514.html

1563
来自专栏aCloudDeveloper

算法导论2-9章补充几道题

本篇博文意在对前几章中遗漏的,本人觉得有意思的习题当独拿出来练练手。 1、习题2-4,求逆序对,时间复杂度要求Θ(nlgn) 定义:对于一个有n个不同的数组A,...

2205
来自专栏枕边书

PHP实现堆排序

经验 工作了,面试我工作这家公司时被技术面打击得不行,因为自己的数据结构等基础学得实在太差,虽然原来是想做设计师的说。。。不过看在PHP写得还凑合的份上能来实习...

2047
来自专栏大数据学习笔记

Java之HashMap源码解读

HashMap一直是数组加链表的数据结构,在数组的某个下标位置,有多次碰撞,则使用链表数据结果存储。在jdk1.8中,引入了红黑二叉查找树的数据结构。刚开始产生...

1996
来自专栏专知

【 关关的刷题日记48】Leetcode 58. Length of Last Word

关关的刷题日记48 – Leetcode 58. Length of Last Word 题目 Given a string s consists of upp...

2564
来自专栏葬爱家族

Android高德之旅(14)行政区划搜索废话简介总结

前后两千万,拍照更清晰。大家好,这里是OPPO R11独家冠名赞助播出的大型情感类电视连续剧《Android高德之旅》,我是主持人大公爵。(开篇占位)

1641

扫码关注云+社区

领取腾讯云代金券