HashMap

HashMap 基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

扩容倍数是多少

原先数组的两倍（始终保持以 2 的整数幂增长）

底层数据结构

1.8 采用的是 数组+链表+红黑树构成

1.7 采用的是 数组+链表

如何处理 hash 冲突

• 链表法

将相同 hash 值的对象组织成一个链表放在 hash 值对应的槽位

• 开放地址法

是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位

• 建立公共溢出区

将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中

• 再哈希法

当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止

HashMap 底层是通过链表来解决 hash 冲突的

如何计算一个 key 的 hash 值

1.8 使用 key 的 hashCode 高 16 位和低 16 位异或（1 次位运算+1 次异或），变相的让高位数据参与到计算中，增加 hash 值的随机性

1.7 9 次扰动处理=4 次位运算+5 次异或

数组长度为什么是 2 的幂次方

1. 当数组长度为 2 的幂次方时，可以使用位运算来计算元素在数组中的下标，提高运算效率

2. 增加 hash 值的随机性，减少 hash 冲突

为什么 table 数组容量大于等于 64 才树化

因为当 table 数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化

链表转换成红黑树的条件

• 链表长度大于等于 8

• table 数组长度大于等于 64

如何计算 key 所对应的索引

 (n - 1) & hash （相当于对数组长度取模，这里用位运算进行了优化）

在什么地方会用到 tableSizeFor 方法

在构造方法里面调用该方法来设置 threshold

查找过程（1.8）

1. 根据 key 的 hashCode 计算 hash 值

2. 根据 hash 值计算下标（hash & n-1）

3. 判断 hash 值和 equals 方法，若相等，则根据节点类型查找 value：若是 TreeNode，则调用红黑树查找；若是链表，则遍历链表

插入过程（1.8）

1. 当 table 数组为空时，通过扩容的方式初始化 table

2. 通过计算键的 hash 值求出下标后，若该位置上没有元素(没有发生 hash 冲突)，则新建 Node 节点插入

3. 若发生了 hash 冲突，遍历链表查找要插入的 key 是否已经存在，存在的话根据条件判断是否用新值替换旧值

4. 如果不存在，则将元素插入链表尾部，并根据链表长度决定是否将链表转为红黑树

5. 判断键值对数量是否大于阈值，大于的话则进行扩容操作

扩容的过程（1.8）

HashMap 每次扩容都是建立一个新的 table 数组，长度和容量阈值都变为原来的两倍，然后把原数组元素重新映射到新数组上，具体步骤如下：

1. 首先会判断 table 数组长度，如果大于 0 说明已被初始化过，那么按当前 table 数组长度的 2 倍进行扩容，阈值也变为原来的 2 倍

2. 若 table 数组未被初始化过，且 threshold(阈值)大于 0 说明调用了 HashMap(initialCapacity, loadFactor) 构造方法，那么就把数组大小设为 threshold

3. 若 table 数组未被初始化，且 threshold 为 0 说明调用 HashMap() 构造方法，那么就把数组大小设为 16，threshold 设为 16*0.75

4. 接着需要判断如果不是第一次初始化，那么扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去，如果节点是红黑树类型的话则需要进行红黑树的拆分

注意：在 JDK1.8 HashMap 扩容阶段重新映射元素时不需要像 1.7 版本那样重新去一个个计算元素的 hash 值，而是通过 hash & oldCap 的值来判断，若为 0 则索引位置不变，不为 0 则新索引=原索引+旧数组长度，原因如下：

因为使用的是 2 次幂的扩展(指长度扩为原来 2 倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动 oldCap 的位置。因此，在扩充 HashMap 的时候，不需要像 JDK1.7 的实现那样重新计算 hash，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成“原索引 + oldCap”

为什么 HashMap 中的 key 需要重写 equals() 和 hashCode() 方法

• 原生的 equals 方法是使用 == 来比较对象的地址

• 原生的 hashCode 值是根据内存地址换算出来的一个值

hashCode()和 equals()方法是用于自定义比较两个对象是否是同一个对象的

HashMap 中 hash()可以确定的 key 的位置，使用 hash 值和 equals() 进一步判断 key 是否相同，实质上可以准确的判断 HashMap 中是否存在一个 key

HashMap 是线程不安全的，其主要体现哪里

1. 在 jdk1.7 中，在多线程环境下，扩容时会造成环形链或数据丢失

2. 在 jdk1.8 中，在多线程环境下，会发生数据覆盖的情况

负载因子的作用

其默认值为 0.75，这是时间和空间成本上一种折衷：

若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.链表长度会越来越长,查找效率降低。反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.表中的数据将过于稀疏（很多空间还没用，就开始扩容了）

如果机器内存足够，并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机器内存紧张，并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它，让它取默认值 0.75 就好了

为什么 int，String 适合最为 key

int 和 String 的好处在于 hash 出来的值不会改变。如果是一个对象，那么他们可能会因为内部引用的改变而 hashCode 值的改变，会导致存储重复的数据或找不到数据的情况。

HashMap 为什么不直接使用对象的原始 hash 值呢

通过移位和异或运算，可以让 hash 变得更复杂，进而影响 hash 的分布性。

既然红黑树那么好，为啥 hashmap 不直接采用红黑树，而是当大于 8 个的时候才转换红黑树

因为红黑树需要进行左旋，右旋操作， 而单链表不需要。

以下都是单链表与红黑树结构对比。

如果元素小于 8 个，查询成本高，新增成本低。

如果元素大于 8 个，查询成本低，新增成本高。

为什么要用红黑树，而不用平衡二叉树

插入效率比平衡二叉树高，查询效率比普通二叉树高。所以选择性能相对折中的红黑树。

jdk7 和 jdk8 之间的区别

1.7 中采用数组+链表，1.8 采用的是数组+链表/红黑树，即在 1.8 中链表长度超过一定长度后就改成红黑树存储。 

1.7 扩容时需要重新计算哈希值和索引位置，1.8 并不重新计算哈希值，巧妙地采用 hash 值 & oldCap 来计算新的索引位置：0 表示位置不变，非 0 表示位置移动到 原先位置 + oldCap 处。

1.7 是采用表头插入法插入链表，1.8 采用的是尾部插入法。 

在 1.7 中采用表头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题；在 1.8 中采用尾部插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题

1.7 中使用的结构是 Entry，1.8 使用的是 Node(实际继承了 Entry)

1.7 hash 函数使用的是 9 次扰动: 4 次位运算+5 次异或，1.8 hash 函数使用的是两次扰动：1 次按位异或 + 1 次无符号右移

HashMap 和 HashTable 有什么区别

• HashMap 是线程不安全的，HashTable 是线程安全的；

• 由于线程安全，所以 HashTable 的效率比不上 HashMap；

• HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null，而 HashTable 不允许；

• HashMap 默认初始化数组的大小为 16，HashTable 为 11，前者扩容时，扩大两倍，后者扩大两倍+1；

• HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode

Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是线程安全，它与 HashTable 在线程同步上有什么不同

ConcurrentHashMap 类（是 Java 并发包 java.util.concurrent 中提供的一个线程安全且高效的 HashMap 实现）。

HashTable 是使用 synchronize 关键字加锁的原理（就是对对象加锁）；

而针对 ConcurrentHashMap，在 JDK 1.7 中采用 分段锁的方式；JDK 1.8 中直接采用了 CAS（无锁算法）+ synchronized。

LinkedHashMap，TreeMap 有什么区别

• LinkedHashMap 保存了记录的插入顺序，在用 Iterator 遍历时，先取到的记录肯定是先插入的；遍历比 HashMap 慢；

• TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序（默认按键值升序排序，也可以指定排序的比较器）

HashMap & TreeMap & LinkedHashMap 使用场景

一般情况下，使用最多的是 HashMap。

• HashMap：在 Map 中插入、删除和定位元素时；

• TreeMap：在需要按自然顺序或自定义顺序遍历键的情况下；

• LinkedHashMap：在需要输出的顺序和输入的顺序相同的情况下。

HashMap & ConcurrentHashMap 的区别

除了加锁，原理上无太大区别。另外，HashMap 的键值对允许有 null，但是 ConCurrentHashMap 都不允许。