集合总结篇
2021-03-16 22:33:43 13 举报AI智能生成
java集合总结
作者其他创作
大纲/内容
Collection
List
List集合基础
实现了Collection接口
List接口特性：是有序的，元素是可重复的
允许元素为null
常用的子类
Vector
底层结构是数组，初始容量为10，每次增长2倍
它是线程同步的，已被ArrayList替代
LinkedList
底层结构是双向链表
实现了Deque接口，因此我们可以像操作栈和队列一样操作它
线程非同步
ArrayList
底层结构是数组，初始容量为10，每次增长1.5倍
在增删时候，需要数组的拷贝复制(navite 方法由C/C++实现)，性能还是不差的！
线程非同步
CopyOnWriteArrayList
原理：在修改时，复制出一个新数组，修改的操作在新数组中完成，最后将新数组交由array变量指向。
写加锁，读不加锁
缺点：CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。
适合在读多写少的场景下使用
Set
Set集合基础
实现了Collection接口
Set接口特性：无序的，元素不可重复
底层大多数是Map结构的实现
常用的三个子类都是非同步的
常用子类
HashSet
底层数据结构是哈希表(是一个元素为链表的数组) + 红黑树
实际上就是封装了HashMap
元素无序，可以为null
LinkedHashSet
底层数据结构由哈希表(是一个元素为链表的数组)和双向链表组成。
父类是HashSet
实际上就是LinkHashMap
元素可以为null
TreeSet
底层实际上是一个TreeMap实例(红黑树)
可以实现排序的功能
元素不能为null
Map
Map基础知识
存储的结构是key-value键值对，不像Collection是单列集合
阅读Map前最好知道什么是散列表和红黑树
Map常用子类
HashMap
底层是散列表+红黑树。初始容量为16，装载因子为0.75，每次扩容2倍
允许为null，存储无序
非同步
散列表容量大于64且链表大于8时，转成红黑树
Key的哈希值会与该值的高16位做异或操作，进一步增加随机性
JDK1.8对hash算法和寻址算法的优化
hash算法的优化：对每个hash值，在他的低16位中，让高低16位进行了异或，让他的低16位同时保持了高低16位的特征，尽量避免一些hash值后续出现冲突，大家可能会进入数组的同一个位置
寻址算法的优化：用与运算替代取模，提升性能
当散列表的元素 > 容量 * 装载因子 时，会再散列，每次扩容2倍
如果hashCode相同，key不同则替换元素，否则就是散列冲突
LinkedHashMap
底层是散列表+红黑树+双向链表，父类是HashMap
允许为null，插入有序
非同步
提供插入顺序和访问顺序两种，访问顺序是符合LRU算法的，一般用于扩展(默认是插入顺序)
迭代与初始容量无关(迭代的是维护的双向链表)
大多使用HashMap的API，只不过在内部重写了某些方法，维护了双向链表
TreeMap
底层是红黑树，保证了时间复杂度为log(n)
可以对其进行排序，使用Comparator或者Comparable
只要compare或者CompareTo认定该元素相等，那就相等
非同步
自然排序(手动排序)，元素不能为null
ConcurrentHashMap
底层是散列表+红黑树，支持高并发操作
key和value都不能为null
线程是安全的，利用CAS算法和部分操作上锁实现
get方法是非阻塞，无锁的。重写Node类，通过volatile修饰next来实现每次获取都是最新设置的值
在高并发环境下，统计数据(计算size…等等)其实是无意义的，因为在下一时刻size值就变化了。
更多脑图和最新原创技术文章可关注公众号：Java3y
0 条评论
下一页
