JAVA 集合
2021-05-14 23:57:52 0 举报AI智能生成
Java 集合框架知识点图
作者其他创作
大纲/内容
数组与集合
数组
数组缺点
长度确定，类型固定
数组提供的方法非常有限，增删查改操作，效率不高。
存储特点：有序可重复，无法满足不重复的需求
集合可以解决数组的弊端
Map(映射）
Hashtable
线程安全，效率低；不能存储null值的key 和 value；
Hashtable 是直接在操作方法上加synchronize关键字，锁住了整个数组，粒度比较大
常用于处理配置文件属性
HashMap
线程不安全，效率高，可存储null的key和value
线程不安全带来的问题
常用方法
添加：put(Object key,Object value)
删除：remove(Object key);
修改：put(Object key, Object value)
查询：get(Object key）
时间复杂度由链表长度决定
长度：size();
遍历：
foreach
for
HashMap底层
初始化
无参构造器：HashMap map = new HashMap();
哈希表默认16，加载因子0.75（数组长度达到3/4进行扩容）
JDK7:调用构造器时产生默认长度、
加载因子的哈希表，while方式产生
加载因子的哈希表，while方式产生
JDK1.8:默认为空，在第一次添加数据时进行初始化，位运算方式产生
有参构造器HashMap(int initialCapacity, float loadFactor)
hashcode函数设计
JDK7
进行了四次异或操作
JDK8
首先获取key的hashcode是Int类型共32位，用hashcode的高16位和低16位进行异或操作（^）,(n-1) & hash
通过hash 值与容量-1相与操作来定位hash值在table哈希表中的位置。
通过hash 值与容量-1相与操作来定位hash值在table哈希表中的位置。
为什么这么设计
一定要尽可能降低hash碰撞，越分散越好；
算法一定要尽可能高效，因为这是高频操作，因此采用位运算
JDK7:流程分析
JDK8:源码分析
HashMap在Jdk 8 中相交于 jdk 7 底层实现有所不同（为什么要优化这几点）
JDK7 new 的时候初始化数组，
JDK8 在首次调用put()方法时，底层创建长度为16的数组。
JDK8 在首次调用put()方法时，底层创建长度为16的数组。
节省空间
jdk7 底层结构：数组 + 链表。
jdk8 底层结构：数组 + 链表 + 红黑树。
jdk8 底层结构：数组 + 链表 + 红黑树。
为了防止发生hash冲突，链表长度过长，降低查询的时间复杂度
当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，
此时此索引位置上的链表改为红黑树存储。树节点个数<6时再转换成链表。防止徘徊发生频繁转换。
此时此索引位置上的链表改为红黑树存储。树节点个数<6时再转换成链表。防止徘徊发生频繁转换。
形成链表时：
头插法jdk7: 新的元素指向旧的元素
尾插法jdk8: 旧的元素指向新的元素
头插法jdk7: 新的元素指向旧的元素
尾插法jdk8: 旧的元素指向新的元素
并发环境下
JDK可能产生死链
JDK8 可能产生数据丢失问题
扩容：JDK7 时，需要对数组中的元素进行重新hash定位在新数组的位置，
JDK8 采用更简单的判读逻辑：位置不变或索引 + 旧容量 大小；
JDK8 采用更简单的判读逻辑：位置不变或索引 + 旧容量 大小；
HashMap底层核心属性说明
核心流程
ConcurrentHashMap
ConcurrentHashMap解决了什么问题
JDK7 HashMap出现的多线程死循环的问题。
JDK8 改进JDK7由头插法，改为尾插法，多线程场景下存在丢失数据问题。
提高HashMap的并发安全性
JDK7 ConcurrentHashMap
segment分段锁
哈希桶数组包含多个segment，一个segment包含多个HashEntry（桶）
segment上锁不影响其他segment操作
segment继承ReentrantLock
value值volatile修饰
保证了可见性
底层数组 + 链表
get 操作
根据 key 计算出 hash 值定位到具体的 Segment ，再根据 hash 值获取定位 HashEntry 对象，并对 HashEntry 对象进行链表遍历，找到对应元素。
volatile 可以保证内存可见性，所以不会读取到过期数据
put 操作
先定位到相应的Segment
获取对象锁成功
定位分段内的桶下标
遍历链表内容
key 已存在看是否覆盖value
key 不存在头插法插入
获取对象锁失败
尝试自旋获取锁
循环式的判断对象锁是否能够被成功获取，直到获取锁才会退出循环，
防止执行put 操作的线程频繁阻塞。
防止执行put 操作的线程频繁阻塞。
重试次数达到一定的次数，会变成阻塞锁。
ConcurrentHashMap 并发度
程序不产生锁竞争的最大线程数
JDK7 里是segment 的数量
过大，可以在一个segment内访问，变成两个segment，命中效率降低
过小，容易产生锁竞争
扩容：segment正在进行扩容操作，其他写线程会被阻塞。
JDK8 ConcurrentHashMap
采用更细粒度的锁，锁住桶数组中的桶节点。
使用CAS + Synchronized 方式，保证线程并发安全
JDK8 对Sychronized做了大量优化后，相对ReentranLock可以减少内存开销。
因为只对桶下标进行上锁。
底层使用数组 + 链表 + 红黑树实现
提升查询效率
数据添加：由JDK7的头插法改为尾插法
尾插法的优势
初始化：由饿汉式改为懒汉式
节约了资源
get 操作
get，无锁操作（仅需要保证可见性,除Treebin（TreeBin节点持有红黑树的根节点） 的读写锁），
扩容过程中get操作拿到是ForwardingNode 它会让get操作在新table进行搜索。
扩容过程中get操作拿到是ForwardingNode 它会让get操作在新table进行搜索。
get 流程
根据key 计算hash值，判断哈希table是否为空
为空，返回null
如果读取到的bin头节点为null
返回null
如果是链表结构，就到链表中查询
如果是红黑树结构，就从红黑树里面查询
读操作get为什么是线程安全的
读操作一般不加锁(TreeBin的读写锁除外)，读写操作可并行；因为C13Map的写操作都要获取bin头部的syncronized互斥锁，能保证最多只有一个线程在做更新，单线程写、多线程读的并发安全性的问题
如果读取的bin是一个链表,
头节点是个普通Node
头节点是个普通Node
如果正在发生链表向红黑树的treeify()（链表转树结构）工作，
因为treeify本身并不破坏旧的链表bin的结构，只是在全部treeify完成后将头节点一次性
替换为新创建的TreeBin,可以放心读取。
因为treeify本身并不破坏旧的链表bin的结构，只是在全部treeify完成后将头节点一次性
替换为新创建的TreeBin,可以放心读取。
如果正在发生resize且当前bin正在被transfer，因为transfer本身并不破坏旧的链表bin的结构，
只是在全部transfer完成后将头节点一次性替换为ForwardingNode，可以放心读取。
只是在全部transfer完成后将头节点一次性替换为ForwardingNode，可以放心读取。
扩容期间hash桶查询数据会发生什么？
扩容前，扩容中可以访问原数组
正在迁移的hash 桶
迁移形成的链是复制的，而非移动，复制不影响原数组的遍历，不会阻塞get操作
扩容完成的
头节点的hash 为负数表示整个数组在扩容
头节点标记为ForwardNode
转发到新数组进行查询
如果其它线程正在操作链表，在当前线程遍历链表的任意一个时间点，都有可能同时在发生add/replace/remove操作。
ConcurrentHashMap 弱一致性
ConcurrentHashMap 弱一致性
如果是add操作，因为链表的节点新增从JDK8以后都采用了尾插法，会多遍历或者少遍历一个tailNode节点
如果是remove操作，存在遍历到某个Node时，正好有其它线程将其remove,导致其孤立
于整个链表之外；
但因为其next引用未变，整个链表并没有断开，还是可以照常遍历链表知道tailNode.
于整个链表之外；
但因为其next引用未变，整个链表并没有断开，还是可以照常遍历链表知道tailNode.
如果是replace 操作，链表的结构未变；只是某个Node的value 发生了变化，没有安全问题。
不能保证happen before
结论：链表线性数据结构，单线程写且插入操作尾插法，并发读取是安全的；
不会存在误读、链表断开导致的漏读、读到环状链表等问题。
不会存在误读、链表断开导致的漏读、读到环状链表等问题。
put 流程
首先会判断key、value 是否为空，如果为空就抛异常
null 区别
ConCurrentHashMap：if (key == null || value == null) throw new NullPointerException();
如果key或者value其中一个null，就报空指针异常
如果key或者value其中一个null，就报空指针异常
HashMap：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
HashMap允许存入key为null
HashMap允许存入key为null
为什么ConcurrentHashMap不能存null
在并发的情况下带来二义性
HashMap中
map.get(key)方法得到值为null
map.contains(key) 方法来判断不存在还是值为 null
ConcurrentHashMap 中
两次调用值可能被改变
判断桶数组为空，创建桶数组
当前线程正在创建另一个线程等待。
创建方式区别
JDK8 仅计算size容量，懒汉式创建
JDK7 直接创建数组，占用内存。
判断当前数组下标是否第一次插入，为空，使用casTabAt创建Node头节点
要创建链表头节点
cas操作保证线程安全，若同时又两个线程进行同一个位置的数据添加，只有一个
会成功，失败的线程进入下一次for循环。
会成功，失败的线程进入下一次for循环。
取代分段锁思想
更细粒度的锁，cas只会对hash表的一个链表头节点上锁，不影响其他链表头的操作
（一个位置一把锁）
（一个位置一把锁）
扩容期间hash 通插入数据会发生什么？
已扩容
hash 值为 -1, 说明为ForwardingNode,有线程正在扩容，当前线程帮忙扩容。
正在扩容的头结点
synchronized锁住桶下标，doubleCheck检测是否变化
是链表，用链表表方式插入
找到相同的key
如果允许更新，进行value值得更新
没有找到
链表尾部进行添加操作（JDK8的尾插法）
链表长度大于8 且table长度大于64,进行树化操作。
是红黑树，用红黑树方式插入
其他线程无法获得锁，被阻塞，不能操作正在迁移的Hash桶
未扩容
可直接插入
最后判断是否进行扩容操作
什么时候触发扩容（transfer）
addCount
helpTransfer
tryPresize
ForwardingNode
hash值MOVED=-1，ForwardingNode存在表示集合正在扩容状态，nextTable指向扩容后的数组。
扩容时如果table某个bin(头结点)迁移完毕，用ForwardingNode作为旧table bin 的头结点（占位功能）
get 遍历到旧table， 如果头结点标识位ForwardingNode， 则到新表中getb遍历，不会阻塞查询操作（转发功能）
sizeCtl 属性在各个阶段的作用
新建而未初始化时
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) +1));
this.sizeCtl = cap;
this.sizeCtl = cap;
sizeCtl值为2的幂次方数
记录集合在实际创建时应该使用的大小。
初始化过程中
U.compareAndSwapInt(this, SIZECTL, sc, -1)
将 sizeCtl 值设置为 -1 表示集合正在初始化
其他线程发现该值为 -1 时会让出CPU资源以便初始化操作尽快完成 。
初始化完成后
sc = n - (n >>> 2);
sizeCtl = sc;
sizeCtl = sc;
记录一下扩容的阈值
正在扩容时
U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)
第一条扩容线程设置的某个特定基数
U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)
后续线程加入扩容大军时每次加 1
U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)
线程扩容完毕退出扩容操作时每次减 1
sizeCtl 用于记录当前扩容的并发线程数情况
此时 sizeCtl 的值为：((rs << RESIZE_STAMP_SHIFT) + 2) + (正在扩容的
线程数) ，并且该状态下 sizeCtl < 0 。
线程数) ，并且该状态下 sizeCtl < 0 。
LinkedHashMap
LinkedHashMap内部提供了Entry
保证在遍历map元素时，可以按照添加的顺序实现遍历。
在原的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素
对于频繁的遍历操作，此类执行效率高于HashMap.
TreeMap
按照key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。
collection 接口
Set接口
HashSet
对于 HashSet 中保存的对象，请注意正确重写其 equals 和 hashCode 方法，以保证放入对象的唯一性。
TreeSet(二叉树)
可以按添加对象的属性进行排序
红黑树
LinkHashSet
遍历可以按照添加的顺序遍历
添加数据时，需要记录此数据前一个数据和后一个数据的引用
对于频繁的遍历操作，LinkedHashSet效率高于HashSet
List接口
ArrayList
优点
查询速度快
缺点
删除、插入都需要移动后面的所有元素，扩容的时候
线程不安全
扩容机制
动态数组
LinkedList
对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储。
ArrayList 和 LinkedList 的区别
数据结构
ArrayList 是动态数组
LinkedList 是 双向链表
随机访问效率
ArrayList : O(1)
LinkedList: O(n)
增加和删除效率
ArrayList : O(0)
LinkedList: O(1)
内存空间占用
LinkedList多两个引用
线程安全
都是线程不安全的
Vector
ArrayList 和Vector 的区别
线程安全
List 和 Set 的区别
List接口
存储特点：存储有序、可重复数据、可存多个null 值
和数组类似，List可以动态扩容，查找元素效率高，插入删除元素，效率低。
Set接口
存储特点：存储无序、不可重复的数据。
Queue
Collections 工具类
作用：操作Collection和Map的工具类
0 条评论
下一页
