看完这篇 HashMap ，和面试官扯皮就没问题了（1）

HashMap 概述

「如果你没有时间细抠本文，可以直接看 HashMap 概述，能让你对 HashMap 有个大致的了解」。

HashMap 是 Map 接口的实现，HashMap 允许空的 key-value 键值对，HashMap 被认为是 Hashtable 的增强版，HashMap 是一个非线程安全的容器，如果想构造线程安全的 Map 考虑使用 ConcurrentHashMap。HashMap 是无序的，因为 HashMap 无法保证内部存储的键值对的有序性。

HashMap 的底层数据结构是数组 + 链表的集合体，数组在 HashMap 中又被称为桶(bucket)。遍历 HashMap 需要的时间损耗为 HashMap 实例桶的数量 + (key - value 映射) 的数量。因此，如果遍历元素很重要的话，不要把初始容量设置的太高或者负载因子设置的太低。

HashMap 实例有两个很重要的因素，初始容量和负载因子，初始容量指的就是 hash 表桶的数量，负载因子是一种衡量哈希表填充程度的标准，当哈希表中存在足够数量的 entry，以至于超过了负载因子和当前容量，这个哈希表会进行 rehash 操作，内部的数据结构重新 rebuilt。

注意 HashMap 不是线程安全的，如果多个线程同时影响了 HashMap ，并且至少一个线程修改了 HashMap 的结构，那么必须对 HashMap 进行同步操作。可以使用 Collections.synchronizedMap(new HashMap) 来创建一个线程安全的 Map。

HashMap 会导致除了迭代器本身的 remove 外，外部 remove 方法都可能会导致 fail-fast 机制，因此尽量要用迭代器自己的 remove 方法。如果在迭代器创建的过程中修改了 map 的结构，就会抛出 ConcurrentModificationException 异常。

下面就来聊一聊 HashMap 的细节问题。我们还是从面试题入手来分析 HashMap 。

HashMap 和 HashTable 的区别

我们上面介绍了一下 HashMap ，现在来介绍一下 HashTable

相同点

HashMap 和 HashTable 都是基于哈希表实现的，其内部每个元素都是 key-value 键值对，HashMap 和 HashTable 都实现了 Map、Cloneable、Serializable 接口。

不同点

• 父类不同：HashMap 继承了 AbstractMap 类，而 HashTable 继承了 Dictionary 类

• 线程安全性：HashMap 不是线程安全的，如果多个外部操作同时修改 HashMap 的数据结构比如 add 或者是 delete，必须进行同步操作，仅仅对 key 或者 value 的修改不是改变数据结构的操作。可以选择构造线程安全的 Map 比如 Collections.synchronizedMap 或者是 ConcurrentHashMap。而 HashTable 本身就是线程安全的容器。

• 性能方面：虽然 HashMap 和 HashTable 都是基于单链表的，但是 HashMap 进行 put 或者 get􏱤 操作，可以达到常数时间的性能；而 HashTable 的 put 和 get 操作都是加了 synchronized 锁的，所以效率很差。

• 初始容量不同：HashTable 的初始长度是11，之后每次扩充容量变为之前的 2n+1（n为上一次的长度）

而 HashMap 的初始长度为16，之后每次扩充变为原来的两倍。创建时，如果给定了容量初始值，那么HashTable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。

HashMap 和 HashSet 的区别

也经常会问到 HashMap 和 HashSet 的区别

HashSet 继承于 AbstractSet 接口，实现了 Set、Cloneable,、java.io.Serializable 接口。HashSet 不允许集合中出现重复的值。HashSet 底层其实就是 HashMap，所有对 HashSet 的操作其实就是对 HashMap 的操作。所以 HashSet 也不保证集合的顺序。

HashMap 底层结构

要了解一个类，先要了解这个类的结构，先来看一下 HashMap 的结构：

最主要的三个类(接口)就是 HashMap,AbstractMap和 Map 了，HashMap 我们上面已经在概述中简单介绍了一下，下面来介绍一下 AbstractMap。

AbstractMap 类

这个抽象类是 Map 接口的骨干实现，以求最大化的减少实现类的工作量。为了实现不可修改的 map，程序员仅需要继承这个类并且提供 entrySet 方法的实现即可。它将会返回一组 map 映射的某一段。通常，返回的集合将在AbstractSet 之上实现。这个set不应该支持 add 或者 remove 方法，并且它的迭代器也不支持 remove 方法。

为了实现可修改的 map，程序员必须额外重写这个类的 put 方法(否则就会抛出UnsupportedOperationException)，并且 entrySet.iterator() 返回的 iterator 必须实现 remove() 方法。

Map 接口

Map 接口定义了 key-value 键值对的标准。一个对象支持 key-value 存储。Map不能包含重复的 key，每个键最多映射一个值。这个接口代替了Dictionary 类，Dictionary是一个抽象类而不是接口。

Map 接口提供了三个集合的构造器，它允许将 map 的内容视为一组键，值集合或一组键值映射。map的顺序定义为map映射集合上的迭代器返回其元素的顺序。一些map实现，像是TreeMap类，保证了map的有序性；其他的实现，像是HashMap，则没有保证。

重要内部类和接口

Node 接口

Node节点是用来存储HashMap的一个个实例，它实现了 Map.Entry接口，我们先来看一下 Map中的内部接口 Entry 接口的定义

Map.Entry

// 一个map 的entry 链，这个Map.entrySet()方法返回一个集合的视图，包含类中的元素，
// 这个唯一的方式是从集合的视图进行迭代，获取一个map的entry链。这些Map.Entry链只在
// 迭代期间有效。
interface Entry<K,V> {
  K getKey();
  V getValue();
  V setValue(V value);
  boolean equals(Object o);
  int hashCode();
}

Node 节点会存储四个属性，hash值，key，value，指向下一个Node节点的引用

// hash值

因为Map.Entry 是一条条entry 链连接在一起的，所以Node节点也是一条条entry链。构造一个新的HashMap实例的时候，会把这四个属性值分为传入

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

实现了 Map.Entry 接口所以必须实现其中的方法，所以 Node 节点中也包括上面的五个

方法

KeySet 内部类

keySet 类继承于 AbstractSet 抽象类，它是由 HashMap 中的 keyset() 方法来创建 KeySet 实例的，旨在对HashMap 中的key键进行操作，看一个代码示例

图中把「1, 2, 3」这三个key 放在了HashMap中，然后使用 lambda 表达式循环遍历 key 值，可以看到，map.keySet() 其实是返回了一个 Set 接口，KeySet() 是在 Map 接口中进行定义的，不过是被HashMap 进行了实现操作，来看一下源码就明白了

// 返回一个set视图，这个视图中包含了map中的key。
public Set<K> keySet() {
  // // keySet 指向的是 AbstractMap 中的 keyset
  Set<K> ks = keySet;
  if (ks == null) {
    // 如果 ks 为空，就创建一个 KeySet 对象
    // 并对 ks 赋值。
    ks = new KeySet();
    keySet = ks;
  }
  return ks;
}

所以 KeySet 类中都是对 Map中的 Key 进行操作的：

​

Values 内部类

Values 类的创建其实是和 KeySet 类很相似，不过 KeySet 旨在对 Map中的键进行操作，Values 旨在对key-value 键值对中的 value 值进行使用，看一下代码示例：

循环遍历 Map中的 values值，看一下 values() 方法最终创建的是什么：

public Collection<V> values() {
  // values 其实是 AbstractMap 中的 values
  Collection<V> vs = values;
  if (vs == null) {
    vs = new Values();
    values = vs;
  }
  return vs;
}

所有的 values 其实都存储在 AbstractMap 中，而 Values 类其实也是实现了 Map 中的 Values 接口，看一下对 values 的操作都有哪些方法

其实是和 key 的操作差不多

EntrySet 内部类

上面提到了HashMap中分别有对 key、value 进行操作的，其实还有对 key-value 键值对进行操作的内部类，它就是 EntrySet，来看一下EntrySet 的创建过程：

点进去 entrySet() 会发现这个方法也是在 Map 接口中定义的，HashMap对它进行了重写

// 返回一个 set 视图，此视图包含了 map 中的key-value 键值对
public Set<Map.Entry<K,V>> entrySet() {
  Set<Map.Entry<K,V>> es;
  return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

如果 es 为空创建一个新的 EntrySet 实例，EntrySet 主要包括了对key-value 键值对映射的方法，如下