Java集合
2020-11-26 09:09:27 5 举报AI智能生成
Java集合
作者其他创作
大纲/内容
Map
HashMap
底层结构：1.7散列表（数组+链表）1.8散列表+红黑树；初始化容量：16；装载因子：0.75；扩容：2；线程不安全；可以为null；存储无序
扩容机制：散列表元素的容量>容量*装载因子；创建一个空数组重写hash，hash公式和长度有关
散列表容量>64 &&链表长度>8,链表转成红黑树
2的次幂：方便位运算；均匀分布（key的哈希值会与该值的高16位做异或操作，增加随机性）
重写equals必须重写HashCode;如果hashCode相同，key不同则替换元素，否则就是哈希冲突
ConcurrentHashMap
key和value都不能为null，线程安全，利用CAS算法和部分操作上锁实现
1.7
底层结构：散列表（数组+链表）
1.8
底层结构：散列表+红黑树
支持高并发操作，高并发下，统计数据（计算size...）是无意义的，下一时刻size值就变化了
get方法是非阻塞，无锁的。重写Node类，通过volatile修饰next来实现每次获取都是最新设置的值
LinkedHashMap
底层结构：散列表+红黑树+双向链表；可以为null；插入有序；线程不安全；父类HashMap
提供插入顺序和访问顺序。访问顺序是符合LRU算法的，一般用于扩展（默认是插入顺序）
迭代与初始容量无关（迭代的是维护的双向链表）
大多数使用HashMap的API，在内部重写了某些方法，维护了双向链表
TreeMap
底层结构：红黑树（保证了时间复杂度log（n））；自然排序（手动排序），元素不能为空；线程不安全
可以对其进行排序使用Comparator或者Comparable，只要compare或者CompareTo认定该元素相等，那就相等
Collection
List
ArrayList
底层结构是数组；初始化容量为10；扩容1.5；线程不安全
查找访问快，增删需要数组的拷贝复制（navite方法是由c/c++实现）性能还是不差的
LinkedList
底层结构是双向链表；线程不安全
适合插入删除频繁的操作，内部维护了链表的长度
Vector
底层结构是数组；初始化容量为10；扩容2；线程安全
已经被ArrayList替代
CopyOnWriteArrayList
原理：在修改时复制出一个新数组，修改的操作在新数组中完成，最后将新数组交由array变量指向
写加锁，读不加锁；适合在读多写少的情况下使用
缺点：只能保证数据的最终一致性，不能保证数据的实时一致性
Set
HashSet
底层结构是哈希表（一个元素为链表的数组）和红黑树；元素无序；可以为null
实际上就是封装了HashMap
LinkedHashSet
底层结构是哈希表（一个元素为链表是数组）和双向链表；元素可以为null
父类是hashSet;实际上就是LinkedHashMap
TreeSet
底层实际上是一TreeMap实例（红黑树）；元素不能为null
可以实现排序的功能
0 条评论
下一页
