java集合
2021-11-18 18:11:39 0 举报AI智能生成
Java集合（java.util.Collection）是Java语言中用于存储和操作一组对象的框架。它提供了一种统一的方式来处理不同类型的对象，如列表、队列、栈等。Java集合的主要接口有List、Set和Map，它们分别代表了有序的、不可重复的和键值对映射的数据结构。Java集合类库包含了许多常用的实现类，如ArrayList、LinkedList、HashSet、TreeSet和HashMap等。使用Java集合可以提高代码的复用性和可维护性，同时也简化了对数据的管理和操作。
作者其他创作
大纲/内容
概述
与数组区别
数组
可以存储基本数据，也可以存储引用数据
存储的元素必须用同一类型数据
固定长度
集合
只能存储引用数据
存储的对象可以是不同类型的
变长
快速失败（fast-fail）
在遍历集合的时候修改（结构上的修改而非元素的修改）集合，会抛出ConcurrentModificationException异常
解决办法
在设计到modCount的地方加上sychronized
使用CopyOnWriteArrayList代替ArrayList
确保集合不会被修改
Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合，
这样改变集合的任何操作都会抛出 Java. lang.UnsupportedOperationException 异常
这样改变集合的任何操作都会抛出 Java. lang.UnsupportedOperationException 异常
哈希冲突
不同的值，根据同一个哈希函数计算出来相同的哈希码
迭代器
（Iterator）
（Iterator）
迭代器允许调用者在迭代过程中移除元素。
概述
只能单向遍历
ListIterator
只能遍历List
可以双向遍历List
对Iterator的扩展
分类
Collection
Queue
BlockingQueue
ArrayBlockingQueue
LinkedBlockingQueue
Dqueue
双端队列
poll()和 remove()区别
相同点
都是返回第一个元素
不同点
如果没有元素
poll()返回null
remove()会抛出异常NoSuchElementException
poll()返回null
remove()会抛出异常NoSuchElementException
List
（有序）
（有序）
ArrayList
Object数组
每次扩容只会增加50%
多线程环境下，Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用
只保证在修改数据时不会有并发问题；
但在使用迭代器时任然会报错，迭代器在获取数据时会检查集合是否被修改过
但在使用迭代器时任然会报错，迭代器在获取数据时会检查集合是否被修改过
LinkedList
双向循环链表
Vector
Object数组
比ArrayList多了一个同步，现在已不建议使用
Stack
每次扩容增加1倍
概念：有序，元素可重复，可插入null元素
Set
（无序）
（无序）
HashSet
（无序，唯一）
（无序，唯一）
基于 HashMap 实现的，底层采用 HashMap 来保存元素
LinkdeHashSet
LinkedHashSet 继承与于HashSet，并且其内部是通过 LinkedHashMap 来实现的。
SortedSet
NavigableSet
TreeSet
（有序，唯一）
（有序，唯一）
红黑树(自平衡的排序二叉树。)
概念：无序，不重复，可插入null元素
Map
HashTable
数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
比HashMap多个线程安全，已不建议使用
null不能作为键
HashMap
JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.
JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
Hash计算方式
1.hashCode()计算哈希码
2.扰动处理
（减少哈希冲突）
（减少哈希冲突）
JDK7
扰动处理：9次扰动=4次位运算+5次异或运算
JDK8
扰动处理：2次扰动=1次位运算+1次异或运算
Put方法具体流程
计算KKey的Hash值
让key.hashCode() 与key.hashCode()>>16 进行异或操作
高16bit补0，一个数和0异或不变，
所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。
因为bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash ，
如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，
设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，
而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能。
高16bit补0，一个数和0异或不变，
所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。
因为bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash ，
如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，
设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，
而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能。
每次扩容为原来的2倍
，resize()方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大小大于其临界值(第一次为12),这个时候在扩容的同时也会伴随桶上面的元素进行重新分发，这也是JDK1.8版本的一个优化的地方，
在1.7中，扩容之后需要重新去计算其Hash值，根据Hash值对其进行分发，
但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0，重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上
在1.7中，扩容之后需要重新去计算其Hash值，根据Hash值对其进行分发，
但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0，重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上
初始大小16(2的四次方)
为啥长度为2的幂次方
让 HashMap 存取高效，尽量较少碰撞，
也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。
也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。
算法
取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率
两次扰动
加大哈希值低位的随机性，使得分布更均匀
最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的；
最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的；
键值都可以为null
LinkedHashMap
（保证插入顺序）
（保证插入顺序）
继承自 HashMap，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序
ConcurrentHashMap
对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁进行保护
键值都不允许为null
① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment，比Hashtable效率提高16倍。）
JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。
JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。
IdentityHashMap
SortedMap
NavigableMap
TreeMap
红黑树（自平衡的排序二叉树）
WeakHashMap
0 条评论
下一页
