JAVA 集合类简述

Posted on

JAVA集合继承关系

Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│　└Stack
└Set-HashSet

Map
├HashTable
├HashMap
│　└LinkedHashMap
├WeakHashMap

ArrayList VS LinkedList

ArrayList

  • 基于数组，在数组中搜索和读取数据是很快的。因此 ArrayList 获取数据的时间复杂度是O(1);
  • 但是添加、删除时该元素后面的所有元素都要移动，所以添加/删除数据效率不高；
  • 另外其实还是有容量的，每次达到阈值需要扩容，这个操作比较影响效率。

LinkedList

  • 实现了Queue、Deque接口，可以用作队列和栈；
  • 基于双端链表，添加/删除元素只会影响周围的两个节点，开销很低；（JDK1.7之前使用双向循环链表实现）；
  • 只能顺序遍历，无法按照索引获得元素，因此查询效率不高；
  • 没有固定容量，不需要扩容；
  • 需要更多的内存，每个节点中需要多存储前后节点的信息，占用空间更多些。

Map

HashMap

  • 底层实现是 链表数组，JDK 8 后又加了 红黑树
  • 允许空键和空值（但空键只有一个，且放在第一位）
  • 元素是无序的，而且顺序会不定时改变
  • 插入、获取的时间复杂度基本是 O(1)（前提是有适当的哈希函数，让元素分布在均匀的位置）
  • 遍历整个 Map 需要的时间与 桶(数组) 的长度成正比（因此初始化时 HashMap 的容量不宜太大）
  • 两个关键因子：初始容量、加载因子。默认初始容量：16，必须是 2 的整数次方；默认加载因子的大小：0.75
  • 哈希表容量取 2 的整数次幂，有以下 2 点好处：散列函数hash&(length-1)使用减法替代取模，提升计算效率；为了使不同 hash 值发生碰撞的概率更小，尽可能促使元素在哈希表中均匀地散列。

LinkedHashMap

LinkedHashMap继承自HashMap，增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序

迭代注意事项

ArrayList使用for循环和Iterator效率差不多，这两种方式原理一样，调用get方法，ArrayList采用数组，随机存取效率高；
LinkedList推荐使用Iterator进行迭代，LinkedList内部的Iterator通过遍历链表实现迭代，效率高；若使用for循环，get方法需要循环一半的链表，效率较低。

使用原则

如果涉及到堆栈，考虑用Deque，并发考虑Stack；对于需要快速插入，删除元素，应该使用LinkedList；如果需要快速随机访问元素，应该使用ArrayList。

缺省使用非同步的类，其效率较高；如果多个线程可能同时操作一个类，应该使用同步的类：Vector、Hashtable。

要特别注意对哈希表的操作，作为key的对象要正确复写equals和hashCode方法。