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