关于java:13分钟了解Java容器

49次阅读

共计 12707 个字符，预计需要花费 32 分钟才能阅读完成。

List

Vector

采纳 Object 数组存储元素

protected Object[] elementData;

Stack

Stack继承了 Vector，采纳Object 数组存储元素

ArrayList

顾名思义，ArrayList底层采纳数组存储元素

Object[] elementData;

LinkedList

顾名思义，LinkedList底层采纳链表存储元素。通过 first 和last指针别离指向头元素和尾元素。

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;
/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

其中 Node 是LinkedList自定义的动态类，通过 next 和prev指针别离指向后驱节点和前驱节点。因而 LinkedList 底层是通过 first 和last指针别离指向头元素和尾元素的 双向链表。

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

CopyOnWriteArrayList

顾名思义，CopyOnWriteArrayList底层是通过 Object[] 数组存储数据，提供的构造方法在初始化时主动创立了长度为0 的数组。

/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;
/**
 * Creates an empty list.
 */
public CopyOnWriteArrayList() {setArray(new Object[0]);
}

CopyOnWrite的逻辑大体上都是在插入数据的时候，从新复制一份数组，在新数组中插入新数据，之后将指针指向新的数组。这种模式次要是为了针对“改变操作很少，次要是读操作”的业务。CopyOnWriteArrayList一样，在操作数据时通过 ReentrantLock 锁住避免并发之后，复制原数组再在新数组中操作数据，最初将指针指向新数组。

  • 相干代码
public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {Object[] elements = getArray();
        E oldValue = get(elements, index);

        if (oldValue != element) {
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len);
            newElements[index] = element;
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        return oldValue;
    } finally {lock.unlock();
    }
}

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {lock.unlock();
    }
}

public E remove(int index) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {Object[] elements = getArray();
        int len = elements.length;
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1));
        else {Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally {lock.unlock();
    }
}

Map

HashTable

HashTable底层通过 Entry 数组存储元素，

private transient Entry<?,?>[] table;
  • 其中 Entry 类型为 HashTable 自定义的数据结构，外部记录了元素的 hash 值，key，value，以及下一节点的指针next。
private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;
    protected Entry(int hash, K key, V value, Entry<K,V> next) {
        this.hash = hash;
        this.key =  key;
        this.value = value;
        this.next = next;
    }
    @SuppressWarnings("unchecked")
    protected Object clone() {
        return new Entry<>(hash, key, value,
                              (next==null ? null : (Entry<K,V>) next.clone()));
    }
    // Map.Entry Ops
    public K getKey() {return key;}
    public V getValue() {return value;}
    public V setValue(V value) {if (value == null)
            throw new NullPointerException();
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }
    public boolean equals(Object o) {if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
           (value==null ? e.getValue()==null : value.equals(e.getValue()));
    }
    public int hashCode() {return hash ^ Objects.hashCode(value);
    }
    public String toString() {return key.toString()+"="+value.toString();}
}

HashMap

HashMap底层通过 Node数组存储元素

transient Node<K,V>[] table;
  • 其中 Node 是HashMap自定义的数据结构，外部记录了元素的 hash 值，key，value，以及下一节点的指针next。
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    public final K getKey()        { return key;}
    public final V getValue()      { return value;}
    public final String toString() { return key + "=" + value;}
    public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final boolean equals(Object o) {if (o == this)
            return true;
        if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

当元素 hash 雷同时，元素会通过链表的模式通过 next 指针相连。在 JDK1.8 之后，当满足肯定条件后，链表会转化为红黑树，此时，元素会从 Node 类型转化为 TreeNode 类型。

  • TreeNode为 HashMap 自定义的数据结构，外部记录父节点 parent，左右孩子left，right，色彩标记red 曾经同级前驱节点prev
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);
    }
    ......
 }

具体的操作逻辑能够参考：[[HashMap]]

LinkedHashMap

LinkedHashMap继承了 HashMap 的逻辑，只不过增加了 Entry 构造。以及 head，tail 首尾指针。

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);
    }
}
private static final long serialVersionUID = 3801124242820219131L;
/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;
/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;

Entry中保留了 before 和after指针，指向上一个插入元素 Entry 以及后一个插入元素 Entry。以 数组 +红黑树 + 元素链表 + 插入程序链表的模式存储数据。

ConcurrentHashMap

ConcurrentHashMap底层通过 Node 数组存储数据

transient volatile Node<K,V>[] table;
  • 其中 Node 是ConcurrentHashMap自定义的数据结构，外部记录了元素的 hash 值，key，value，以及下一节点的指针next。
static class Node<K,V> implements Map.Entry<K,V> {
      final int hash;
      final K key;
      volatile V val;
      volatile Node<K,V> next;
      Node(int hash, K key, V val, Node<K,V> next) {
          this.hash = hash;
          this.key = key;
          this.val = val;
          this.next = next;
      }
      public final K getKey()       { return key;}
      public final V getValue()     { return val;}
      public final int hashCode()   { return key.hashCode() ^ val.hashCode();}
      public final String toString(){ return key + "=" + val;}
      public final V setValue(V value) {throw new UnsupportedOperationException();
      }
      public final boolean equals(Object o) {
          Object k, v, u; Map.Entry<?,?> e;
          return ((o instanceof Map.Entry) &&
                  (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
                  (v = e.getValue()) != null &&
                  (k == key || k.equals(key)) &&
                  (v == (u = val) || v.equals(u)));
      }
      /**
       * Virtualized support for map.get(); overridden in subclasses.
       */
      Node<K,V> find(int h, Object k) {
          Node<K,V> e = this;
          if (k != null) {
              do {
                  K ek;
                  if (e.hash == h &&
                      ((ek = e.key) == k || (ek != null && k.equals(ek))))
                      return e;
              } while ((e = e.next) != null);
          }
          return null;
      }
  }

当元素 hash 雷同时，元素会通过链表的模式通过 next 指针相连。在 JDK1.8 之后，当满足肯定条件后，链表会转化为红黑树，此时，table 数组中的 Node 元素会转化为 TreeBin 类型，TreeBin 类型记录了由 TreeNode 形成红黑树的根节点 root。

  • TreeBin有 ConcurrentHashMap 自定义，继承了 Node 类型。寄存了下辖红黑树的根节点root。
static final class TreeBin<K,V> extends Node<K,V> {
    TreeNode<K,V> root;
    volatile TreeNode<K,V> first;
    volatile Thread waiter;
    volatile int lockState;
    // values for lockState
    static final int WRITER = 1; // set while holding write lock
    static final int WAITER = 2; // set when waiting for write lock
    static final int READER = 4; // increment value for setting read lock
    ......
}
  • TreeNode由 ConcurrentHashMap 自定义，跟 HashMap 的TreeNode相似，然而 ConcurrentHashMap 的TreeNode继承自 Node 类型。
static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next,
             TreeNode<K,V> parent) {super(hash, key, val, next);
        this.parent = parent;
    }
    ......
}

具体的操作逻辑能够参考：[[ConcurrentHashMap]]

TreeMap

TreeMap 通过 Entry 存储数据，底层是以红黑树的逻辑构造存储。

private transient Entry<K,V> root;
  • Entry是 TreeMap 自定义的数据结构，其中蕴含key，value，左右子树left，right，以及父节点parent，和标记色彩的color；
static final class Entry<K,V> implements Map.Entry<K,V> {
      K key;
      V value;
      Entry<K,V> left;
      Entry<K,V> right;
      Entry<K,V> parent;
      boolean color = BLACK;
      /**
       * Make a new cell with given key, value, and parent, and with
       * {@code null} child links, and BLACK color.
       */
      Entry(K key, V value, Entry<K,V> parent) {
          this.key = key;
          this.value = value;
          this.parent = parent;
      }
      ......
}

WeakHashMap

WeakHashMap底层通过 Entry[] 数组存储数据，采纳链表法解决hash 抵触，跟 HashMap 不同没有 进行长链表的红黑树转化。

Entry<K,V>[] table;
  • Entry为 WeakHashMap 自定义的数据结构继承了 WeakReference，其中蕴含value，hash 值，以及 next 指针。key为 弱援用 reference 的值。
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    V value;
    final int hash;
    Entry<K,V> next;
    /**
     * Creates new entry.
     */
    Entry(Object key, V value,
          ReferenceQueue<Object> queue,
          int hash, Entry<K,V> next) {super(key, queue);
        this.value = value;
        this.hash  = hash;
        this.next  = next;
    }
    ......
}

具体的操作逻辑能够参考：[[WeakHashMap]]

ConcurrentSkipListMap

ConcurrentSkipListMap底层通过跳表的数据结构进步查找效率。ConcurrentSkipListMap通过 Node 存储根本的 key,value 数据，Index存储跳表索引，HeadIndex为层级头索引。

// Node 存储根本的 key,value 数据，是一个简略的链表
static final class Node<K,V> {
    final K key;
    volatile Object value;
    volatile Node<K,V> next;
    ...
}
// Index 内蕴含 Node 元素，以及向下和向右的 Index 指针
static class Index<K,V> {
    final Node<K,V> node;
    final Index<K,V> down;
    volatile Index<K,V> right;
    ...
} 
// HeadIndex 继承了 Index, 增加了 level 索引层级属性
static final class HeadIndex<K,V> extends Index<K,V> {
    final int level;
    HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {super(node, down, right);
        this.level = level;
    }
}

同时，ConcurrentSkipListMap通过对大部分操作增加 CAS 锁避免并发。

Set

HashSet

HashSet底层默认通过 HashMap 存储元素，数据贮存在 HashMap 的key中，value设置为默认值Object。

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object(); // default value
public boolean add(E e) {return map.put(e, PRESENT)==null;
}

HashSet 底层还能够通过 LinkedHashMap 存储元素。依据结构函数参数不同抉择是 HashMap还是 LinkedHashMap 实现。

HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

LinkedHashSet

LinkedhashSet继承了 HashSet，采纳LinkedHashMap 存储元素。

ConcurrentSkipListSet

底层通过 ConcurrentSkipListMap 实现，寄存的值作为 key 存入 ConcurrentSkipListMap 中，应用 Boolean.TRUE 对象最为默认的value。

private final ConcurrentNavigableMap<E,Object> m;

/**
 * Constructs a new, empty set that orders its elements according to
 * their {@linkplain Comparable natural ordering}.
 */
public ConcurrentSkipListSet() {m = new ConcurrentSkipListMap<E,Object>();
}

public boolean add(E e) {return m.putIfAbsent(e, Boolean.TRUE) == null;
}

TreeSet

TreeSet底层通过 TreeMap 存储元素，和 HashSet 相似，数据存储在 TreeMap 的Key中，value设置为默认值Object。

private transient NavigableMap<E,Object> m;
  // Dummy value to associate with an Object in the backing Map
  private static final Object PRESENT = new Object();
  
  public TreeSet(Comparator<? super E> comparator) {this(new TreeMap<>(comparator));
  }

CopyOnWriteArraySet

底层通过 CopyOnWriteArrayList 实现，通过 List.addIfAbsent() 办法实现同一个元素只存在一个，保障了元素的唯一性。

private final CopyOnWriteArrayList<E> al;

/**
 * Creates an empty set.
 */
public CopyOnWriteArraySet() {al = new CopyOnWriteArrayList<E>();
}

public boolean add(E e) {return al.addIfAbsent(e);
}

Queue

PriorityQueue

PriorityQueue优先队列，底层通过 Object 数组存储元素，Object[]以档次遍历的模式存储优先队列（齐全二叉树）的元素值。索引 n 的左右孩子索引别离为 $2n+1,2*(n+1)$;

transient Object[] queue;

BlockingQueue

A Queue that additionally supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element.

阻塞队列接口，提供了额定的一些操作，当这些操作无奈立刻执行时（插入时容量满了、删除 / 获取元素时队列为空），不会像失常的 queue 一些立刻返回而是 阻塞一段时间 直到满足条件（设置了等待时间、条件满足了）

阻塞队列的阻塞操作个别是通过创立多个条件锁 ReentrantLock.Condition 实现的，通过调用 Condition.await() 以及 Condition.signal() 进行线程的 阻塞和唤醒。

private final Condition notEmpty;

/** Condition for waiting puts */
private final Condition notFull;

  • 增加元素

    • add(E e)/offer(E e)办法，当数组满了之后，间接返回false

      public boolean offer(E e) {checkNotNull(e);
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {if (count == items.length)
            return false;
        else {enqueue(e);
            return true;
        }
    } finally {lock.unlock();
    }
}

    • put(E e)/offer(E e, long timeout, TimeUnit unit)办法，当数组满了之后，阻塞直到唤醒或者阻塞指定工夫

      public void put(E e) throws InterruptedException {checkNotNull(e);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {while (count == items.length)
            notFull.await();
        enqueue(e);
    } finally {lock.unlock();
    }
}

public boolean offer(E e, long timeout, TimeUnit unit)
    throws InterruptedException {checkNotNull(e);
    long nanos = unit.toNanos(timeout);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {while (count == items.length) {if (nanos <= 0)
                return false;
            nanos = notFull.awaitNanos(nanos);
        }
        enqueue(e);
        return true;
    } finally {lock.unlock();
    }
}

  • 获取元素

    • poll()，弹出队首元素，队列为空时间接return null;
    • take()，弹出队首元素，队列为空时 阻塞至队列不为空。
    • poll(long timeout, TimeUnit unit)，弹出队首元素，队列为空时 阻塞指定工夫后 重试一次。
    • peek()，获取 队首元素，队列为空时间接return null;

ArrayBlockingQueue

A bounded BlockingQueue backed by an array. This queue orders elements FIFO (first-in-first-out). The head of the queue is that element that has been on the queue the longest time. The tail of the queue is that element that has been on the queue the shortest time. New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements at the head of the queue.

顾名思义，ArrayBlockingQueue底层是通过 Object[] 数组实现元素的存储的。ArrayBlockingQueue是 有界队列 ，存储元素的数量通过 初始化办法指定 。当数组满了的时候，就无奈 间接 往数组中增加元素了。ArrayBlockingQueue FIFO，增加元素到队尾，删除队首元素。

  • 初始化办法

    public ArrayBlockingQueue(int capacity, boolean fair) {if (capacity <= 0)
        throw new IllegalArgumentException();
    this.items = new Object[capacity];
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull =  lock.newCondition();}

LinkedBlockingQueue

依据初始化参数动静结构是否有界的阻塞队列。底层通过 Node 构造实现的链表进行存储。

  • Node 构造

    static class Node<E> {
    E item;

    Node<E> next;

    Node(E x) {item = x;}
}

  • 初始化办法

    public LinkedBlockingQueue() {
    // 不指定队列容量，默认为 Integer 的最大值
    this(Integer.MAX_VALUE);
}

public LinkedBlockingQueue(int capacity) {if (capacity <= 0) throw new IllegalArgumentException();
    this.capacity = capacity;
    last = head = new Node<E>(null);
}

ArrayBlockingQueue 和 LinkedBlockingQueue 除了底层实现形式不同之外，ArrayBlockingQueue在进行数据操作时用的都是同一把锁 final ReentrantLock lock;，而LinkedBlockingQueue 初始化了二把锁插入和弹出操作应用不同的锁。final ReentrantLock putLock；final ReentrantLock takeLock；

正文完
java
发表至： java
2020-11-14
 0
细数研究生和导师的那些恩怨情仇
基础查询
BeginnersBook-Java-字符串教程
Eclipse-如何链接数据库