List, Set, Map
- List:元素可以不唯一、有序
- Set:不允许元素重复
- Map:键值对。Key不能重复
ArrayList, LinkedList, Vector
- 线程安全:ArrayList 和 LinkedList 是不同步的;Vector 是同步的(始于JDK1.0,后被ArrayList取代)
- 数据结构:ArrayList 底层是Object数组;LinkedList 是双向链表(JDK1.6之前为循环链表,JDK1.7取消了循环)
- 快速随机访问:通过元素的序号快速获取元素对象(对应于get(int index)方法)。LinkedList 不支持,而ArrayList 支持。
HashMap 和 Hashtable
- 线程安全:HashMap 是非线程安全的,效率较高;HashTable是线程安全的(始于JDK1.0,内部的方法基本都经过 synchronized 修饰,现在基本被淘汰),效率较低。并发环境下推荐使用 ConcurrentHashMap。
- HashMap允许null作为键,这样的键只能有一个;HashTable中若键为null会NPE
- 初始容量和扩容大小:Hashtable默认初始大小为11,每次扩充变为原来的2n+1;HashMap 默认的初始化大小为16,每次扩充容量变为原来的2n。
- 数据结构:JDK1.8以后,HashMap在解决哈希冲突时,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable没有这样的机制。
- 关于Hashtable:Hashtable的第二个t小写是sun的失误,后来sun也确实讨论过这个t的问题,但由于Hashtable是jdk1.0的产物,替换会导致很多老的系统无法兼容,于是sun决定保留小写t
HashMap 和 HashSet
- HashSet 底层就是基于 HashMap 实现的。
HashMap | HashSet |
---|---|
实现了Map接口 | 实现Set接口 |
存储键值对 | 仅存储对象 |
调用 put() 向map中添加元素 |
调用 add() 方法向Set中添加元素 |
HashMap使用键(Key)计算Hashcode | HashSet使用成员对象来计算hashcode值,对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性, |
HashSet如何检查重复
- 先计算对象hashcode,与其他加入的对象的hashcode值作比较,如果没有相同的,则会调用equals() 方法检查hashcode相同的对象是否真的相同。如果两者相同,HashSet就不会允许加入操作成功。
ConcurrentHashMap 和 HashMap
- 线程安全:
- ConcurrentHashMap(分段锁):JDK1.7时,对整个桶数组进行了分割分段(Segment);JDK1.8时摒弃了Segment概念,采用Node数组+链表+红黑树的数据结构实现,并发控制用synchronized和CAS来操作。
- Hashtable(同一把锁):使用 synchronized 来保证线程安全,效率非常低下。
Comparable和Comparator
- Comparable出自java.lang包,它有一个compareTo()方法
- Comparator出自java.util包,它有一个compare()方法
集合的选择
- 键值选Map,排序选TreeMap,不排序HashMap,线程安全ConcurrentHashMap
- 存放元素Collection,保证唯一选Set如TreeSet或HashSet,不唯一选ArrayList或LinkedList