1. HashMap原理
1.1 HashMap的容量
HashMap中使用数组作为存储元素的桶，对应的内部属性为table，如下图所示。HashMap的内部数组不是在创建HashMap对象时初始化，而是在首次存入元素时进行初始化，以减少对内存的占用。
从源码注释中我们可以发现，官方规定table的长度总是2的幂，即2的N次方。这样设计的原因是为了保证HashMap的速度足够快。
我们知道，不论存操作还是取操作，HashMap都使用除留取余法通过key的哈希值计算key在桶中的索引。如果能优化这一计算的速度，将会大幅优化HashMap存取操作的速度。
在数学中有这样一条公式：X % 2^n = X & (2^n - 1) 。简单的说，当X对Y取余时，如果Y是2的幂，则可以将取余运算转换为位运算，以提高计算速度。
综上，HashMap的容量始终是2的幂，以保证内部高效的哈希运算。
1.2 HashMap的初始容量
与ArrayList相似，HashMap的初始容量分为默认容量和手动指定两种情况。
当使用无参构造器创建HashMap对象时，table的初始化长度为16，由如下的静态常量指定。
因此，默认情况下，HashMap的默认容量为16。
HashMap支持使用带参构造器HashMap(int initialCapacity)来创建HashMap对象，并指定内部数组的初始化长度。
此处需要注意，HashMap并不会直接使用开发者指定的长度作为内部数组的长度，而是会通过一个内部方法，计算大于开发者指定长度的最小的2的幂作为内部数组的长度。
例如：
因此，当开发者指定初始长度时，HashMap的容量为大于该长度的最小的2的幂。
1.3 HashMap的扩容
HashMap中提供了桶的自动扩容机制，在满足特定的条件时自动将桶的长度扩容到原来的两倍。
想要理解桶的扩容条件，需要先分清楚4个概念：
- 1、容量（capacity）：HashSet内部数组的长度，默认长度为16
- 2、大小（size）：HashSet中实际存储的元素的个数，默认为0
- 3、负载因子（loadFactor）：用来衡量HashSet“满”的程度，默认值为0.75f
- 4、临界值（threshold）：当size超过临界值时，HashSet将会扩容，threshold = capacity * loadFactor
对于一个默认的HashSet来说，临界值=16 * 0.75 = 12，即当存储了超过12个元素时，HashSet会自动扩容，将容量扩大到原来的2倍，即32。
扩容后，还会对所有的元素进行一次rehash操作，相当于对所有的元素重新做一遍Hash运算，是一项比较耗时的操作。
由于存在上述的设计，因此开发者手动指定HashMap的初始容量时，需要计算合适的容量，而不是直接传入要存储元素的个数。具体可参考《阿里巴巴 Java开发手册》中的建议。
1.4 树化与退化
HashMap中使用链地址法处理Hash冲突，当桶中某个位置的链表过长时，会响查询效率的情况。
自Java 8开始，HashMap在解决哈希冲突时引入了红黑树的应用，以提高查找操作的效率。当链表长度大于等于阈值（默认为8），同时HashMap容量已达到64时，链表会转换为红黑树，从而减少查找操作的时间复杂度，这个过程称为树化（Treeify）。
树化的2个阈值由HashMap内部的静态常量指定。
红黑树是一种自平衡的二叉搜索树，它具有良好的平衡性能和较快的查找、插入和删除操作的时间复杂度。相比于链表，红黑树在大型哈希桶中可以提供更快的查找速度。
同时，当红黑树中的节点数量减少到一定程度（默认为6）时，HashMap会将红黑树转换回链表。这个过程称为退化（Untreeify）。退化的阈值同样由HashMap内部的静态常量指定：
2. LinkedHashMap
2.1 LinkedHashMap概述
HashMap虽然提供了高效的添加和查询功能，但是无法保存元素的添加顺序。在一些特定的应用场景中，可能需要保存键值对的添加顺序，此时可以使用LinkedHashMap来实现。
例如：项目既需要提供按用户名快速查询用户信息的功能，也需要提供按用户签到顺序显示用户信息列表的功能。此时需要能够记载元素的添加顺序。
LinkedHashMap是在HashMap的基础上维护了一个Entry的双向链表，以此记录元素之间的先后顺序。
2.2 LinkedHashMap示例
编写代码，测试LinkedHashMap的遍历。代码示意如下：
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
public class LinkedHashMapDemo {
public static void main(String[] args) {
LinkedHashMap<Integer,String> map = new LinkedHashMap<>();
// 存放元素，以键值对形式
map.put(5, "Tom");
map.put(3, "Jerry");
map.put(9, "Lucy");
// 通过entrySet方法遍历
Set<Map.Entry<Integer,String >> entrySet = map.entrySet();
for(Map.Entry<Integer,String> entry:entrySet){
System.out.println("key: " + entry.getKey()+" value: " + entry.getValue());
}
}
}
