Java集合篇

概念

JAVA中的集合

List

List是有序的collection,主体为数组

• ArrayList，扩容原理是，将原来的数组复制到新的数组。查询快，插入删除慢。
• LinkedList 是双向链表，查询慢，插入删除快。

Set

set不允许重复的元素，set中是无序的。

• HashSet 是通过HashMap实现的，（所有Key都是用相同的Value，一个名为PRESENT的Object类型常量）。
  因为基于HashMap，所以线程不安全。
• LinkedHashSet继承HashSet，使用双向链表维护插入顺序。
• TreeSet通过TreeMap实现。有序

Map

Map是键值对集合。

• HashMap 数组+链表。当链表长度大于8，表容量>=64，桶内变为红黑树。
• LinkedHashMap 基于HashMap，双向链表。
• HashTable 数组+链表。加锁，颗粒度粗。
• TreeMap 红黑树
• ConcurrentHashMap Node数组+链表+红黑树实现，线程安全的（jdk1.8以前Segment锁，1.8以后volatile + CAS 或者 synchronized）

线程安全的集合

常见的。

• HashTable 给每个方法加synchronized锁
• ConcurrentHashMap：它与 HashTable 的主要区别是二者加锁粒度的不同，在JDK1.7，ConcurrentHashMap加的是分段锁，也就是Segment锁，每个Segment 含有整个 table 的一部分，这样不同分段之间的并发操作就互不影响。
  在JDK 1.8 ，它取消了Segment字段，直接在table元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率。对于put操作，如果Key对应的数组元素为null，则通过CAS操作（Compare and Swap）将其设置为当前值。如果Key对应的数组元素（也即链表表头或者树的根元素）不为null，则对该元素使用 synchronized 关键字申请锁，然后进行操作。如果该 put 操作使得当前链表长度超过一定阈值，则将该链表转换为红黑树，从而提高寻址效率。

集合遍历的方法

• for
• 增强for循环(string element : List)
• Iterator迭代器
• ListIterator迭代器
• forEach方法
• Stream API