集合容器
2022-03-11 00:29:08 0 举报AI智能生成
java常见集合容器关键知识
作者其他创作
大纲/内容
概述
什么是集合框架
集合定义存储数据的容器，集合框架提供一种表示和操作集合的一种标准的体系结构，提供有效的数据结构和算法，无需将精力花费在底层实现上
1、接口：对外操作的接口，允许我们不需关心具体实现，达到多态
2、接口的实现：集合操作的具体实现，是重用性很高的数据结构
3、算法：提供了集合操作的计算方法，比如说查找、排序等
集合的特点
1、数据存储和对象存储
2、对象数量确定可以使用数组，不定数量使用集合，因为集合是可变长度的
集合与数组的区别
1、集合可变长度，数组长度固定
2、集合只可存储引用类型，数组即可存储基本类型也可以存储引用类型
3、数组的内容必须是相同类型的数据，集合无需相同类型
java集合体系
Collection
Set(一般无序、不可重复、
只允许一个null元素)
HashSet（hashMap实现）
LinkedHashSet
SortedSet
NavigableSet
TreeSet（有序唯一，
红黑树实现）
List(有序、可重复、多个null元素)
ArrayList（Object数组实现）
LinkList（双向循环链表）
Vector（object数组）
Queue
BlockingQueue
Dequeue
Map
HashTable（数组+链表实现，数组是hashMap的主体，链表是为了解决hash冲突而存在，线程安全）
HashMap（数组+链表，JDK8数组大于8结构存储为红黑树）
LinkHashMap（在hashMap基础上增加一条双向链表，记录原因插入时间）
sortedMap
NavigableMap
WeakHashMap
IdentityHashMap
fail-fast机制
修改结构的遍历、多线程修改结构的情况下，会抛出异常
原因：迭代器维护了一个modCount变量，遍历期间结构发生变化，变量值将会改变。通过比较预期值expectModCount，不一致抛出异常，终止遍历
解决方案
遍历中，使用synchronize同步变量；
使用copyOnWriteArrayList来替换ArrayList
collection接口
迭代器Iterator：可遍历任何collection接口，允许我们边迭代边移出元素。特点：单向遍历
List接口和Set的区别：List是有序的，即存入和取出的顺序一致，元素可以重复并允许多个null元素，可以通过下标遍历；Set是无序的，元素不可重复，只允许一个null元素，无法通过下标访问，插入和删除不影响元素位置
List接口
遍历方式
1、迭代器遍历
2、for循环遍历：基于计数器的遍历，依次读取集合元素，到达最后一个位置停止遍历
3、foreach循环遍历：内部还是使用了iterator迭代器，无需显式声明。有点是代码简洁不易出错，缺点是只能简单遍历不能在遍历中删除添加元素
最佳实践：如果数据集合实现了RandomAccess接口，意味着按位置读取的时间复杂度为O(n)，可采用for循环遍历；否则使用foreach或迭代器遍历
ArrayList
优点：随机访问，底层基于数据实现，查找元素快，顺序添加元素方便
缺点：删除和插入元素的时候需要进行复制，性能耗费较大
可使用Collections.synchronizeLits()方法转换成线程安全的容器再使用
transient关键字修饰数组：通过重写ReadObject和WriteObject方法，将扩容导致的无元素存储空间不进行序列化，而只序列化有实际元素的存储空间中的元素
ArrayList、LinkedList
的区别与联系
数据结构：A基于数组实现，L基于双向链表实现
随机访问效率：A提供随机访问效率高，L需要移动指针进行查找
添加和删除效率：A添加和删除涉及到数组复制，效率低；L仅仅需要改变指针指向
空间占用：L需要保存链表的前驱和后继需要更加多的存储资源
线程安全：都是非线程安全的
使用：频繁读取推荐使用A，插入和删除较多时使用L
vector：线程安全的arrayList，每次扩容1倍，使用了synchronize来保证线程同步
Set接口
HashSet的实现原理：基于HashMap实现，value统一为new object()对象，不仅比较hash值，也要比较equal的值，如果均相同说明重复将会被覆盖
补充：如果两个对象相等，那么hashcode相等且equals相等；若hashcode相等，equals不一定相等；equals相等hashcode一定相等。所以重写了hashcode方法要重写equals方法
Map接口
HashMap
实现原理
底层基于数组+链表实现，元素存储的位置基于hash算法，计算出要存储元素的数组下标，如果该下标有值，则放入该下班对应的链表中。查找时，根据key的hashcode得到数组下标，再查找链表中key相同的值返回即可。
简而言之，核心是采用数组的存储方式，并将出现hash冲突的key放入链表，发现冲突就在链表中进行对比
哈希算法：将任意长度的消息压缩到一定长度的消息的消息摘要函数，不能通过散列值来确定惟一值
hash冲突：不同的消息输入通过散列函数得到相同散列值的现象叫做哈希冲突，通过链地址法解决
hash算法得到是整形int数值，代表有2的31次方个数组地址，但数组长度远远达不到，所以需要进行重写hash方法，让高低位都参与hash运算，尽量减少碰撞概率，保证存储效能。这种过程称为扰动
JDK7与JDK8实现差别
JDK7：采用数组+链表的方式存储，链表元素采用头插法，4次位运算5次异或运算得到hash值（9次扰动）
JDK8：采用数组+链表+红黑树的方式存储，链表或数新增元素采用尾插法，链表长度一旦超过8个元素，将进化成红黑树，查找时间复杂度从O(n)到Olog(n)，1次位运算和1次异或运算得到hash值（2次扰动）
扩容机制
默认数组容量为16，若指定一个容量，则hashMap将自动查找大于等于2的n次幂的容量，默认负载因子为0.75，即数组容量达到75%就行扩容
扩容过程：新建一个两倍的数组，并将元素遍历后重新计算下标放入新数组，扩展后的节点要么在原来的位置，要么是原来位置的2倍
为什么必须是2的n次幂数组长度：为了保证hash算法的有效性，因为hash算法使用了二进制操作符异或，我们知道二进制运算都是操作2的倍数
concurrentHashMap
实现原理：锁分段技术，通过每个分组都采用一个锁的方式实现线程安全，相对于hashTable锁定整个hash表锁力度更加精细，并发性能更加好，底层采用分段数组+链表实现
线程安全的保证：与原理一致，对底层数组桶采用分割（Segment）的方式作为持有锁的单位，多线程环境下，操作的数据不再同一个组内，不存在竞争现象。JDK8摒弃了分组的概念，使用了红黑树+node数组+链表的数据结构来实现，线程安全使用synchronize+CAS保证，只锁定当前链表或红黑树的首节点，只要hash不冲突，就没有并发关系
0 条评论
下一页
为你推荐
查看更多
