Java基础之HashMap.md

概念

HashMap 基于 Map 接口实现，元素以键值对的方式存储，并且允许使用 null 键和 null 值，因为 key 不允许重复，因此只能有一个键为 null， HashMap 不能保证放入元素的顺序，它是无序的，和放入的顺序并不能相同。HashMap 是线程不安全的。

注：有序存储键值对数据时，可以使用 LinkedHashMap；要保证线程安全时，可以使用 ConcurrentHashMap。

实现机制

HashMap 由数组和链表来实现对数据的存储。HashMap 采用 Entry 数组来存储键值对，每一个键值对组成了一个 Entry 实体，Entry 类实际上是一个单向的链表结构，它具有 Next 指针，可以连接下一个 Entry 实体，以此来解决 Hash 冲突的问题。

1. 数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：查找容易，插入和删除困难。
2. 链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O(N)。链表的特点是：查找困难，插入和删除容易。

注：HashMap 里面实现一个静态内部类 Entry，其重要的属性有 hash，key，value，next。

HashMap 存储规则：每个元素存储的是一个链表的头结点。那么一个长度16的数组中，元素是按照什么规则存放到数组中呢。是通过元素的 key 的哈希值（key 的 hashcode 进行二次 hash）对数组长度 - 1的位运算得到存储位置的下标。比如哈希值8（8 & (16 - 1) = 8）、12（12 & (16 - 1) = 12）、40（40 & (16 - 1) = 8）、140（140 & (16 - 1) = 12），所以8和40存储在数组下标为8的位置；12和140存储在数组下标为12的位置。

HashMap 链式数据结构：Entry 类中有一个 next 属性，指向下一个 Entry。比如第一个键值对A进来，通过计算其 key 的 hash 得到的index = 0，记做：Entry[0] = A；此时又有一个键值对B进来，通过计算得到的index也等于0，此时 HashMap 会使得Entry[0] = B，B.next = A；若这时又进来一个键值对C，同样的index等于0，此时 HashMap 会使得Entry[0] = C，C.next = B；index = 0的位置存储了A、B、C三个键值对，它们之间通过 next 这个属性链接在一起，所以数组中存储的是最后插入的元素，先插入的元素终会被放到Entry链的尾部，这里你也就明白为什么 HashMap 是无序的了吧。

扩容机制

添加元素时，会判断当前元素个数，当大于等于阈值（数组的长度 * 加载因子的值）时，就会自动扩容。扩容就是重新计算容量，但是 Java 中数组是无法自动扩容的，所以需要新的数组代替已有的容量小的数组。

比如长度为16的数组，加载因子为0.75，则阈值为 16 * 0.75 = 12，也就是说当元素个数达到12，在添加第13个元素时会进行扩容。即 16 * 2 = 32，那么扩容后的容量是32。这里先抛出一个问题，为什么每次扩容都在原有容量乘以2，继续往下看。

注：HashMap 使用的是懒加载，构造完 HashMap 对象后，只要不进行 put 方法插入元素之前，HashMap 并不会去初始化或者扩容。

问题：为什么容量大小为2的n次幂效率最好？

& 1111	8	9	8	9
hashcode值	1 0 0 0	1 0 0 1	1 0 0 0	1 0 0 1
数组长度 - 1	1 1 1 1	1 1 1 1	1 1 1 0	1 1 1 0
结果	1 0 0 0	1 0 0 1	1 0 0 0	1 0 0 0

如上表，左边两组是数组长度为16(2的4次幂)，右边两组是数组长度为15。两组的 hashcode 均为8 和 9，然而与 1110 做位运算时，产生相同的结果，也是会存储到数组的同一个位置上，这就产生了碰撞，8 和 9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，降低了查询的效率。我们还可以发现，当数组长度为15的时候，hashcode 的值会与14（1110）进行位运算，最后一位永远是0，那 0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素，浪费空间。数组可使用的位置比数组长度小很多，这样会增加碰撞的几率，减慢查询的效率。

数组长度为2的n次幂的时候，不同的 key 算得的 index 相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了，所以在存储大容量数据时，最好预先指定容量大小为2的n次幂（其实不指定为2的n次幂的话，HashMap也会以大于且最接近指定值大小的2的n次幂进行初始化），也解释了上面问题，为什么 HashMap 每次扩容都在原有容量上乘以2。

扩容是一个特别耗性能的操作，所以在使用 HashMap 的时候，估算 map 的大小，初始化的时候给一个大致的数值，避免 map 进行频繁的扩容。那么这个数值多少才是最合适的值呢，下面看一个例子。

例：假如有1000个元素需要存储到 HashMap 中，那么根据上面提到的容量大小为2的n次幂效率最好，那么 new HashMap(1024) 是比较合适的，但是上面也提到了，当存储元素达到阈值时，HashMap 会进行扩容，那么1024 * 0.75 < 1000，所以为了不进行扩展，需要size * 0.75 > 1000，那么可以得出 new HashMap(2048) 才是最合适的。

重写 hashcode 和 equals 方法

疑问：为什么要重写 hashcode 和 equals 方法？

根据上面介绍，我们知道想查找某个元素，就需要先获取其所在位置，那么首先计算 key 的 hashcode，找到其在数组中对应的位置，然后通过 key 的 equals 方法在对应位置的链表中找到元素。因此 hashcode 与 equals 方法对于找到对应元素是两个关键方法。

重写 equals 方法需要满足三个条件：

1. 自反性：a.equals(a) == true。
2. 对称性：a.equals(b) == true时，b.equals(a) 也为 true。
3. 传递性：a.equals(b) == true时，且b.equals(c) == true，那么 a.equals(c) 也要为 true。

JDK 1.8 优化

以上都是基于 JDK 1.7 进行分析的，JDK 1.8 在 HashMap 实现方式上做了一些优化。数据结构的存储由数组+链表的方式，变化为数组+链表+红黑树的存储方式，当链表长度超过阈值（8）时，将链表转换为红黑树。性能上有了提升。