2021-09-29 Collection集合

• Collection
• • List
  • • ArrayList
    • linkedList
  • Set
  • • HashSet
    • TreeSet
• Map
• • HashMap
  • linkedHashMap
  • TreeMap
  • Hashtable

ArrayList：非线程安全

原理：数组

性质：查询效率高，增加效率低；当不考虑查询效率或元素个数少的时候可以使用ArrayList；

linkedList：非线程安全

原理：链表

性质：查询效率低，增加效率高；当出现大量添加而不需要大量的查询的时候可以考虑使用linkedList；

HashSet：非线程安全

原理：本质上还是HashMap，维护了一个HashMap map；

性质：不存在相同的元素，且查询与添加的效率较高；

TreeSet：非线程安全

原理：与TreeMap相同——红黑树

性质：每次添加元素时，会找到一个叶子结点去存放，但当树出现不平衡的情况下，需要进行平衡，查询效率相对较高，添加效率一般（主要原因在于树的平衡）

HashMap：非线程安全

原理：数组+链表+红黑树（JDK1.8后）、数组+链表（JDK1.7）

性质：以牺牲空间来换取时间，每个元素以键值对的方式进行存储；添加元素时，会先计算哈希值进行位运算找到对应的桶位，若桶位以有元素，将以链表的方式存在相同的桶位下，当冲突严重链表的长度达到8时进行树（红黑树）化；若元素个数达到集合容量的75%时（装填因子0.75），将会触发扩容机制；

linkedHashMap：非线程安全

原理：数组+链表+红黑树+双向链表（JDK1.8后）、数组+链表+双向链表（JDK1.7）

性质：在继承HashMap的数据结构基础上多了双向链表，保持快速查询，还具有添加顺序与，遍历顺序相同的性质

TreeMap：非线程安全

原理：红黑树

性质：继承于SortedMap接口，性质与红黑树性质相同；

在官方注释里说，Java集合框架与新的集合实现不同，{@code Hashtable}是同步的。如果不需要线程安全的实现，建议使用{@link HashMap}代替{@code Hashtable}。如果需要一个线程安全的高并发实现，那么推荐使用{@link java.util.concurrent.ConcurrentHashMap}代替{@code Hashtable}

因此，当选择使用Hashtable不需要线程安全时，可以选择使用HashMap；在高并发的情况下可选择ConcurrentHashMap