Java常用容器总结(List、Set、Map等)

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
0%