HashMap 深入解析（一）

共两篇，本文是第一篇，包含前四节。

目录

1. 引言
2. 基本存储结构
3. Put 方法原理
4. Get 方法原理
5. 装填因子默认值及作用
6. HashMap 默认长度及原因
7. HashMap 的线程安全问题
8. Java8 中 HashMap 的优化
9. HashMap 和 HashSet 的关系
10. 线程安全的 HashMap：CurrentHashMap 简介

引言

  相信大多数人在面试的时候都会问到一个问题：你最常用的集合类有哪些？HashMap 你熟悉嘛？只要面试前稍微做点准备，我相信大部分人都能回答上来常用的集合类和各个集合类的特点和区别，至于 HashMap 的数据结构就不是那么多人了解了，更别说目录里的其他问题了。

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

以上是百度百科和 360 百科的解释，字太多不用看了，我会在下面一点一点说清楚的。

基本存储结构

  HashMap 以键值对的形式表现出来，一个键对应一个值，Key 和 Value 默认都是 Object 类型的，我们一般用 String 当 key。“HashMap”顾名思义它与 Hash 有不解的渊源。HashMap 首先会以 key 的 hashcode 为索引搜索键值对，所有 hashcode 是非常重要的！hashcode 是一个 int 值，hashCode() 方法是定义在 Object 中 native 方法，我之所以常用 String 当 Key 除了它符合我们的习惯之外，还因为 String 重写了 hashCode() 和 equals() 方法，如下

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

如果使用 == 我们自定义的对象当作 Key 的话，也需要重写 hashCode() 和 equals() 方法，特别是 equals() 方法 ==，它定义再 Object 中默认实现是 ==，必须重写！
  说到 == 和 equals() 的区别我不得不吐槽一下：面试了很多人，能说出 == 是对比对象地址的人特别多，但是说出来和 equals() 的默认实现是 == 的人很少，看一下 Object 的源码：

public boolean equals(Object obj) {
        return (this == obj);
    }

更有人只是知道 == 的概念但是根本就不知道如何应用,对比两个对象还是用 == 或者根本就不重写 equals()，吐槽完毕回归正文。
   通俗地讲，1.7 版本的 HashMap 是数组和单向链表的结合体，数组中存放 hashcode 不同的 Entry 对象，链表中存放 hashcode 相同的 Entry 对象。

Put 方法原理

第一步：

public V put(K key, V value) {
        // 如果是空数组则初始化数组
        if (table == EMPTY_TABLE) {
            // 该方法会在HashMap【默认长度及原因】详细分析
            inflateTable(threshold);
        }
        // key允许为null
        if (key == null)
            // 对key为null的特殊处理 放在数组的第一位
            return putForNullKey(value);
        // 下文介绍
        int hash = hash(key);
        // 根据hash值定位在数组中的索引,在【默认长度及原因】详细分析
        int i = indexFor(hash, table.length);
        // 查询再数组对应的链表中key是否存在 如果存在则替换原始值
        for (Entry<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;
            }
        }
        // 增加结构修改次数
        // 因为hashMap是线程不安全的，它作用是在迭代器中如果其他线程修改了hashMap的结构则立刻抛出异常快速失败即Fail-Fast机制
        modCount++;
        // 增加新的节点
        addEntry(hash, key, value, i);
        return null;
    }

第二步：

void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果当前大小达到或者大于临界值且当前索引不是空 则把远数组大小扩展一倍
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            // 重新计算在新数组中的索引
            bucketIndex = indexFor(hash, table.length);
        }
        // 创建新的节点
        createEntry(hash, key, value, bucketIndex);
    }

第三步：

// 创建新的Entry并替换掉在数组中的节点，添加在链表的头部，而不是添加链表的尾部
// 据说是因为最新插入的对象被查询的概率更高
void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

扩展数组

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        // 如果旧的数组已经达到最大限制 则不进行扩容 当然一般达不到
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        // 创建新的数组
        Entry[] newTable = new Entry[newCapacity];
        // 把旧数组中的链表头节点重新定位并放入新的数组中
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        // 根据装填因子因子重新计算临界值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

Get 方法原理

第一步：

public V get(Object key) {
        // 如果key是空则特殊处理
        if (key == null)
            // 从数组第一个节点的链表中查询
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

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

第二步：

final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
        
        int hash = (key == null) ? 0 : hash(key);
        // 根据key获得所在数组中的索引，并遍历该索引上的Entry链表
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            // 先判断hashcode 再判断值是否相同
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }