【2020-06-06--02期】Java 集合类
提纲
- ArrayList 与LinkedList 异同；
- HashMap 与Hashtable 异同；
- HashMap与HashSet异同；
- CurrentHashMap 和HashTable 异同；
- ConcurrentHashMap线程安全的具体实现方式/底层具体实现
image-20200606172502386
1. Arraylist 与 LinkedList 异同
| Arraylist | LinkedList | |
|---|---|---|
| 线程安全 | 否 | 否 |
| 底层数据结构 | Object数组 | 双向循环链表 |
| 时间复杂度 | 是 O(n) | 否 O(1) |
| 快速随机访问 | RandmoAccess 接口,是，通过元素的序号快速获取元素对象(对应于get(int index)方法)。 |
否 |
| 内存空间占用 | 结尾会预留一定的容量空间 | 素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。 |
2.HashMap 和 Hashtable 的区别
| HashMap | Hashtable | |
|---|---|---|
| 线程安全 | 否 | 是 |
| 效率 | 高 | 低，淘汰 |
| Null key ，Null value | 唯一null key，多null value | 非null key |
| 初始大小，扩容 | 16， 2的n次方扩容 | |
| 底层数据结构 | 较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间 | 无特殊处理 |
为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。
这个算法应该如何设计呢？
我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。
2.1 HashTable
2.1.1 HashTable UML
image-20200606190400889
2.1.2 HashTable UML Detail;
image
2.2 HashMap
image
3. HashSet 和 HashMap 区别？
-
HashMap HashSet 接口 实现了Map接口 实现Set接口 存储对象 存储键值对 进存储对象 hashcode生成方式 使用key，计算Hashcode 1.使用成员对象来计算hashcode值；<br />2.两个对象hashcode 可能相同；<br />3.equals()方法判断对象是否相同；<br />4. 获取方式 速度较快，使用唯一的key获取对象 较慢
3.1 Hashset Class UML
image-20200606183749453
**HashSet 具体方法类**
image
4.CurrentHashMap与Hashtable异同
| ConcurrentHashMap | Hashtable | |
|---|---|---|
| 底层数据结构 | 分段的数组+链表(解决哈希冲突)<br />数组+链表/红黑二叉树 （jdk1.8,超过8个的时候） | 数组+链表 的形式，数组是 HashMap 的主体，链表(解决哈希冲突) |
| 线程安全的方式 | （JDK1.7分段锁）<br /> 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。<br />JDK1.8 Node 数组+链表+红黑树<br />直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作 | Hashtable(同一把锁)使用 synchronized 来保证线程安全，效率非常低下 |
4.1 ConcurrentHashMap Class UML；
image-20200606191037744
4.2 ConcurrentHashMap UML Detal ；
[图片上传失败...(image-968fdd-1591450931527)]
5. ConcurrentHashMap线程安全的具体实现方式/底层具体实现
5.1 JDK1.7 CurrentHashMap的实现；
image-20200606212218385
image-20200606193621263
-
首先将数据分段；
-
然后给没一段加把锁；
-
当一个线程占用锁访问其中一个段的时候，其他的数据也能被其他线程访问；
-
ConcurrentHashMap 是由 Segment 数组结构和 HahEntry 数组结构组成
-
Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。
static class Segment<K,V> extends ReentrantLock implements Serializable { } -
ConcurrentHashMap 里包含一个 Segment 数组；
-
Segment 的结构和HashMap类似，是一种数组和链表结构，
-
一个 Segment 包含一个 HashEntry 数组，
-
每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。
5.2 JDK1.8 ConcurrentHashMap实现；
image-20200606212032814
- ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。
- synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。
网友评论