HashMap 原理

---

HashMap由数组和单向链表构成。

• HashMap由单向链表和数组构成， 默认初始化数组大小为16。
• HashMap中hash值相同的元素存储在同一个链表中， HashMap根据元素key的hashCode值与数组大小计算hash值。
• HashMap允许key=null的元素存在。
• HashMap线程不安全。
• HashMap无序。
• HashMap单个链表元素数量超过一定值会树化， 由单链表转换为红黑树TreeNode
• HashMap大小超过临界值threshold会自动扩容， 自动扩容比较消耗资源， 需要将老数据copy到新的数组结构中，并重新分片。

HashMap 重要成员

---

    static final int DEFAULT_INITIAL_CAPACITY = 16;
    static final int MAXIMUM_CAPACITY = 1073741824;
    static final float DEFAULT_LOAD_FACTOR = 0.75F;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;
    transient HashMap.Node<K, V>[] table;
    transient Set<Entry<K, V>> entrySet;
    transient int size;
    transient int modCount;
    int threshold;
    final float loadFactor;

• table*     HashMap.Node<K, V>[]， HashMap底层数据结构， 用于存储key-value对。
  table由HashMap.Node组成， HashMap.Node是HashMap中的重要数据结构。

static class Node<K, V> implements Entry<K, V> {
        final int hash;
        final K key;
        V value;
        HashMap.Node<K, V> next;

        Node(int hash, K key, V value, HashMap.Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey() {
            return this.key;
        }

        public final V getValue() {
            return this.value;
        }

        public final String toString() {
            return this.key + "=" + this.value;
        }

        public final int hashCode() {
            return Objects.hashCode(this.key) ^ Objects.hashCode(this.value);
        }

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

        public final boolean equals(Object o) {
            if (o == this) {
                return true;
            } else {
                if (o instanceof Entry) {
                    Entry<?, ?> e = (Entry)o;
                    if (Objects.equals(this.key, e.getKey()) && Objects.equals(this.value, e.getValue())) {
                        return true;
                    }
                }

                return false;
            }
        }
    }

HashMap.Node是一个单向链表，由hash, key, value, next四个字段组成， 实现了接口Map.Entry<K, V>, 接口Map.Entry<K,V>代码如下:

public interface Entry<K, V> {
        K getKey();

        V getValue();

        V setValue(V var1);

        boolean equals(Object var1);

        int hashCode();

        static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() {
            return (Comparator)((Serializable)((c1, c2) -> {
                return ((Comparable)c1.getKey()).compareTo(c2.getKey());
            }));
        }

        static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() {
            return (Comparator)((Serializable)((c1, c2) -> {
                return ((Comparable)c1.getValue()).compareTo(c2.getValue());
            }));
        }

        static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
            Objects.requireNonNull(cmp);
            return (Comparator)((Serializable)((c1, c2) -> {
                return cmp.compare(c1.getKey(), c2.getKey());
            }));
        }

        static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
            Objects.requireNonNull(cmp);
            return (Comparator)((Serializable)((c1, c2) -> {
                return cmp.compare(c1.getValue(), c2.getValue());
            }));
        }
    }

HashMap.Node主要重新实现了Map.Entry的Get/Set/hashCode方法。

• entrySet   Map.EntrySet<K,V>实体
• size      已存储元素数量
• threshold   临界值，代表可存储元素数量， 超过此值，代表需要扩容
• loadFactor   负载因子， 衡量满的程度。
• capacity    数组容量， 默认16

HashMap重要方法

---

1. hash

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

根据key的hashCode高位和低位异或得到，减少hash冲突的可能性。

• key为null时， hash为0， 也就是说key=null时， 一定存在table[0], 第一个链表中。

2. put

通过putVal方法将key-value添加到数组table中。

put.png

1. 根据key算出hash值。
2. 判断数组table 是否为空， 若为空，进行初始化。
3. 根据hash和数组table 容量大小异或， 找到数组指定下标table[i]。
4. 判断table[i]是否为空，若为空则初始化链表，直接插入key-value。
5. 判断key是否存在， 若存在，则直接覆盖旧值。
6. 判断当前链表是否是红黑树， 若是，则直接插入。
7. 遍历链表，判断链表长度是否>=8, 若大于，则将链表转换为红黑树， 并且若key值存在， 则覆盖旧值， 若key不存在
8. 4-7完成后， 增加修改次数modCount
9. 判断size是否大于临界值， 若大于临界值， 则调用resize方法扩容

3.Get

通过getNode方法从table中查找value。

1. 判断table是否为空， 若为空，返回null。
2. 根据hash和table容量异或获得数组下标， 判断指定下标链表是否为空， 若为空，返回null。
3. 判断链表第一位key与指定key是否相等，若相等，返回该value。
4. 遍历链表， 若链表为红黑树， 查找红黑树，若为链表， 查找链表，返回key或null。

4.Resize

对table进行扩容。

1. 根据旧的capacity和threshold, 得到新的capacity和threshold。
2. 构造新表， 初始化新表。
3. 遍历旧表， 将旧表的值重新hash, 填充到新表中。

实战问题

参考资料