Java 集合 Collections

Java 集合结构图如图所示

Java 集合最底层的根接口是 Collection 和 Map 接口

Collection 接口有3个继承接口, 分别是 Set 集合, List 列表, Queue 队列

Set 集合

其中 Set 集合 是 无序 且 不重复的

• HashSet 是 Set 的实现类, Hashset本身线程不安全，是用 Hash值 把元素存储在Set里的一种数据结构 查询速度快, 内部是 HashMap
• LinkedHashSet 是HashSet的子类, 数据结构在 HashSet基础上加入了双向链表记录插入顺序，内部是LinkedHashMap
• SortedSet 是Set 子类, 可以用 Comparator进行排序的Set
• NavigableSet 可以sort in ascending order or in descending order
• TreeSet 是 SortedSet 的实现类, TreeSet本身线程不安全, 使用 红黑树存储元素, 支持 自然排序 和 定制排序; 自然排序使用默认Comparable 接口, 而 定制排序则需要改造Comparable接口实现定制。
• CopyOnWriteArraySet 是线程安全的，加上了并发锁; 修改的时候进行拷贝确保write不会影响read

List 列表

其中 List 列表 是 有序 且 重复 的

• Vector 底层是 Arrays，是顺序内存并且有一段连续的内存空间，支持随机访问；(线程安全，但不推荐使用) 使用 InitialCapacity 设定长度, 当存储超出 InitialCapacity，InitialCapacity 会自动增加，InitialCapacity默认值为10
• Stack
• ArrayList 底层是 Arrays，是顺序内存并且有一段连续的内存空间，支持随机访问； 使用 InitialCapacity 设定长度, 当存储超出 InitialCapacity，InitialCapacity 会自动增加，InitialCapacity默认值为10 （线程不安全); 插入删除效率低, 查询效率高
• LinkedList 底层是 双向链表, 是非顺序内存，支持Iterator遍历；可以被当作Stack或者Queue使用 (线程不安全); 插入删除效率高，查询效率低
• CopyOnWriteArrayList 是线程安全的，加上了并发锁; 修改的时候进行拷贝确保write不会影响read

Queue 队列

• Priority Queue
• Blocking Queue
• PriorityBlockingQueue

Map 键值对

• HashMap 底层是 Arrays + 双向链表 + 红黑树，线程不安全; initialSize = 16, 扩容情况下 newsize = oldSize * 2; loadFactory = 0.75, loadFactory 加载因子是控制 InitialSize 扩容的变量, threadshold = newsize * loadFactory, 又叫 扩容的阈值 hashMap 允许 key, value 为null; InitialSize >8 就会使用上红黑树
• LinkedHashMap 是 HashMap的子类, 用 双向链表 记录了元素插入顺序
• IdentityHashMap
• WeakHashMap
• SortedMap 是 Map 继承的Interface, 返回排序好的Map
• NavigableMap
• TreeMap 是 SortedMap 的实现类, 底层是 红黑树，每一对 key,value 都是一个 红黑树节点，可以保持每一个节点sorted TreeMap 也支持 自然排序 和 定制排序; 排序也是同样: 自然排序使用默认Comparable 接口, 而 定制排序则需要改造Comparable接口实现定制。
• Dictionaries
• Hashtable 底层是 Arrays + 双向链表, 线程安全; initialSize = 11, 扩容情况下 newsize = oldSize * 2 + 1 hashtable 不允许 key, value 为 null; 继承Dictionaries, 只支持单线程没有ConcurrentHashMap好
• ConcurrentHashMap 底层是 Segmented Arrays + 双向链表, 线程安全; initialSize = 16 concurrentHashMap 不允许 key, value 为 null; 使用 CAS + synchronized 实现了线程安全; concurrentHashMap 使用segment分段锁，而segment继承 ReentrantLock 重入锁; 其中 concurrencyLevel 指并发数也就是segment分段锁的个数
• Properties

Collection 工具类使用

Colletions 有多个 synchronizedXXX(), 将数据结构从线程不安全转换成线程安全

Collections可以返回不可变类，包括 emptyXxx(), singletonXxx(), unmodifiableXxx()

Java Collection 常见面试题

1. Hashmap 内部构成原理: ArrayList + LinkedList + 红黑树(左旋,右旋)
2. ArrayList 的动态扩容过程是什么: 先是InitialSize, 然后调用resize创建一个更大ArrayList; 然后将现在的ArrayList复制到更大的ArrayList里
3. 如何避免 Hash冲突: 开放定址法: 用同一个Hash函数再次计算hash值, 直到解决Hash冲突 再哈希法: 用不同的Hash函数再次计算hash值, 直到解决Hash冲突 拉链法: 就是同一个hash值对应多个Entry<K,V>, 简而言之就是用 ArrayList + LinkedList (HashMap使用的是此方法)