HashMap

Java 集合，也称作容器，主要是由两大接口 (Interface)派生出来的：Collection 和 Map。

Map集合体系：

Map集合特点： (1) 键值对存储(key-value),一个键值对是Map集合中一个元素 (2) 键：无序、无下标、元素不允许重复(唯一  因为key是用set集合存储的) (3) 值：无序、无下标、元素允许重复  （也是用集合存储的）

实现类

HashMap

探究HashMap是什么、能做什么以及一些操作原理。

HashMap是什么？

HashMap是由我们常用的数组+链表+红黑树（JDK1.8增加了红黑树）组合构成的数据结构。

HashMap的存储及扩容

存储

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。（其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合）。

数组里面每个地方都存了Key-Value这样的实例，在Java7叫Entry在Java8中叫Node，两者都为HashMap的内部类且都实现了Map.Entry接口。

下图中的每个黑色圆点就是一个Node对象：

（此图其实就是一个哈希表，哈希表有多种不同的实现方法，这里是最常用的一种方法—— 拉链法。通俗的讲就是hash+数组+链表的结合）

HashMap就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。例如程序执行下面代码：

数组的初始值为空，长度一定为2的幂次方（默认值为16）。在put插入的时候回根据key用hash函数去计算一个index（下标）值，例如：

map.put("1001","桃树");

hash("1001")=2//举例结果为2，真正结果不一定为2

系统将调用"1001"这个key的hashCode()方法得到其hashCode 值（该方法适用于每个Java对象），然后再通过Hash算法的后两步运算（高位运算和取模运算）来定位该键值对的存储位置，如果位置为空，则直接插入；如果不为空，即两个key定位到了相同的位置，此时表示发生了Hash碰撞。当发生Hash碰撞时，会在当前数组位置用链表存储新的键值对。原本键值对都在数组上，添加、查找等操作只需要一次寻址即可，当出现链表后，对于在链表上的键值对，添加等操作的时间复杂度会增加，变为O(n)。所以，考虑性能，Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。

那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。

注意：如果自定类型的对象作为HashMap的键，为了保证元素不重复(键)，则（键）对象对应的类需覆盖 hashCode和equals方法。但是为了提高检索的效率，开发时通常使用String/Integer(例如String的用户名或是Integer的id)作为HashMap的键 。 

扩容

java8之前是头插法，就是说新来的值会取代原有的值，原有的值就顺推到链表中去，在java8之后，都是所用尾部插入了。

在理解Hash和扩容流程之前，我们得先了解下HashMap的几个字段。从HashMap的默认构造函数源码可知，构造函数就是对下面几个字段进行初始化：

intthreshold;// 所能容纳的key-value对极限

finalfloatloadFactor;// 负载因子

intmodCount;

intsize;

首先，Node[] table（哈希桶数组）的初始化长度length。(initialCapacity ， 默认值是16)。

threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。

loadfactor为负载因子(默认值是0.75)。

在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子loadfactor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。对HashMap的优化就在于此，如果改得好，就实现了对HashMap的优化，如果改得不好，，，凉凉，，。因为默认的负载因子0.75是对空间和时间效率的一个平衡选择，所以，一般不建议不建议不建议修改。

size是HashMap中实际存在的键值对数量。（当size>length * loadfactor时会进行扩容）

modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

其中：threshold = length * loadfactor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

所以threshold就是在此loadfactor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。

扩容方式：将老数组中的数据逐个地遍历，计算，然后扔到新的扩容后的数组中。

staticintindexFor(inth,intlength) {// h 为key 的 hash值；length 是数组长度

returnh&(length-1);

    }

公式： index = h&(length-1)

PS：为什么不直接将原数组的数据直接复制到新数组而要麻烦的逐个计算再put进新数组？

因为扩容后，数组长度变了，所以同样的键计算出来的index也会发生变化，不再是原来的index值了，所以不能简单的复制。

模运算和高位运算：

模运算： h % length  （貌似刚开始的时候用的模运算，扩容的时候用的是高位运算）

高位运算：h & (length-1)（是二进制运算）（将原来的h和扩容后的length-1进行与运算（全为真才是真），如果左边新加的一位是0则元素还放到原来的位置，如果是1则放到新位置，新位置=原来位置+原来数组长度）

关于table长度必须为2的幂次方：

在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化。

        1.当长度为2时， h & (length-1) 的值会出现和 h % length 计算的结果是一样的情况，大大减少了之前已经散列良好的老数组的数据位置的重新调换。

        2.当数组长度为2的n次幂的时候，不同的key算得（高位运算）的index相同的几率较小，那数据在数组上分布也就比较均匀，即碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

put操作图解：

线程安全性

在多线程使用场景中，应该尽量避免使用线程不安全的HashMap（HashMap可能造成死循环），而使用线程安全的ConcurrentHashMap。

扩展

HashMap和HashTable 的异同？

二者的存储结构和解决冲突的方法都是相同的。

HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。

HashTable 中 key和 value都不允许为 null，而HashMap中key和value都允许为 null（key只能有一个为null，而value则可以有多个为 null）。但是如果在 Hashtable中有类似 put( null, null)的操作，编译同样可以通过，因为 key和 value都是Object类型，但运行时会抛出 NullPointerException异常。

Hashtable扩容时，将容量变为原来的2倍+1，而HashMap扩容时，将容量变为原来的2倍。

Hashtable计算hash值，直接用key的hashCode()，而HashMap重新计算了key的hash值，Hashtable在计算hash值对应的位置索引时，用 %运算，而 HashMap在求位置索引时，则用 &运算。

(ps:部分图片源于网络)