JAVA集合

1. 接口集成关系和实现

集合类存放于Java.util 包中，主要有3 种：set(集）、list(列表包含Queue）和map(映射)。

1. Collection：Collection 是集合List、Set、Queue 的最基本的接口。

2. Iterator：迭代器，可以通过迭代器遍历集合中的数据

3. Map：是映射表的基础接口

2. 常见的集合数据

我们常见的集合数据有三种结构：1、数组结构 2、链表结构 3、哈希表结构 下面我们来看看各自的数据结构的特点：

2.1数组结构： 存储区间连续、内存占用严重、空间复杂度大

优点：随机读取和修改效率高，原因是数组是连续的（随机访问性强，查找速度快）

缺点：插入和删除数据效率低，因插入数据，这个位置后面的数据在内存中都要往后移动，且大小固定不易动态扩展。

2.2链表结构：存储区间离散、占用内存宽松、空间复杂度小

优点：插入删除速度快，内存利用率高，没有固定大小，扩展灵活

缺点：不能随机查找，每次都是从第一个开始遍历（查询和修改效率低）

2.3哈希表结构：结合数组结构和链表结构的优点，从而实现了查询和修改效率高，插入和删除效率也高的一种数据结构。而我们常见的HashMap就是这样的一种数据结构。后面会详细的总结hashmap的知识。

3. List相关知识

Java 的List 是非常常用的数据类型。List 是有序的Collection。Java List 一共三个实现类：分别是ArrayList、Vector 和LinkedList。

ArrayList 是最常用的List 实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要将已经有数组的数据复制到新的存储空间中。当从ArrayList 的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。

Vector 与ArrayList 一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList 慢。

LinkedList 是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了List 接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。

4. set相关知识

Set 注重独一无二的性质,该体系集合用于存储无序(存入和取出的顺序不一定相同)元素，值不能重复。对象的相等性本质是对象hashCode 值（java 是依据对象的内存地址计算出的此序号）判断的，如果想要让两个不同的对象视为相等的，就必须覆盖Object 的hashCode 方法和equals 方法。

3.1HashSet

哈希表存放的是哈希值。HashSet 存储元素的顺序并不是按照存入时的顺序（和List 显然不同） 而是按照哈希值来存的，所以取数据也是按照哈希值取得。元素的哈希值是通过元素的hashcode 方法来获取的, HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较equals 方法 如果 equls 结果为true ，HashSet 就视为同一个元素。如果equals 为false 就不是同一个元素。哈希值相同equals 为false 的元素是怎么存储呢,就是在同样的哈希值下顺延（可以认为哈希值相同的元素放在一个哈希桶中）。也就是哈希一样的存一列。如图1 表示hashCode 值不相同的情况；图2 表示hashCode 值相同，但equals 不相同的情况。

HashSet 通过hashCode 值来确定元素在内存中的位置。一个hashCode 位置上可以存放多个元素。

3.2 TreeSet()

1. TreeSet()是使用二叉树的原理对新add()的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。

2. Integer 和String 对象都可以进行默认的TreeSet 排序，而自定义类的对象是不可以的，自己定义的类必须实现Comparable 接口，并且覆写相应的compareTo()函数，才可以正常使用。

3.在覆写compare()函数时，要返回相应的值才能使TreeSet 按照一定的规则来排序

4.比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。

3.3 LinkedHashSet ()

对于LinkedHashSet 而言， 它继承与HashSet 、又基于LinkedHashMap 来实现的。

LinkedHashSet 底层使用LinkedHashMap 来保存所有元素，它继承与HashSet，其所有的方法操作上又与HashSet 相同，因此LinkedHashSet 的实现上非常简单，只提供了四个构造方法，并通过传递一个标识参数，调用父类的构造器，底层构造一个LinkedHashMap 来实现，在相关操作上与父类HashSet 的操作相同，直接调用父类HashSet 的方法即可。

5. Map相关知识

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

5.1在new HashMap时指定数组长度为13，此时数组的长度是13吗？

明显这是一个坑，因为HashMap的数组长度只能是2的n次幂的数。而且当我们把指定容量以new HashMap(13)的方式传进构造方法之后，构造方法会调用tableSizeFor方法进行处理，把处理之后的结果再赋给threshold属性.。

tableSizeFor方法生成的值是指定容量的值往上找最近的2次幂的数：比如13 -> 16;17 -> 32;通过threshold()上的注释也可以看出，返回的是一个2的次幂的数。

注意： 数组是在put操作的时候才创建，而不是new HashMap的时候。

5.2为什么数组的大小必须是2的次幂？

在put操作的源码中可以看到下标是（数组长度 -1） & hash值按位与生成的。

大小必须是2的次幂

由上图可知，左半部的计算的结果是hash值的后几位，右半部个别的二进制位经过计算后发生了改变。因为不是2的次幂的数减一之后对应的二进制数里肯定有为0的二进制位，这样不管hashcode对应的二进制位是1还是0，计算后的结果肯定为0，这样就导致元素分布的不够散列，使得Nodes[] tab数组上有些位置一直都为null，链表就会变得较长，增大了hash碰撞的概率，就会出现性能问题。

5.3那为什么不一开始就用红黑树，反而要经历一个转换的过程呢？

红黑树是一个特殊的平衡二叉树，查找的时间复杂度是 O(logn) ；而链表查找元素的时间复杂度为 O(n)，远远大于红黑树的 O(logn)，尤其是在节点越来越多的情况下，O(logn) 体现出的优势会更加明显；简而言之就是为了提升查询的效率。

其实在 JDK 的源码注释中已经对这个问题作了解释：单个 TreeNode 需要占用的空间大约是普通 Node 的两倍，所以只有当包含足够多的 Nodes 时才会转成 TreeNodes，而是否足够多就是由 TREEIFY_THRESHOLD 的值（默认值8）决定的。而当桶中节点数由于移除或者 resize 变少后，又会变回普通的链表的形式，以便节省空间，这个阈值是 UNTREEIFY_THRESHOLD（默认值6）。

5.4为什么链表的长度要大于8才转为红黑树？转换阈值8是怎么来的？

如果 hashCode 分布良好，也就是 hash 计算的结果离散好的话，那么红黑树这种形式是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为 8 的时候，概率仅为 0.00000006。这是一个小于千万分之一的概率，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。

事实上，链表长度超过 8 就转为红黑树的设计，更多的是为了防止用户自己实现了不好的哈希算法时导致链表过长，从而导致查询效率低，而此时转为红黑树更多的是一种保底策略，用来保证极端情况下查询的效率。

5.5链表长度大于8就一定会转红黑树吗？

其实链表长度大于8时不一定会转红黑树。原因我们可以看putVal的源码中找到答案：

链表长度大于8，数组长度大于等于64的时候才会立马转成红黑树源码

通过上面代码可以发现，不一定会立马转红黑树，如果数组长度小于64，先尝试扩容，解决链表过长的问题。所以只有链表长度大于8，数组长度大于等于64的时候才会立马转成红黑树。

5.5 HashMap在什么情况下会扩容，怎么扩容？

当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。执行put方法时，如果当前的数组里的元素个数大于阈值(阈值=数组长度 x 负荷因子)，就会执行resize()方法扩容。扩容的方法也很简单，创建一个比原来数组容量大两倍的新数组，遍历原来的数组，把原来数组上的元素重新按位与运算，放到新数组上。

6. 聊聊 ConcurrentHashMap 这个类

众所周知，在 Java 中，HashMap 是非线程安全的，如果想在多线程下安全的操作 map，主要有以下解决方法：

第一种方法，使用Hashtable线程安全类；

第二种方法，使用Collections.synchronizedMap方法，对方法进行加同步锁；

第三种方法，使用并发包中的ConcurrentHashMap类；

Hashtable 是遗留类，很多映射的常用功能与HashMap 类似，不同的是它承自Dictionary 类，Hashtable 是一个线程安全的类，Hashtable 几乎所有的添加、删除、查询方法都加了synchronized同步锁！相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞等待需要的锁被释放，在竞争激烈的多线程场景中性能就会非常差，所以 Hashtable 不推荐使用！

再来看看第二种方法，使用Collections.synchronizedMap方法，我们打开JDK源码，可以很清晰的看到，如果传入的是 HashMap 对象，其实也是对 HashMap 做的方法做了一层包装，里面使用对象锁来保证多线程场景下，操作安全，本质也是对 HashMap 进行全表锁！使用Collections.synchronizedMap方法，在竞争激烈的多线程环境下性能依然也非常差，所以不推荐使用！

再来看看第三种方法，使用并发包中的ConcurrentHashMap类！JDK1.7版本ConcurrentHashMap 类所采用的正是分段锁的思想，将 HashMap 进行切割，把 HashMap 中的哈希数组切分成小数组，每个小数组有 n 个 HashEntry 组成，其中小数组继承自ReentrantLock（可重入锁），这个小数组名叫Segment， 如下图：

jdk1.7分段锁

JDK1.8 中 ConcurrentHashMap 类取消了 Segment 分段锁，采用 CAS + synchronized 来保证并发安全，数据结构跟 jdk1.8 中 HashMap 结构类似，都是数组 + 链表（当链表长度大于8时，链表结构转为红黑二叉树）结构。ConcurrentHashMap 中 synchronized 只锁定当前链表或红黑二叉树的首节点，只要节点 hash 不冲突，就不会产生并发，相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍！

从源码1.7上可以看出，ConcurrentHashMap 初始化方法有三个参数，initialCapacity（初始化容量）为16、loadFactor（负载因子）为0.75、concurrentLevel（并发等级）为16，如果不指定则会使用默认值。其中，值得注意的是 concurrentLevel 这个参数，虽然 Segment 数组大小 ssize 是由 concurrentLevel 来决定的，但是却不一定等于 concurrentLevel，ssize 通过位移动运算，一定是大于或者等于 concurrentLevel 的最小的 2 的次幂！通过计算可以看出，按默认的 initialCapacity 初始容量为16，concurrentLevel 并发等级为16，理论上就允许 16 个线程并发执行，并且每一个线程独占一把锁访问 Segment，不影响其它的 Segment 操作！

详细的介绍请参看

7. 聊聊LinkedHashMap

LinkedHashMap继承于HashMap，首先使用super调用了父类HashMap的构造方法，其实就是根据初始容量、负载因子去初始化Entry[] table，然后把accessOrder设置为false，这就跟存储的顺序有关了，LinkedHashMap存储数据是有序的，而且分为两种：插入顺序和访问顺序。这里accessOrder设置为false，表示不是访问顺序而是插入顺序存储的，这也是默认值，表示LinkedHashMap中存储的顺序是按照调用put方法插入的顺序进行排序的。LinkedHashMap其实就是可以看成HashMap的基础上，多了一个双向链表来维持顺序。

HashMap

LinkedHashMap