Java集合框架思维导图
2018-10-13 16:23:03 95 举报AI智能生成
Java集合框架
作者其他创作
大纲/内容
Collection
List
ArrayList
特点：
元素特点：排列有序，可重复
结构上：底层使用数组
使用方式：随机访问速度快，插入删除效率低
线程不安全
扩容方式
初始容量10
扩容时机：当容量不足以容纳元素个数时（minCapacity > oldCapacity）
注：minCapacity: 扩容时候所需最小容量 --minCapacity = size + （所添加元素的个数，有可能是多个）
扩容大小：(minCapacity > newCapacity) ? minCapacity : newCapacity
注：newCapacity = (oldCapacity * 3)/2 + 1
Vector
特点
排列有序，可重复
底层使用数组
速度快，增删慢
线程安全，效率低
当容量不够时，Vector默认扩展一倍容量
LinkedList
特点
元素特点：排列有序，可重复
结构上：底层使用双向循环链表数据结构
使用上：随机访问速度慢，增删快，add()和remove()方法快
线程不安全
Set
HashSet
排列无序，不可重复
底层使用Hash表实现
存储速度快
内部时HashMap
TreeSet
有序，不可重复
底层使用二叉树实现
排序存储
内部是TreeMap的SortedSet
LinkedHashSet
采用Hash表存储，并用双向链表记录插入顺序
内部是LinkedHashMap
queue
在两端出入的List，所以也可以用数组或链表来实现
Map
HashMap
原理
底层使用哈希表（数组+链表），当链表过长将被转化成红黑树以实现O（logn）时间复杂度的查找
特点
键不可重复，值可以重复
底层哈希表
线程不安全
允许key为null，value也可以为null(插入时，若key为null，将value存入table[0]处)
成员变量
DEFAULT_INITIAL_CAPACITY=16
put方法过程
1、对key的hashCode再求hash值，然后计算下标
2、如果没有碰撞，直接放入桶中
3、如果碰撞了，以链表的方式来链接在后面
4、如果链表长度超过阈值（TREEIFY_THRESHOLD = 8），链表转成红黑树
5、如果节点已经存在就替换值
6、如果桶满了（容量*加载因子），就需要resize()
hash函数实现
1、高16bit不变，低16位和高16bit异或
2、（n-1）& hash得到下标
其它实现方式??
扩容机制
何时扩容
当向容器添加元素的时候，元素个数size++大于等于阈值threshold—
即当前数组的长度乘以加载因子的值的时候(int)(capacity * loadFactor)，就要自动扩容啦。
即当前数组的长度乘以加载因子的值的时候(int)(capacity * loadFactor)，就要自动扩容啦。
扩容方法
resize(int newCapacity)
判断扩容前容量大小
初始化新Entry数组
通过transfer(newTable)方法将原来数组里的元素拷贝到新数组里
JDK1.7：使用大数组替换小数组，遍历旧数组，从新计算每个元素在新数组中的位置
多线程同时操作链表指针时可能出现死循环
JDK1.8:看原来的hash值新增的那个bit是1还是0就好了
新位置只可能在两个位置：原下标位置；《原下标+原容量》的位置
更新table,修改阈值
源码
其它
hash冲突的解决方法
开放地址法
链地址法
HashTable
键不可重复，值可重复
默认容量11
底层哈希表
线程安全
key、value都不能是null
TreeMap
键不可重复，值可重复
底层红黑树
0 条评论
下一页
