Skip to Content

Java数据结构笔记

Posted on
Table of Contents

系统的看一下Java支持的数据结构，记一下从数据结构到java实现的一些基础笔记。以下内容主要参考《java核心技术》与jdk11源码。

用于保存对象的数据结构一般称作容器类，也称作泛型集合（generic collection，由于容易和Collection接口混淆，因此有些书直接叫做容器类container library）。主要分为Collection和Map两种，Collection用于存储独立的元素，而Map用于存储“键值对”对象。

一些细节

在查找元素、查找位置、移除等操作中，判断对象是否相同的方式是调用equal函数。

retainAll(Collection c)求两个集合的交集。

实现时接口与实现分离。使用时用满足需要的接口（如队列使用Queue），针对具体的场景new合适的实现。当需要自行实现对应的功能，为了降低实现接口中过多函数的复杂程度，可以直接扩展对应的Abastract类（如AbstractQueue），这种抽象接口加抽象类的方式在集合设计中经常遇到。

集合类只能容纳对象句柄。集合在存储基本类型时，会通过封装器（Integer等）将基本类型转换成普通类，因此在处理效率上不如数组（直接存储基本类型）。

迭代器 Iterator

public interface Iterator<E>{
  E next();
  boolean hasNext();
  void remove();
}
// 并没有一个函数直接返回迭代器指向位置的值

public interface Iterable<E>{
  Iterator<E> iterator();
}

for each循环可以针对任何实现了Iterable的对象（由编译器直接翻译成Iterator对应的代码）。for (String e: c){…}

Collection接口实现了Iterable接口，可以返回遍历元素的迭代器。

通过迭代器，能够用一套代码访问不同的容器类。

和C++的迭代器指向具体位置的设计不同，java的迭代器指向的位置可以看作是两个元素的中间。当调用next时，迭代器会跳过下一个元素，并返回被跳过元素的引用。不能像C++那样直接取当前位置的元素。对于remove函数，删除的是上一次next函数返回的位置（由于经常需要通过此位置的值判断是否删除）。也因此，每次调用remove函数前必须调用一次next方法，因此连续调用两次remove会出错。

List

ArrayList相当于dynamic array，随机访问快，随机插入慢。类似的实现还有Vector，相当于一个线程安全的ArrayList。

LinkedList，双向链表，随机访问慢，随机插入快。LinkedList比较特殊，除了List接口还是了双端队列的Deque接口。

LinkedList无法获取到node的指针，但可以通过获取ListIterator控制前后的位置（相对于Iterator，添加了previous等向前访问的函数）。

LikedList并没有缓存指针的位置，因此get(n)等随机访问和修改的操作效率不高。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Map

《java核心技术》中将Map的介绍放在了Set之后，但是Hashset的实现直接使用了HashMap，此处先写写Map的实现。

HashMap

（下面的默认参数取自openjdk11源码）

实现常量时间的数据get和put。

HashMap用hashcode结合链表的实现。使用了桶（bucket）机制，将hashcode取余后放入一个链表，当一个桶中的数据达到8个时，会通过treeifyBin函数将链表的形式转成红黑树存储以加快检索效率。

在构造函数中设置了两个参数。threshold（默认为16）和loadFactor（默认为0.75），初始化时桶的数量会用threshold，往后threshold会等于 桶的数量×loadFactor。添加元素时，HashMap中的元素个数达到threshold时会调用resize让桶的数量翻倍，此时会遍历先前的所有元素添加到扩容之后的数组中（rehash过程）。

通过一个名为table的数组存储桶的节点，默认情况下的初始化桶的个数为16，每次会增加为之前的2倍，最大为Int型的最大值。

transient Node<K,V>[] table;

static class Node<K,V> implements Entry<K,V> {
 final int hash;
 final K key;
 V value;
 Node<K,V> next;
 // ...
}

resize过程使用的头插入（新的table数组中插入的元素插入到链表头部，避免遍历到尾部的开销）。

当一个桶中的数据达到TREEIFY_THRESHOLD（8）个，并且桶的数量超过MIN_TREEIFY_CAPACITY（64）时，会在treeifyBin函数中将每个桶中的数据从链表转换成红黑树。

通过hashCode()函数得到hash值，通过equal()函数判断对象是否相等。

并发访问中，HashMap的实现中并没有考虑多线程的问题，在多线程结构化（structurally）修改HashMap时可能会出问题（结构化主要指添加和删除，修改某个key对应的值不算结构化修改）。

TreeMap

基于红黑树实现的Map，对于获取键值、插入、删除的操作时间复杂度为log(n)。put时将数据插入红黑树，get时从树中取数据。

由于数据存储在红黑树有序排列，获得排序后的数据较快。

将key-value键值对做为节点插入到红黑树中，由于需要排序，通过Comparator<? super K>接口让插入的键值可比较。

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;
	// ...
}

当类默认的比较函数不能满足需要时，可以另外定义新的comparator传入TreeMap。

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

EnumMap 用于枚举类型

所有的key必须是同一个enum类型中。内部通过数组的方式表达。每个类型对应数组中的一个元素。

put时直接获取key对应的enum位置，直接对数组中的此位置赋值。

private transient K[] keyUniverse;
private transient Object[] vals;

public V put(K key, V value) {
    typeCheck(key);
    int index = key.ordinal();
    Object oldValue = vals[index];
    vals[index] = maskNull(value);
    if (oldValue == null)
        size++;
    return unmaskNull(oldValue);
}

在put函数中，直接获取key对应的enum索引位置

LinkedHashMap实现原理

LinkedHashMap通过一个额外的双向链表链接所有的元素，通过构造函数中的参数accessOrder决定记录元素添加顺序还是元素访问顺序。

可以用来copy一个map，使新的map中的元素顺序与被赋值的map顺序相同（如下）。也适用于LRU cache类似的场景。

void foo(Map m) {
  Map copy = new LinkedHashMap(m);
  // ...
}

源码实现

总体逻辑为，每次添加新的元素，都回加入到链表的尾部。每次访问节点时，如果accessOrder为true（链表按照访问顺序），则将当前访问的节点放到链表尾部；当accessOrder为false（链表按照插入顺序），则不对链表操作。

通过两个指针可以获得所有元素的链表。

// 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;

jdk11的实现上略微有点跳，不同于jdk8直接重写了关键函数，jdk11通过多态的形式插入了一些和HashMap不同的操作。

想象中的让链表记录元素插入顺序的方式，直接在put新的元素后，直接将新的元素加入到链表（记录元素访问顺序在get函数中类似）。jdk11在实现时，在HashMap类中定义了三个空函数用于在LinkedHashMap中实现：

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

三个函数分别在Node的访问、插入、删除三种情况后被调用，在HashMap中为空函数，LinkedHashMap中具体实现。 但是，链表的插入顺序并没有直接放在afterNodeInsertion函数中，而是重写了创建新节点的newNode函数：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
     Entry<K,V> p =
         new Entry<>(hash, key, value, e);
     linkNodeLast(p); // 将p节点通过tail指针添加到链表尾部
     return p;
}

其它Map

WeakHashMap 值不用后会被回收，利用了GC机制中的标记。

IdentityHashMap 用==而非equals比较键值。

Set

接口和Colection基本相同，除了java9加了几个针对不可变集合的函数。

public interface Set<E> extends Collection<E> {...}

Set的内部很多都直接使用上面的Map实现，如HashSet内部直接使用了HashMap做为存储，在添加元素时，将加入的元素作为key，用一个常量作为value。

private transient HashMap<E,Object> map; 
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

LinkedHashSet 记录了插入的顺序。

TreeSet使用了TreeMap，通过红黑树适用于需要排序的数据。

EnumSet包含枚举类型

Queue

ArrayDeque and LinkedList

Deque(double-ended queue）双端队列，发音为|deck|。

常见的队列主要有ArrayDeque（数组实现的双端循环队列）和 LinkedList（链表实现的双端队列），其中LinkedList虽然名字是List，但实现了Queue的函数，定义如下）。

通常情况下ArrayDeque的数组型实现效率会高于LinkedList的指针型实现。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
	//...
}

双端循环队列的addFirst函数实现如下

// 其中Deque表示“double end queue”，发音为deck
public interface Deque<E> extends Queue<E> {...}

// ArrayDeque使用的是循环队列
// addFirst函数会向队列头部加入一个新的元素
// 当头部为0时，会通过dec函数将head指针移到数组尾部对应的位置
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    final Object[] es = elements;
    es[head = dec(head, es.length)] = e;
    if (head == tail)
        grow(1);
}

static final int dec(int i, int modulus) {
    if (--i < 0) i = modulus - 1;
    return i;
}

PriorityQueue

通过一个数组形式的堆实现最小优先队列，transient Object[] queue;，默认将最小值放在堆顶，peek()函数返回堆中最小值。没有直接的更改顺序的方式，如果需要将最大值放在堆顶需要传入Comparator接口的实现。

满足堆的性质，poll()函数返回队列中的最小值或者最大值O(log(n))。

Stack

public class Stack<E> extends Vector<E> {...}

public class Vector<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

LIFO (后进先出）

源码中的一些操作

位操作

用按位与操作提高取余效率

仅针对取余数为2^n次方的数。

对2取余实质上就是取2进制的最后一位，对4取余实质上是取2进制数的最后两位。

如 5 % 2 = （2进制）101 & 001。

2^n - 1 = （2进制的n个1）11….1

hash % n 等于 (n - 1) & hash

移位表示2^n

1 « 4 // 相当于2^4

当数组为2的倍数时，向左移m位相当于乘2的m次方

4 « m // 相当于 4*(2^m)

移位表示乘2和除2

22 » 1 // 除以二 22 « 1 // 乘2 22 »> 1 // 忽略符号位除以2

通过-1向右移位»>

对于8位的byte，-1 的源码为 10000001，因此可以通过»>得到一个00010000的2^n的数。

在HashMap中，hash桶的数量只能为2^n。下面的函数能够获取最小的n使2^n > cap。

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}