一、容器之 Map 汇合

汇合体系的源码中，Map 中的 HashMap 的设计堪称最经典，波及数据结构、编程思维、哈希计算等等，在日常开发中对于一些源码的思维进行参考借鉴还是很有必要的。

• 根底：元素增查删、容器信息；
• 进阶：存储构造、容量、哈希；

API 体系

在整个 Map 和 Set 的 API 体系中，最重要的就是 HashMap 的实现原理：

• HashMap：基于哈希表治理元素；
• LinkedHashMap：基于 HashMap 和双向链表；
• HashSet：底层保护 HashMap 构造；
• LinkedHashSet：继承 HashSet，双向链表；

所以 Map 和 Set 的系列中，除非凡 API 之外，基本原理都依赖 HashMap，只是在各自具体实现时，实用于不同特点的元素治理。

二、数据结构

在看 HashMap 之前，先了解一种数据结构：数组 + 链表的构造。

基于数组治理元素的地位，元素的存储造成链表构造，既然是链表那么就能够是单双向的构造，这须要针对具体的 API 去剖析，通过这个构造能够失去几个要害信息：

• 扩容：基于数组则面对扩容问题；
• 链表：造成链表构造的机制；
• 哈希：哈希值计算与抵触解决；

三、HashMap 详解

1、构造封装

既然下面简略形容了数组 + 链表的构造，那么从源码角度看看是如何封装的：

transient Node<K,V>[] table;

在 HashMap 中数组构造的变量命名为 table（表），并且是基于 Node<K,V> 的节点：

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

实现 Map.Entry 接口，并定义节点的构造变量，和节点本身的相干办法。

2、构造方法

在晓得 HashMap 中的根底构造后，能够看其相干的构造方法，初始化哪些变量：

无参结构

public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR;}

• float DEFAULT_LOAD_FACTOR = 0.75f;
• this.loadFactor = DEFAULT_LOAD_FACTOR;

实际上还要关注一个外围参数：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

即数组默认的初始化容量 DEFAULT_INITIAL_CAPACITY 为 16，扩容的阈值 loadFactor 为 0.75，即示意当数组中元素达到 12 个便会进行扩容操作。

有参结构

当然也能够通过有参构造方法去设置两个参数：即容量和扩容的阈值：

public HashMap(int initialCapacity, float loadFactor) ;

通过两个构造方法的源码可知：当间接创立新的 HashMap 的时候，不会立刻对哈希数组进行初始化，然而能够对要害变量做自定义设置。

3、装载元素

顺着 HashMap 的应用办法，看元素增加：

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

在 put 的时候并没有做过多间接操作，而是调用两个要害办法：

• hash()：计算 key 的 hash 值；
• putVal()：元素增加过程；

这里必须看一个要害办法，哈希值的计算：

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

并不是间接获取 Object 中 hashCode 的返回值，计算 key 对应的 hashCode 值，和 hashCode 值右移 16 位的值，并对两个后果进行异或运算，以此拉低哈希抵触产生的概率。

再看 putVal() 办法，这里的操作就相当精彩：

外围步骤总结：

• 首次执行判断并初始化底层数组；
• 基于哈希值计算结果增加元素；
• 依据增加元素后的容量来判断是否扩容；

这里还须要阐明一个问题：

HashMap 基于红黑树来解决哈希抵触问题，如果 hash 抵触过多，对 O(n)的查问性能的影响十分大，当抵触节点链表的抵触元素数量达到 8 时，并且数组的长度达到 64 时，会应用红黑树结构代替链表来解决哈希抵触的查问性能问题，对于树结构能够移步之前的相干文章。

4、自动化扩容

容器在肯定边界内能够一直增加元素，其外围的机制就是扩容，HashMap 的扩容遵循最小可用准则，当然容量达到阈值，便会触发主动扩容机制。

阈值：threshold=capacity*loadFactor，默认即 16*0.75=12。

外围办法：resize；

外围步骤总结：

• 判断扩容的边界参数：threshold；
• 外围参数计算：容量和阈值；
• 基于新参数创立一个新的空数组；
• 原数组为 null 则过程能够了解为初始化；
• 原数组不为 null 则扩容并迁徙数据；

很显然如果波及数组扩容则会很影响效率，所以在日常开发中，能够在应用 HashMap 的时候事后预计好 HashMap 的大小，保障阈值大于存储的元素数量，尽可能防止进行屡次扩容操作。

5、查问元素

getNode查找办法，通过 hash 值的计算，而后顺次通过数组、红黑树、链表进行遍历查问：

6、删除元素

removeNode删除办法，首先通过 hash 值的计算，找到要删除的节点，而后判断索引地位是红黑树还是链表构造，别离执行各自的删除流程：

7、补充阐明

这里对两个办法做个简略的阐明：hashCode()与equals()，通常来说重写 equals 办法的时候须要重写 hashCode 办法。

这两个办法都能够用来比拟两个对象是否相等，然而 hash 值有存在抵触的状况，可能存在两个对象的 hash 值抵触，这时候能够通过 equals 判断对象值是否雷同，==判断值对象，地址判断援用对象。

在 HashMap 的构造中，链表上的 hash 值雷同状况还要通过 equals 办法来判断具体值是否雷同，能力找到相应的对象。

四、源代码地址

GitHub·地址
https://github.com/cicadasmile/java-base-parent
GitEE·地址
https://gitee.com/cicadasmile/java-base-parent

浏览标签

【Java 根底】【设计模式】【构造与算法】【Linux 零碎】【数据库】

【分布式架构】【微服务】【大数据组件】【SpringBoot 进阶】【Spring&Boot 根底】

【数据分析】【技术导图】【职场】