您的位置: 首页  >  IT文章  >  Java 集合类 1 List 2 Map 3 Set 4 Stack 5 Queue / Deque

Java 集合类 1 List 2 Map 3 Set 4 Stack 5 Queue / Deque

分类: IT文章 • 2022-03-28 20:09:34

Java 集合类 1 List 2 Map 3 Set 4 Stack 5 Queue / Deque

  1.1 ArrayList

      基于数组实现，按照插入顺序排序，可重复，线程不安全，默认初始化为空数组对象，在添加第一个元素时，初始化大小为10的数组。支持自动扩容，扩展因子为0.5，即 newCapacity=oldCapacity*1.5，扩容方式是 Arrays.copyOf(elementData, newCapacity);。

  1.2 Vector

     基于数组实现，按照插入顺序排序，可重复，通过 synchronized 来保证线程安全，默认初始化大小为10的数组。添加元素时。支持自动扩容，扩展因子为1，即 newCapacity=oldCapacity*2，扩容方式是 Arrays.copyOf(elementData, newCapacity);。

  1.3 LinkedList

      基于双向链表实现，按照插入顺序排序，实现了接口 Deque，所以它也是一个双端队列。

1 // 双端链表结构 
2 private static class Node<E> { 
3     E item; Node<E> next; Node<E> prev; 
4 }
View Code

2 Map

  2.1 HashMap

      基于散列链表+红黑树实现，无序，链表长度>=8时转为红黑树，红黑树<=6时转为链表，首次添加元素时，初始化默认数组长度16，并且必须是2的幂次方大小，当指定的大小不够2的幂次方时自动补齐大小，默认加载因子0.75，默认扩展因子1，线程不安全。

 1 // 哈希链表结构
 2 static class Node<K,V> implements Map.Entry<K,V> {
 3     final int hash; // 数组索引
 4     final K key;
 5     V value;
 6     Node<K,V> next; // 下一个节点
 7 }
 8 // 红黑树结构
 9 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
10     TreeNode<K,V> parent;
11     TreeNode<K,V> left;
12     TreeNode<K,V> right;
13     TreeNode<K,V> prev;
14     boolean red;
15 }
View Code

      添加元素时为了更均匀地分布，对 key 进行两次的 hash 运算。

1 static final int hash(Object key) {
2     int h;
3     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
4 }
View Code

      扩容方式：resize()，扩容后的容量是之前的2倍。

 1 Node<K,V> loHead = null, loTail = null;
 2 Node<K,V> hiHead = null, hiTail = null;
 3 Node<K,V> next;
 4 do {
 5     next = e.next;
 6     if ((e.hash & oldCap) == 0) { // 索引没有变化
 7         if (loTail == null)
 8             loHead = e;
 9         else
10             loTail.next = e;
11         loTail = e;
12     }
13     else { // 索引变为原索引+oldCap
14         if (hiTail == null)
15             hiHead = e;
16         else
17             hiTail.next = e;
18         hiTail = e;
19     }
20 } while ((e = next) != null);
21 if (loTail != null) {
22     loTail.next = null;
23     newTab[j] = loHead;
24 }
25 if (hiTail != null) {
26     hiTail.next = null;
27     newTab[j + oldCap] = hiHead;
28 }
View Code

      线程安全性问题

      1、put 导致数据丢失；

      2、resize 导致的 get 操作时的死循环，JDK 8 已经解决此问题，利用 head 和 tail 来保证链表的顺序不变，避免导致死循环；

  2.2 HashTable

      基于散列链表实现，默认数组长度11，默认加载因子0.75，默认扩展2*原数组长度+1，利用 synchronized 保证线程安全。

  2.3 TreeMap

      基于红黑树实现，按 key 自然排序。key 不等于 null。

  2.4 LinkedHashMap

      利用 HashMap 来实现。散列双向链表的结构。

1 static class Entry<K,V> extends HashMap.Node<K,V> {
2     Entry<K,V> before, after;
3 }
View Code

      accessOrder 的排序方式：

  • accessOrder=false（默认）表示按插入顺序排序
  • accessOrder=true 表示按访问顺序排序(最少被访问的靠前，最近访问的靠后)，可用于实现LRU算法（Least recently used，最近最少使用算法）

3 Set

  3.1 HashSet

      利用 HashMap 实现，无序，去重，默认初始化为默认的 HashMap，value 固定为 Object 对象，可以参考 HashMap 的实现。

1 // 初始化
2 public HashSet() {
3     map = new HashMap<>();
4 }
5 // 添加元素
6 public boolean add(E e) {
7     return map.put(e, PRESENT)==null;
8 }
View Code

  3.2 TreeSet

      利用 TreeMap 实现，自然排序，去重，不能添加 null，默认初始化为默认的 TreeMap，value 固定为 Object 对象，可以参考 TreeMap 的实现。

  3.3 LinkedHashSet

      继承了 HashSet，利用 LinkedHashMap 实现，可以参考 LinkedHashMap 的实现。

4 Stack

      栈的结构，继承了 Vector 类，利用 synchronized 来保证线程安全。

5 Queue / Deque

      队列 / 双端队列的结构，Deque 继承 Queue 接口。

      常见实现：

  • PriorityQueue，优先队列，默认初始化长度为 11，通过二叉小顶堆实现，保证每次取出值最小的元素。
  • ArrayDeque，数组实现的双端队列，默认初始化长度为 16，FIFO 原则。
  • LinkedList
  • BlockingQueue，阻塞队列，详见《并发集合包》。

相关推荐