第6节：Java基础 - 三大集合（上)

本小节是Java基础篇章的第四小节，主要介绍Java中的常用集合知识点，涉及到的内容包括Java中的三大集合的引出，以及HashMap，Hashtable和ConcurrentHashMap。

三大集合接口的引出

Java中的集合，从上层接口上看分为了两类，Map和Collection。也就是说，我们平时接触到的常用的集合，包括HashMap，ArrayList和HashSet等都直接或者间接的实现了这两个接口之一。而Collection接口的子接口又包括了Set和List接口。这样我们常见的Map，Set和List三大集合接口就出来了。接口类图如下所示：

Map，List和Set都是Collection的子接口吗？

Map是和Collection并列的集合上层接口，没有继承关系；List和Set是Collection的子接口。

（1）Java中常见的集合

Java中的常见集合可以概括如下。

• Map接口和Collection接口是所有集合框架的父接口

• Collection接口的子接口包括：Set接口和List接口

• Map接口的实现类主要有：HashMap、TreeMap、Hashtable、LinkedHashMap、ConcurrentHashMap以及Properties等

• Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等

• List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等

（2）HashMap和Hashtable的区别有哪些？

HashMap和Hashtable之间的区别可以总结如下。

• HashMap没有考虑同步，是线程不安全的；Hashtable使用了synchronized关键字，是线程安全的；

• HashMap允许null作为Key；Hashtable不允许null作为Key，Hashtable的value也不可以为null

解析：

这个算是针对HashMap的一个开胃小菜，既然说出了线程安全和不安全的区别，会接着考察线程安全的具体含义，如下所示：

HashMap是线程不安全的，可以举一个例子

• HashMap线程不安全主要是考虑到了多线程环境下进行扩容可能会出现HashMap死循环

• Hashtable线程安全是由于其内部实现在put和remove等方法上使用synchronized进行了同步，所以对单个方法的使用是线程安全的。但是对多个方法进行复合操作时，线程安全性无法保证。 比如一个线程在进行get操作，一个线程在进行remove操作，往往会导致下标越界等异常。

既然说到了这里，那么我们来看看大家一直想说的Java集合快速失败（fast-fail）机制是怎么回事儿吧~

Java集合中的快速失败（fast-fail）机制

快速失败是Java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast。

例如：

假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就可能会抛出 ConcurrentModificationException异常，从而产生fast-fail快速失败。

那么快速失败机制底层是怎么实现的呢？

迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedModCount值，是的话就返回遍历；否则抛出异常，终止遍历。JDK源码中的判断大概是这样的：

（3）HashMap底层实现结构有了解吗？

HashMap底层实现数据结构为数组+链表的形式，JDK8及其以后的版本中使用了数组+链表+红黑树实现，解决了链表太长导致的查询速度变慢的问题。大概结构如下图所示：

HashMap的初始容量，加载因子，扩容增量是多少？

HashMap的初始容量16，加载因子为0.75，扩容增量是原容量的1倍。如果HashMap的容量为16，一次扩容后容量为32。HashMap扩容是指元素个数（包括数组和链表+红黑树中）过了16*0.75=12之后开始扩容。

HashMap的长度为什么是2的幂次方？

• 我们将一个键值对插入HashMap中，通过将Key的hash值与length-1进行&运算，实现了当前Key的定位，2的幂次方可以减少冲突（碰撞）的次数，提高HashMap查询效率

• 如果length为2的幂次方，则length-1 转化为二进制必定是11111……的形式，在与h的二进制与操作效率会非常的快，而且空间不浪费

• 如果length不是2的幂次方，比如length为15，则length-1为14，对应的二进制为1110，在与h与操作，最后一位都为0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。

接下来，我们来做一个简单的总结：

总结：

也就是说2的N次幂有助于减少碰撞的几率，空间利用率比较大。这样你就明白为什么第一次扩容会从16 ->32了吧？总不会再说32+1=33或者其余答案了吧？至于加载因子，如果设置太小不利于空间利用，设置太大则会导致碰撞增多，降低了查询效率，所以设置了0.75。

上边介绍了HashMap在存储空间不足的时候会进行扩容操作。那么，我们接着来看HashMap中的存储和扩容等相关知识点吧。

HasMap的存储和获取原理：

当调用put()方法传递键和值来存储时，先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象，也就是找到了该元素应该被存储的桶中（数组）。当两个键的hashCode值相同时，bucket位置发生了冲突，也就是发生了Hash冲突，这个时候，会在每一个bucket后边接上一个链表（JDK8及以后的版本中还会加上红黑树）来解决，将新存储的键值对放在表头（也就是bucket中）。

当调用get方法获取存储的值时，首先根据键的hashCode找到对应的bucket，然后根据equals方法来在链表和红黑树中找到对应的值。

HasMap的扩容步骤：

HashMap里面默认的负载因子大小为0.75，也就是说，当Map中的元素个数（包括数组，链表和红黑树中）超过了16*0.75=12之后开始扩容。将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。

但是，需要注意的是在多线程环境下，HashMap扩容可能会导致死循环。

前面我们介绍了在HashMap存储的时候，会发生Hash冲突，那么我们一起来看Hash冲突的解决办法吧。

解决Hash冲突的方法有哪些？

• 拉链法 （HashMap使用的方法）

• 线性探测再散列法

• 二次探测再散列法

• 伪随机探测再散列法

哪些类适合作为HashMap的键？

String和Interger这样的包装类很适合做为HashMap的键，因为他们是final类型的类，而且重写了equals和hashCode方法，避免了键值对改写，有效提高HashMap性能。为了计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashCode的话，那么就不能从HashMap中找到你想要的对象。

扩展知识点：

在高级的算法中，还有一个一致性Hash算法，有能力和精力的同学可以去研究下“一致性Hash算法”，有所了解一致性Hash算法对于面试是一个很好的加分点。

（4）ConcurrentHashMap和Hashtable的区别？

ConcurrentHashMap结合了HashMap和Hashtable二者的优势。HashMap没有考虑同步，Hashtable考虑了同步的问题。但是Hashtable在每次同步执行时都要锁住整个结构。

ConcurrentHashMap锁的方式是稍微细粒度的，ConcurrentHashMap将hash表分为16个桶（默认值），诸如get，put，remove等常用操作只锁上当前需要用到的桶。

ConcurrentHashMap的具体实现方式(分段锁)：

• 该类包含两个静态内部类MapEntry和Segment，前者用来封装映射表的键值对，后者用来充当锁的

• Segment是一种可重入的锁ReentrantLock，每个Segment守护一个HashEntry数组里得元素，当对HashEntry数组的数据进行修改时，必须首先获得对应的Segment锁。

  解析： ConcurrentHashMap与Hashtable以及HashMap的比较是一个绝对高频的考察点，我们必须熟练掌握ConcurrentHashMap分段锁的实现方式。在实际的开发中，我们在单线程环境下可以使用HashMap，多线程环境下可以使用ConcurrentHashMap，至于Hashtable已经不被推荐使用了（也就是说Hashtable只存在于面试题目中了）。

  总结：

  本小节中，我们交流学习了Java基础中的三大集合，重点阐述了HashMap相关的知识点。这里郑重提示，本小节所涉及到的内容几乎是面试中的必现考察点。有能力的同学，最好是打开JDK的源码，好好研究HashMap以及ConcurentHashMap的实现方式。当然如果你遇到问题，可以在评论区留言，我们可以一起探讨学习，一起进步。

  限于作者水平，文章中难免会有不妥之处。大家在学习过程中遇到我没有表达清楚或者表述有误的地方，欢迎随时在文章下边指出，我会及时关注，随时改正。另外，大家有任何话题都可以在下边留言，我们一起交流探讨。

  附图：

  集合的类图：

  HashMap的类图结构：

  

  ConcurrentHashMap的类图结构：

  

  Hashtable的类图结构：