JAVA非并发容器--HashMap-存储结构

概述

我相信只要写过JAVA的程序要拿99%的都用过HashMap, 其是我们最常用，也是最基础的一个Ｍap.本篇文章将从存储结构、hash规则、扩容策略、迭代器四方面来分析其源代码。

存储结构

HashMap用Entry<K,V>存储key, value数据,代码如下：

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<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) {
        }
    }

Entry<K,V> 具有四个属性, 可以组成一个单项链表。

       final K key;
        V value;
        Entry<K,V> next;
        int hash;

HashMap用数组来组织entry:

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

所以，hashMap的底层数据结构如下图：

hashmap-array.png