结构体系图
List
ArrayList,LinkedList,Vector 有什么区别?
ArrayList
只能装入引用对象(基本类型要转换为封装类);
线程不安全;
底层由数组实现(顺序表), 因为由顺序表实现, 所以会具备顺序表的特点, 如: 需要声明长度, 超出长度时需要进行扩容, 不适合频繁的移动删除元素, 检索元素快;
capacity 默认为 10, 超出时, capacity 自动增长 0.5 倍(oldCapacity>> 1);
Vector:
只能装入引用对象(基本类型要转换为封装类);
Vector 通过 synchronized 方法保证线程安全;
底层也由数组实现;
capacity 默认为 10(在构造方法中), 超出时增长 capacityIncrement 的量, capacityIncrement 小于等于 0 时, 则增长 1 倍
- ((capacityIncrement> 0) ? capacityIncrement : oldCapacity)
- LinkedList
只能装入引用对象(基本类型会转换为封装类);
线程不安全;
底层实现为链表, 具备链表的特点, 如: 不用声明长度, 检索性能较差, 但是插入移动删除较快.
链表通过 Node 对象实现
ArrayList 的扩容消耗
由于 ArrayList 使用
elementData = Arrays.copyOf(elementData, newCapacity);
进行扩容, 而
每次都会重新创建一个 newLength 长度的数组, 所以扩容的空间复杂度为 O(n), 时间复杂度为 O(n)
Arrays.asList 方法后的 List 可以扩容吗?
不能, asList 返回的 List 为只读的. 其原因为: asList 方法返回的 ArrayList 是 Arrays 的一个内部类, 并且没有实现 add,remove 等操作
而在 AbstractList 中, add 操作
如何使 List 线程安全
Collections.synchronizedList(list);
或者使用手动的方法保护线程安全.
List 是有序的吗?
这里的有序指有序性, 有序或无序是指是否按照其添加的顺序来存储对象, List 是有序的.
List 怎么实现排序?
实现排序, 可以使用自定义排序
list.sort(new Comparator(){...})
或者使用 Collections 进行快速排序
Collections.sort(list)
List 和 Array 之间如何互相转换?
Array 转 List:List list = new ArrayList(array);
List 转 Array:Object [] objects = list.toArray();
Set
Set 与 List 有什么区别?
Set
只能装入引用对象(基本类型要转换为封装类);
线程不安全
较 List, 是无序的(无法保证添加的顺序), 而且元素不能重复
底层使用了 map 进行实现(HashMap&LinkedHashMap), 借用 map 的 key 不能重复的特性, 来实现不重复性.
HashSet,LinkedHashSet,TreeSet 的区别?
都无法保证线程安全, 底层都使用 map 实现不重复性 (所以特性也在 map 中),Set 都不能使用 get(index) 的方法获取元素, 只能使用 iterator 进行获取. 其中:
HashSet
使用 HashMap, 无法保证有序性.
LinkedHashSet
使用 LinkedHashMap, 可以保证有序性
TreeSet
使用 NavigableMap, 可以使用 Comparator 来控制顺序
如何使 Set 线程安全
- Collections.synchronizedSet(set);
- Map
HashMap,LinkedHashMap,Hashtable,TreeMap 的区别?
HashMap
线程不安全
允许有一个 key 为 null
通过 hash 算法, 来确定 key 是否存在
不能保证有序性
默认大小为 16, 每次扩容默认增大 1 倍. 默认情况下, 数组大小为 16, 那么当 HashMap 中元素个数超过 16*0.75=12(这个值就是代码中的 threshold 值, 也叫做临界值)的时候, 就把数组的大小扩展为 2*16=32, 即扩大一倍.
LinkedHashMap
HashMap 的子类, 将结构与操作更改为链表形式
线程不安全
accessOrder 默认 fasle, 可以保证有序性
在 HashMap 的线性单向链表的基础上, 内部维护了一个双向链表
Hashtable
父类为 Dictionary, 与 HashMap 不同
线程安全, 方法通过 synchronized 同步
key&value 都不能为 null
不能保证有序性
默认大小为 11, 其余与 HashMap 一致
TreeMap
线程不安全
内部使用红黑树, 需要 key 实现 Comparable 接口
可以定义 Comparator 控制顺序
迭代遍历时使用中序遍历
如何使 Map 线程安全
Collections.synchronizedMap(map);
什么样的对象适合做为键, 有什么要求?
String,Interger 这样的类是 final 类型的, 具有不可变性, 且重写了 equals()和 hashCode()方法. 换言之, 做为 key 的对象, 不可变性是必要的, 因为要计算 hashCode(), 要防止放入时和取出时 hashcode 不一致. 此外还需要重写 equals()和 hashCode()方法, 用于比较对象一致性.
HashMap 初始化传入的容量参数的值就是 HashMap 实际分配的空间么?
不是, 是比传入容量参数值大的最小的 2 的 n 次方, 比如传入 6, 实际分配 8.
HashMap 的底层数据结构是什么?
是一个数组, 结合了顺序表 + 单向链表的形式, 内部的每一个节点都是 Node 对象
附录
推荐几篇描述 map 原理还不错的文章
- https://blog.csdn.net/uhgagnu/article/details/54982960
- http://baijiahao.baidu.com/s?id=1585269929754900992&wfr=spider&for=pc
来源: https://www.cnblogs.com/qbzf-Blog/p/9002137.html