Java集合体系大杂烩

Java集合体系主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。

下面贴出Map的继承/实现关系。Collection的子孙太多，这里就不贴出来了。感兴趣的可以自己用idea生成。

概括来说：

　　Java中4大集合系统（Map、Set、List、Queue），常用的主要是前三种，Queue的主要实现是多线程阻塞队列。

　　Map、Set、List的各个实现类之间的性能比较，HashMap/HashSet插入自定义对象时，复写了equals方法、hashCode方法的不同情况对应不同结果，TreeMap/TreeSet插入自定义对象，复写equals方法、compareTo 方法的不同情况对应不同结果。

对equals、hashCode、compareTo这里简要的总结几点：

　　1.HashCode方法是根据key计算存储到数组的哪一个单元，删除操作时，先计算位置，再用equals方法比较，相同则删。查询也是先计算hashcode，找到位置后再通过equals方法比较，相同则true否则false
　　2.compareTo就是自定义一套比较规则，用来红黑树组件过程中比较大小时使用。如果出现修改，则删除修改的元素会出现异常，删除其它元素则不会。
　　3.一般都通过定义final的方法，避免在使用像HashMap、HashSet、TreeMap、TreeSet集合时，修改了集合中的元素，导致异常。

说到集合体系，数据结构是绕不过的坎，常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表。详细介绍我下期再讲，这期还是主讲Java集合,大家看下图能否唤起你的回忆。

上面的概括对于很多人可能过于笼统，下面就针对具体的集合实现来做对比介绍。

List

List 的特点是「元素有序、可重复」，这里所谓的有序意思是：「元素的存入顺序和取出顺序一致」。例如，存储元素的顺序是 11、22、33，那么我们从 List 中取出这些元素的时候也会按照 11、22、33 这个顺序。List 接口的常用实现类有：

「ArrayList」：底层数据结构是数组，线程不安全
「LinkedList」：底层数据结构是链表，线程不安全
「Vector」：底层数据结构是数组，线程安全(争议比较大，虽然源代码注释里面隐式说这个是线程安全的，因为确实很多方法都加上了同步关键字synchronized，但是对于复合操作而言，只是同步方法但并没有解决线程安全的问题。因为在两个原子操作之间存在间隙，在多线程环境中，完全有可能被其他线程获得 vector的 lock 并改变其状态。要真正达成线程安全，还需要以vector对象为锁，来进行操作。所以，如果是这样的话，那么用vector和ArrayList就没有区别了，所以，不推荐使用vector。）

注：数组的特点--大小固定，不适合动态存储，不方便动态添加/删除,但查询效率高

　　链表的特点--可动态添加删除大小可变，只能通过顺次指针访问，查询效率低

Set

Set最重要的特点是他「拒绝添加重复元素，不能通过整数索引来访问」，并且「元素无序」。所谓无序也就是元素的存入顺序和取出顺序不一致。其常用实现类有：

「HashSet」：底层基于 HashMap 实现，采用 HashMap 来保存元素
「LinkedHashSet」：LinkedHashSet 是 HashSet 的子类，并且其底层是通过 LinkedHashMap 来实现的。L

List和Set对比

List和Set均为单列集合
可以添加重复元素（List）和不可以添加重复元素（Set）
可以通过整数索引访问（List）和不可以通过整数索引（Set）
List可以通过下标来访问，而Set不能。

Queue

　　对于队列在此不做过多介绍，后续介绍多线程会着重介绍阻塞队列。

Map

　　「双列集合」 java.util.Map：元素是成对存在的。每个元素由键（key）与值（value）两部分组成，通过键可以找对所对应的值。显然这个双列集合解决了数组无法存储映射关系的痛点。另外，需要注意的是，「Map 不能包含重复的键，值可以重复；并且每个键只能对应一个值」,「Map部分子类允许KEY、VALUE为空，详见如下」。

类型	全路径	key是否允许null	value是否允许null
HashMap	java.util.HashMap	允许	允许
LinkedHashMap	java.util.LinkedHashMap	允许	允许
ConcurrentHashMap	java.util.concurrent.ConcurrentHashMap	不允许	不允许
ConcurrentSkipListMap	java.util.concurrent.ConcurrentSkipListMap	不允许	不允许
Hashtable	java.util.Hashtable	不允许	不允许

HashMap 、LinkedHashMap 的 key 和 value 都允许为 null。
ConcurrentHashMap、ConcurrentSkipListMap、Hashtable 的 key 和 value 都不允许为 null。

　　「HashMap」

　　HashMap可以说是面试必备，不弄到滚瓜烂熟都不敢去面试。

　　主要的问题：何为hash冲突？如何解决hash冲突？1.7和1.8的区别？HashMap为什么不安全？HashMap如何PUT值及扩容？

　　Hash冲突

　　不同的数据元素关键字key，p =H（key）计算出的哈希值相同，此时两个或多个数据，对应同一个存储地址，即产生冲突。

　　解决hash冲突的四种方法：

链地址法

　　对于相同的哈希值，使用链表进行连接。（HashMap使用此法）

　　优点：处理冲突简单，无堆积现象缺点：查询时效率较低。（存储是动态的，查询时跳转需要更多的时间）

再哈希法

　　提供多个哈希函数，如果第一个哈希函数计算出来的key的哈希值冲突了，则使用第二个哈希函数计算key的哈希值。

　　优点：不易产生聚集缺点：增加了计算时间

建立公共溢出区

　　将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

开放定址法

　　当关键key的哈希地址p =H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，若p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。即：Hi=（H（key）+di）% m （i=1，2，…，n）

　　开放定址法有下边三种方式：

线性探测再散列：顺序查看下一个单元，直到找出一个空单元或查遍全表
二次(方)探测再散列：在表的左右进行跳跃式探测，直到找出一个空单元或查遍全表
伪随机探测再散列：建立一个伪随机数发生器，并给一个随机数作为起点

　　1.7和1.8的区别

　　JDK 1.8 之前 HashMap 底层由数组加链表实现，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（链地址法（“拉链法” ）解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间（注意：将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，只有当当链表超过8且数组长度(数据总量)超过64才会转为红黑树）。

　　为什么要在数组长度大于64之后，链表才会进化为红黑树

　　在数组比较小时如果出现红黑树结构，反而会降低效率，而红黑树需要进行左旋右旋，变色，这些操作来保持平衡，同时数组长度小于64时，搜索时间相对要快些，总之是为了加快搜索速度，提高性能。

　　HashMap为什么不安全？

JDK1.7 中，由于多线程对HashMap进行扩容(头部插入)，调用了HashMap#transfer()，具体原因：某个线程执行过程中，被挂起，其他线程已经完成数据迁移，等CPU资源释放后被挂起的线程重新执行之前的逻辑，数据已经被改变，造成死循环、数据丢失。
JDK1.8 中，由于多线程对HashMap进行put操作(尾部插入)，调用了HashMap#putVal()，具体原因：假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完第六行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。
数据丢失、死循环已经在在JDK1.8中已经得到了很好的解决

　　HashMap如何PUT值？

首先根据key的值计算hash值，找到该元素在数组中存储的下标
如果数组是空的，则调用resize进行初始化；
如果没有哈希冲突直接放在对应的数组下标里
如果冲突了，且key已经存在，就覆盖掉value
如果冲突后是链表结构，就判断该链表是否大于8，如果大于8并且数组容量小于64，就进行扩容；如果链表节点数量大于8并且数组的容量大于64，则将这个结构转换成红黑树；否则，链表插入键值对，若key存在，就覆盖掉value
如果冲突后，发现该节点是红黑树，就将这个节点挂在树上

　　HashMap扩容

　　什么时候触发扩容？

　　capacity 即容量，默认16。

　　loadFactor 加载因子，默认是0.75

　　threshold 阈值。阈值=容量*加载因子。默认12。当元素数量超过阈值时便会触发扩容

在首次调用put方法的时候，初始化数组table（初始化时为定义容量）
当HashMap中的元素个数超过capacity(容量)*loadFactor(负载因子)时，就会进行数组扩容，loadFactor的默认值(DEFAULT_LOAD_FACTOR)是0.75,这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中的元素个数超过16×0.75=12(这个值就是阈值或者边界值threshold值)的时候，就把数组的大小扩展为2×16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预知元素的个数能够有效的提高HashMap的性能。
当HashMap中的其中一个链表的对象个数如果达到了8个，此时如果数组长度没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链表会变成红黑树，节点类型由Node变成TreeNode类型。当然，如果映射关系被移除后，下次执行resize方法时判断树的节点个数低于6，也会再把树转换为链表。

　　为什么加载因子设置为0.75，初始化容量是16？

　　默认的loadFactory是0.75，loadFactory越小，越趋近于0，数组中个存放的数据(entry)也就越少，表现得更加稀疏。0.75是对空间和时间效率的一种平衡选择

　　HashMap中的threshold阈值是HashMap所能容纳键值对的最大值。计算公式为length*LoadFactory。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数也越大

loadFactory越趋近于1，那么数组中存放的数据（entry也就越来越多），数据也就越密集，也就会有更多的链表长度处于更长的数值，我们的查询效率就会越低，当我们添加数据，产生hash冲突的概率也会更高

　　HashMap的容量是有上限的，必须小于1<<30，即1073741824。如果容量超出了这个数，则不再增长，且阈值会被设置为Integer.MAX_VALUE（ 2^31−1 ，即永远不会超出阈值了）。

　　扩容之后原位置的节点只有两种调整/迁移

保持原位置不动（e.hash & oldCap != 0新bit位为0时）
散列原索引+扩容大小的位置去（e.hash & oldCap != 0新bit位为1时）

　　当数组长度从16到32，其实只是多了一个bit位的运算，我们只需要在意那个多出来的bit为是0还是1，是0的话索引不变，是1的话索引变为当前索引值+扩容的长度，比如5变成5+16=21

　「LinkedHashMap」

　　HashMap 的子类，可以保证元素的存取顺序一致（存进去时候的顺序是多少，取出来的顺序就是多少，不会因为 key 的大小而改变）。

　　LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构，即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

　「ConcurrentHashMap」

　　　从上面我们已经知道HashMap是线程不安全的，HashTable它的remove,put，get做成了同步方法，保证了Hashtable的线程安全性。但每个操作数据的方法都进行synchronized同步控制之后，由此带来的问题任何一个时刻只能有一个线程可以操纵Hashtable，所以其效率比较低。

　　1.7版本

　　官方首次在1.7版本新增了ConcurrentHashMap。为了提高效率，ConcurrentHashMap将Map分段了，每个段Segment 进行加锁，其中 Segment 继承于 ReentrantLock。而不是想Hashtable,SynchronizedMap是整个map加锁，这样就可以多线程访问了。ConcurrentHashMap默认运行16个线程同时访问该map。但是我们可以通过一个函数来设置增加或减少最大可运行访问的线程数目(concurrencyLevel)。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。

　　concurrentHashMap由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表。put、get时需要定位到具体的 Segment 中;HashEntry和 HashMap 非常类似，唯一的区别就是其中的核心数据如 value ，以及链表都是 volatile 修饰的，保证了获取时的可见性。虽然 HashEntry 中的 value 是用 volatile 关键词修饰的，但是并不能保证并发的原子性，所以 put 操作时仍然需要加锁处理。

　　get的流程

　　首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁，如果重试的次数达到了 MAX_SCAN_RETRIES（64） 则改为阻塞锁获取，保证能获取成功。

　　put 的流程

将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。
为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
最后会解除在 1 中所获取当前 Segment 的锁。

　　1.8 版本

　　1.7版本虽然解决了并发问题，能够支持N个segemnt的并发，但其那查询遍历链表效率太低。故1.8版本弃用了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。也将 1.7 中存放数据的 HashEntry 改为 Node，但作用都是相同的；其中的 val next 都用了 volatile 修饰，保证了可见性。

　　get的流程

根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
如果是红黑树那就按照树的方式获取值。
就不满足那就按照链表的方式遍历获取值。

　　put 的流程

根据 key 计算出 hashcode 。
判断是否需要进行初始化。
f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
如果都不满足，则利用 synchronized 锁写入数据。
如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

　「ConcurrentSkipListMap」

　　SkipList跳表，它是一种可以替代平衡树的数据结构，其数据元素默认按照key值升序，天然有序。Skip list让已排序的数据分布在多层链表中，以0-1随机数决定一个数据的向上攀升与否，通过“空间来换取时间”的一个算法，在每个节点中增加了向前的指针，在插入、删除、查找时可以忽略一些不可能涉及到的结点，从而提高了效率。（redis Zset类型就使用了跳表）

　　SkipList采用空间换时间的算法，其插入和查找的效率O(logn)，其效率不低于红黑树，但是其原理和实现的复杂度要比红黑树简单多了。

　　ConcurrentSkipListMap其内部采用SkipLis数据结构实现。为了实现SkipList，ConcurrentSkipListMap提供了三个内部类来构建这样的链表结构：Node、Index、HeadIndex。其中Node表示最底层的单链表有序节点、Index表示为基于Node的索引层，HeadIndex用来维护索引层次。到这里我们可以这样说ConcurrentSkipListMap是通过HeadIndex维护索引层次，通过Index从最上层开始往下层查找，一步一步缩小查询范围，最后到达最底层Node时，就只需要比较很小一部分数据了

　「Hashtable」

　　线程安全，使用synchronized修饰。put get remove效率都很低

标签：key,Java,HashMap,元素,大杂烩,链表,线程,数组,集合
From： https://www.cnblogs.com/JackpotHan/p/16646375.html