Java学习 - 集合类

想到有关Java集合类有关的内容，就是几点：

• 列表(ArrayList)
• 链表(LinkedList)
• 集合(Set, HashSet)
• 键值对(HashMap, HashTable)
• 线程安全

ArrayList相关

一般来说，ArrayList要不就是跟LinkedList进行对比，要不就是询问有关线程安全相关的内容。

ArrayList VS. Vector VS. Array VS. LinkedList

ArrayList	LinkedList	Vector	Array
底层维护的是一个数组	底层是一个双向链表	底层维护的是一个数组	本身就是一个数组
内存是连续的	内存不是连续的	内存是连续的	内存是连续的
支持随机访问	不支持随机访问	支持随机访问	支持随机访问
线程不安全	线程不安全	线程安全	线程不安全

ArrayList扩容

关于ArrayList的扩容，可以将其分阶段来讲

创建新ArrayList对象：

• 指定了大小：ArrayList大小即为指定大小
• 没有指定大小：ArrayList容量初始化为0

添加元素：

• 大小不为0：判断添加元素后ArrayList长度是否超过了capacity。如果超过了：
  • 扩容后没有超过最大指定容量($\texttt{MIN\_ARRAY\_SIZE}$)：capacity = capacity + (capacity >> 1)，基本上就是为原上限的1.5倍
  • 扩容后超过了$\texttt{MIN\_ARRAY\_SIZE}$：
    • 超过了最大容量：capacity = INTEGER.MAX_VALUE
    • 没有超过最大容量：capacity = MIN_ARRAY_SIZE
• 扩容之后，新建一个容量为新capacity的数组，将旧数组内容使用copyof()复制到新数组中，将引用指向新数组的内存地址，释放旧数组。

CopyOnWriteArrayList

CopyOnWriteArrayList是一个线程安全的ArrayList，在现实中的运用场景，通常会假设读情况远远大于写情况。

在该数据结构中引入了一个“写时复制”的理念，其核心非常简单。由于假设了读频率远大于写，所以在出现写的情况时，会生成一个原数组的拷贝，然后写操作只会在这个拷贝上进行修改。在修改结束之后，再将结果覆盖到原数组上。

除此以外，跟正常ArrayList的差别不大，为数不多的差别体现在CopyOnWriteArrayList中没有实现像ArrayList中那样的扩容机制。

Map相关

Map的核心就是键值对，然后设计了一系列的针对解决高性能键值对操作问题的数据结构。

HashMap VS. HashTable

HashMap	HashTable
非线程安全	线程安全
常用类	古早版本的产物，少用
接受null值	不接受null值
扩容机制: 2n	扩容机制: 2n+1
对哈希值进行了高位和低位 的混合扰动处理以减少冲突	直接使用hashcode()
桶大小小时：值为链表 桶大小大时：只为红黑树	没有动态策略

扩容机制:

HashTable:

• 没有指定初始值：11
• 扩容时： 2n +1

HashMap:

• 没有指定初始值：16
• 指定了初始值：取决于初始值扩容到2的幂次方大小
• 扩容时：2n

HashCode相关

经典问题：重写equals()时为什么必须重写hashCode()方法?

在将类实例添加到Hash相关数据结构中时，有如下步骤：

1. 计算该实例对应的hashCode()，同时计算其他已添加到数据结构中对象的hashCode
2. 如果没有相同hashCode，程序会认为没有相同对象被添加进结构中，否则调用equals方法来判断两个对象是否相同
3. 根据结果，判断是否成功添加了对象

由以上可以看出来，在某些情况下，equals和hashCode都被用来检测两个对象是否相等，如果没有重写hashCode方法，也许会发生以下问题：

• 两个不同的对象由极大可能性拥有相同的hashCode，这违背了java的equals与hashcode的契约（即对象A与对象Bequals -> 对象A的hashcode与对象B的hashcode相同）
• 添加对象到结构中时，equals为true的两个对象也许hashcode不相同，这导致两个本应放在相近或者同一个桶中的对象被分在了不同的桶中
• 在结构中查找对象时，无法精确定位到目标对象，导致潜在的错误的查询失败问题

LinkedHashMap

其本质就是为每一个键值添加了一个双向链表节点的特性，让他们多了一个next指针和一个prev指针。

由于依然保留了HashMap的特性，LinkedHashMap在桶大小到了一定阈值时便将内部结构变为红黑树。因此，可以延伸出一个问题：这里的红黑树节点与HashMap的红黑树节点是一样的吗？

答案是一样的，HashMap中的TreeNode继承了有双向链表特性的Entry。这让它们有着Entry的特性的同时，也拥有TreeNode的特性。只是在HashMap中并不会用到Entry的特性。Java的设计者应该是为了统一节点风格而这么做的。但是这样做，似乎会让TreeNode多了两个没有用的引用指针，导致资源浪费。关于这一点，听听Java设计者怎么说的：

Because TreeNodes are about twice the size of regular nodes, weuse them only when bins contain enough nodes to warrant use(see TREEIFY_THRESHOLD). And when they become too small (due toremoval or resizing) they are converted back to plain bins. Inusages with well-distributed user hashCodes, tree bins arerarely used. Ideally, under random hashCodes, the frequency ofnodes in bins follows a Poisson distribution

大意就是HashMap中的键值被转化为红黑树的可能性比较低。就算转为红黑树变为树节点，也可能会因为移除或者扩容将 TreeNode 变为 Node，所以 TreeNode 的使用概率不算很大，对于这一点资源空间的浪费是可以接受的。^[1]

ConcurrentHashMap

顾名思义，是一个线程安全的HashMap。这个类被分为两个时期进行讨论

Java 8 以前

采用了Segment + HashMap的方式，将HashMap数据分为多个Segment,每一个Segment中都维护着一个类似于HashMap的结构。每一个Segment中都分配了一把锁，以保证在对某一个Segment中的内容进行操作时，不会让其他Segment中的内容的读写造成影响。

这里的Segment继承了ReentrantLock，所以每一个Segment本身也就是一个可重入锁。在1.8以前，ConcurrentHashMap维护的是一个Segment数组，其大小在初始化之后便无法改变，也就是说，假设初始化大小为n，则意味着最高可支持n个线程并行操作。然而，默认n = 16。

Java 8之后

摒弃了Segment，采取了Node + CAS / Synchronized 来实现线程安全。当然，这里的Node取决于键值形式，也许是双向链表Node，也也许是TreeNode。

新的ConcurrentHashMap大量使用了CAS机制来进行读写操作，但是在某些情况下依然会使用Synchronized来保证线程安全。比如说，当一个桶的大小（冲突量）超过阈值，需要将键值结构转为红黑树时，ConcurrentHashMap会使用Synchronized将该key中的内容锁住，以保证数据完整性和安全性。

引用

1. LinkedHashMap 源码分析 ↩