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)，就要自动扩容啦。
扩容方法
resize(int newCapacity)
判断扩容前容量大小
初始化新Entry数组
通过transfer(newTable)方法将原来数组里的元素拷贝到新数组里
JDK1.7：使用大数组替换小数组，遍历旧数组，从新计算每个元素在新数组中的位置
多线程同时操作链表指针时可能出现死循环
JDK1.8:看原来的hash值新增的那个bit是1还是0就好了
新位置只可能在两个位置：原下标位置；《原下标+原容量》的位置
源码
其它
hash冲突的解决方法
开放地址法
链地址法
HashTable
键不可重复，值可重复
默认容量11
线程安全
key、value都不能是null
TreeMap
底层红黑树
0 条评论
回复 删除
下一页
