Java基础(一)-容器篇(Map专题)

Java基础(一)-容器篇(Map专题)

在上一篇章中，我们对Java的基本容器类有了一个比较全面的了解，Java为数据结构中的映射定义了一个借口java.util.Map。此借口主要有四个常用的实现类。分别是HashMap、HashTable、linkedHashMap和TreeMap。

一、HashMap、HashTable、linkedHashMap与TreeMap概述

(1) HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

(2) Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

(3) linkedHashMap：linkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历linkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

(4) TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

二、HashMap的基础实现

在JDk1.8前，HashMap是使用数组加链表的结构实现的。在JDK1.8中，HashMap使用数组+链表+红黑树来实现。其结构如下所示：

HashMap的Put方法

当调用HashMap的put方法时，HashMap会对输入的Key值进行哈希计算，用于确定该新增节点应该存储在数组的哪个位置。然而，HashMap的哈希算法可能会导致哈希冲突现象。当两个不同的Key值计算出来的HashCode相同时，HashMap会把新插入的节点插入到对应数组节点的链表中。需要注意的是在链表中插入新节点时采用的是头插法（HashMap的发明者认为新插入的Entry节点被查找的概率要高于旧节点）。

HashMap的Get方法

当调用HashMap的get方法时，HashMap会对输入的Key值进行哈希计算，得到对应Key值在数组中的存储下标（Index）。之后遍历该下标下的链表，找出key值对应的value并进行返回。

三、HashMap的结构优化 1、HashMap的Hash算法

在HashMap中，Hash算法能很大程度提高程序性能。一个好的Hash算法应该能使输入的Key进行Hash后尽可能分散，减少hash冲突。在JDK1.8中，其实现算法如下：

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

可以看见，若key值为null，其默认放置在索引为0的位置（不难理解为何HashMap仅允许一个键值为Null的记录）；若其key值不为null，会对输入Key进行三步 *** 作：

取key的hashCode值（hashCode使用C实现）；对hashKey进行高位运算；对计算结果进行取模，获取其在数组中的具体索引地址；

以下图片展示了其具体计算逻辑

如上图，由于进行取模运算时效率较低，Java把取模运算优化为&运算。即当数组长度length是2的整数次幂时，length - 1的二进制是一个全1的序列，此时对其进行取模和对其进行与运算结果相同。这也解释了为什么在对HashMap扩容时，其数组大小必须是2的整次幂。（若不为2的整次幂，其数组长度length - 1不为全1，此时做与运算会导致Hash值不能均匀分布，影响实际性能）。

2.HashMap的扩容机制

扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。下面结合1.7版本扩容代码进行介绍。

 void resize(int newCapacity) {   //传入新的容量
     Entry[] oldTable = table;    //引用扩容前的Entry数组
     int oldCapacity = oldTable.length;         
     if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
         threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
         return;
     }
  
     Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
     transfer(newTable);                         //！！将数据转移到新的Entry数组里
     table = newTable;                           //HashMap的table属性引用新的Entry数组
     threshold = (int)(newCapacity * loadFactor);//修改阈值
 }

可以看到，在扩容时主要分为几步：

创建一个新的Entry数组，其容量为原来旧容量的两倍（若已达到容量上限2^30，则不能继续扩容）；遍历旧数组，对旧数组元素重哈希（若发生冲突，则采用头插法插入链表中）；

在JDK1.8中做了一些优化，由于扩容是使用2次幂的扩展，因此元素重哈希的位置只有两种情况（1、在原地；2、在原来的位置移动二的次幂，结合&运算逻辑思考）。因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。

HashMap扩容时机

在HashMap中有一个元素loadFactory（负载因子），当数组的多于length*loadFactory个位置有元素时，会触发扩容。在初始化时，HashMap的默认容量大小是16，负载因子大小是0.75。

HashMap的线程安全性

在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap。由于在HashMap中进行 *** 作并没有进行锁控制，因此当有两个线程对同一个HashMap进行 *** 作时，若触发了HashMap的扩容 *** 作，可能导致链表中出现环，影响正常使用。

参考文献

java8系列之重新认识HashMap：https://tech.meituan.com/2016/06/24/java-hashmap.html

漫画：什么是HashMap：https://zhuanlan.zhihu.com/p/31610616

JDK8之最新改进,HashMap底层特性全解析：https://zhuanlan.zhihu.com/p/295019678