集合Map底层数据结构总结

文章资讯 2020-07-19 14:13:35

集合Map底层数据结构总结

3.4.1 hash map

整体框架是数组结构,每一个位置储存同hashcode的链表
与j7对比,j8变更的是,储存的链表改成红黑树,从On时间复杂度降低至Ologn
3.4.2 concurrentHashMap
不可扩容数组储存16个segment,每个sement为线程安全的数组,每一个数组类似hash map,数组的位置储存链表。
因此segment也被称为分段锁。合起来导致全局线程安全
因此,并发数最多是16个(并发的操作位置在不同的segment上)
3.4.3HashTable
遗留下的类,继承dictionary类,线程安全的,但没有CHM快,因为CHM有分段锁。线程不安全可用HM替代
3.4.3 TreeMap
加入了排序功能,迭代器,遍历的结果是排序后的
3.4.4 LinkedHashMap
加入了保有插入顺序的功能;迭代器,遍历的结果是排序后的