本文最后更新于：2022年7月3日下午

JAVA集合框架结构

首先我们知道JAVA的集合框架中有两大体系，一类是Collection，另一类是Map。其中Collection中包含List(ArrayList、LinkedList、Vector、还有继承自Vector的Stack)、Set(HashSet、LinkedHashSet、继承自Set的SortedSet接口下的TreeSet)、Queue(继承自Queue的Deque双向队列)。

Map下包括HashMap、LinkedHashMap、(继承自Map的SortedMap接口，以及其实现类TreeMap)、Hashtable等实现类。下面就一个一个来进行解析。

Collection

List（列表）

List接口下有ArrayList、LinkedList（LinkedList是实现了List接口和Deque接口的类）、Vector、Stack

ArrayList

ArrayList 是一个动态数组结构，支持随机存取，尾部插入删除方便，内部插入删除效率低（因为要移动数组元素）；如果内部数组容量不足则自动扩容，因此当数组很大时，效率较低。

ArrayList是我们平时使用的比较多的一个数据结构了，其底层实现为Array数组，我们看看他的代码。

transient Object[] elementData; // 存储数据的数组
private int size;//容器当前的大小
private static final int DEFAULT_CAPACITY = 10;//默认大小
//带初始化容量的构造函数
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
//无参构造函数
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//实现Collection接口的子类的构造函数
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

我们看到其如果进行无参构造的话，那么会得到一个DEFAULT_CAPACITY=10的ArrayList，如果有指定初始容量，且大小合规的话，那么就创建初始化大小的ArrayList，如果参数是实现了Collection接口的，那么就调用Collection接口下的toArray()方法，将其变成数组，然使用Arrays.copyof()方法将原来容器内的元素拷贝到当前ArrayList下。

需要注意的是其大小达到其容量的时候会触发grow()方法。

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

可以看到其扩容后的容量为int newCapacity = oldCapacity + (oldCapacity >> 1);即新容量=旧容量*1.5；

LinkedList

LinkedList 是一个双向链表结构，在任意位置插入删除都很方便，但是不支持随机取值，每次都只能从一端开始遍历，直到找到查询的对象，然后返回；不过，它不像 ArrayList 那样需要进行内存拷贝，因此相对来说效率较高，但是因为存在额外的前驱和后继节点指针，因此占用的内存比 ArrayList 多一些。

transient Node<E> first;//看到first和last
transient Node<E> last;
transient int size = 0;
//内部类节点
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;
    }
}
//包含两个构造函数
//第一个什么都没干，就是初始化了成员变量
public LinkedList() {
}
//第二个就是将继承自Collection接口的元素一个一个链接起来
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

下面看一下其add方法。

public boolean add(E e) {
    //调用了linkLast方法将其元素链接到尾节点中
    linkLast(e);
    return true;
}
void linkLast(E e) {
    final Node<E> l = last;
    //在构造方法中将前驱指针置为当前last元素，后记节点置为Null;
    final Node<E> newNode = new Node<>(l, e, null);
    //last节点
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

Vector

Vector 也是一个动态数组结构，一个元老级别的类，早在 jdk1.1 就引入进来类，之后在 jdk1.2 里引进 ArrayList，ArrayList 大部分的方法和 Vector 比较相似，两者是不同的，Vector 是允许同步访问的，Vector 中的操作是线程安全的，但是效率低，而 ArrayList 所有的操作都是异步的，执行效率高，但不安全！需要注意的是Vector和ArrayList的扩容方式有所区别，Vector的扩容是新容量=旧容量*2

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

关于Vector，现在用的很少了，因为里面的get、set、add等方法都加了synchronized，所以，执行效率会比较低，如果需要在多线程中使用，可以采用下面语句创建 ArrayList 对象

1	`List<Object> list =Collections.synchronizedList(new ArrayList<Object>());`

也可以考虑使用复制容器 java.util.concurrent.CopyOnWriteArrayList进行操作，例如：

1	`final CopyOnWriteArrayList<Object> cowList = new CopyOnWriteArrayList<String>(Object);`

其底层代码和ArrayList基本相同，不同点在于其对数组的操作都加入了synchronized关键词，所以保证了其再多线程条件下也是可以保证其线程的安全性的，但是由于使用了sychronized关键词，所以导致其效率不太行。所以一般推荐使用Collections.synchronizedList进行操作，是因为Vector读写性能可以和Collections.synchronizedList比肩(因为虽然一个是是在方法上进行加锁，另一个是在同步代码块内加锁，但是其锁住的范围几乎相同)，但Collections.synchronizedList不仅可以包装ArrayList,也可以包装其他List,扩展性和兼容性更好。

Stack

Stack 是 Vector 的一个子类，本质也是一个动态数组结构，不同的是，它的数据结构是先进后出，取名叫栈！

关于Stack，现在用的也很少，因为有个ArrayDeque双端队列，可以替代Stack所有的功能，并且执行效率比它高！

Set(集合)

HashSet

说到HashSet，那就不得不说HashMap，HashSet底层是基于 HashMap 的k实现的，元素不可重复，特性同 HashMap。

具体的实现与HashMap不同的是，其value是固定的一个Object对象。

我们可以查看源码

private static final Object PRESENT = new Object();
//内置的HashMap对象。
private transient HashMap<E,Object> map;

每次进行add操作的时候都是执行了

public boolean add(E e) {
    //Put一个固定的元素。
    return map.put(e, PRESENT)==null;
}

其他的部分和HashMap基本相同，如果对HashMap不熟悉的话可以看后面关于HashMap的详细解析。

LinkedHashSet

LinkedHashSet底层也是基于 LinkedHashMap 的k实现的，一样元素不可重复，特性同 LinkedHashMap。LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。
LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。

我们看一下他的源码，发现其方法都是用了父类HashSet的方法，然后其父类也是基本使用HashMap实现的，所以LinkedHashMap还是和HashMap有着千丝万缕的关系，当然和LinkedHashMap有着更近的关系，我们看他的构造函数，发现其使用的构造函数还是LinkedHashMap。

1
2
3

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

再看看他的类图是不是和HashMap很像呢？

类的方法也基本上只有构造函数，连重写都没有，真的美滋滋。

TreeSet

TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。向TreeSet中加入的应该是同一个类的对象。

TreeSet也是对NavigableSet的继承，在NavigableSet顾名思义是一导航的接口，它定义了方法 lower、floor、ceiling 和 higher 分别返回小于、小于等于、大于等于、大于给定元素的元素，如果不存在这样的元素，则返回 null，通过这个导航类来实现排序的功能。

其底层是根据红黑树来进行实现的，具体关于红黑树的讲解参考：**https://zhuanlan.zhihu.com/p/79980618**

Queue(队列)

Queue是一个队列集合，队列通常是指“先进先出”（FIFO）的容器。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。

ArrayDeque

ArrayQueue是一个基于数组实现的双端队列，可以想象，在队列中存在两个指针，一个指向头部，一个指向尾部，因此它具有“FIFO队列”及“栈”的方法特性。

其具体的实现是一个数组，其扩容方法是将容量扩大为原来的两倍，即新容量=旧容量<<1;

PriorityQueue

PriorityQueue也是一个队列的实现类，此实现类中存储的元素排列并不是按照元素添加的顺序进行排列，而是内部会按元素的大小顺序进行排列，是一种能够自动排序的队列。

LinkedList

LinkedList是List接口的实现类，也是Deque的实现类，底层是一种双向链表的数据结构，LinkedList可以根据索引来获取元素，增加或删除元素的效率较高，如果查找的话需要遍历整合集合，效率较低，LinkedList同时实现了stack、Queue、PriorityQueue的所有功能。

我们看看他的构造函数：

内部实现是使用数组，构造函数将上面集中接口初始化的方式都涵盖了。

重要的几个方法

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        //第一个则不排序
        queue[0] = e;
    else
        //排序
        siftUp(i, e);
    return true;
}
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    //看到奇怪的的扩容方法，如果容量小于64的话，那么每次新容量=旧容量*2+2否则新容量=旧容量*1.5
    //且其初始容量是奇怪的11 private static final int DEFAULT_INITIAL_CAPACITY = 11;
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // 防止整数溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //扩容，增加需要的元素的内存大小。
    queue = Arrays.copyOf(queue, newCapacity);
}
private void siftUp(int k, E x) {
    if (comparator != null)
        //如果指定了比较器用比较器进行排序
        siftUpUsingComparator(k, x);
    else
        //否则使用Comparable接口的方法排序
        siftUpComparable(k, x);
}
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    //二分查找后插入
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

Map（映射）

Map是一个双列集合，其中保存的是键值对，键要求保持唯一性，值可以重复。

HashMap

HashMap是使用数组和单链表（在JDK1.8红黑树）组成的数据结构，因为使用的是哈希表存储元素，所以输入的数据与输出的数据，顺序基本不一致，另外，HashMap最多只允许一条记录的 key 为 null。

HashMap应该是我们日常开发中使用的最多的一个工具类，本人的话就经常用它来传递JSON数据给前端。

说到HashMap的历史，在JDK1.7中，HashMap是使用Entry进行对节点的存储，而JDK1.8，中使用Node和TreeNode静态内部类进行数据的存储。JDK1.7是用单链表进行的纵向延伸，当采用头插法时会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。

初始化方法：

//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//无参构造
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//初始化构造
public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
}
//默认容量及加载因子
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
}

重要的方法

Hash算法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Put方法

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

看到put方法调用了putval方法，去看看

Putval

/**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; 
    Node<K,V> p;
    int n, i;
    //初始化tab，这里我们看看resize方法。
    if ((tab = table) == null || (n = tab.length) == 0)
        //n是新的Node数组的长度
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        //哈希值和(n-1)做&，即011111这种形式，避免数组越界，且得到的下标为null，直接插入
        tab[i] = newNode(hash, key, value, null);
    //否则就是出现了哈希值的碰撞，这个时候就要考虑是进行链表插入还是红黑树的插入
    else {
        Node<K,V> e; K k;
        //如果插入的元素的hash与传入的hash一样（即发生hash碰撞）且两个对象的key一样，把p赋值给e
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //否则两个对象的key并不相同且发生hash碰撞，且p是红黑树类型的Node
        else if (p instanceof TreeNode)
            //那么就把这个元素加入到红黑树中，然后复制给e，这个e是红黑树类型的Node
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //否则两个对象的key并不相同且发生hash碰撞，且p不是红黑树类型的Node（TreeNode）-现在已经发生hash碰撞，且没有达到转换成红黑树的临界条件
        else {
            for (int binCount = 0; ; ++binCount) {
                //找到链表最后的节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //可以看到 TREEIFY_THRESHOLD 的值为8，即当链表长度大于等于8的时候使用treeifyBin方法，将链表变成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //如果大于8个节点，那么就转成红黑树，-》转换成红黑树的方法
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

//得到新的Node数组方法
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        //旧容量已经达到Integer.MAX_VALUE，就不扩容了，自生自灭好吧。
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //旧容量*2之后如果小于Integer.MAX_VALUE且旧容量>默认容量16
        //那么容量=容量*2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {
        // zero initial threshold signifies using defaults
        // 如果还没初始化呢，那么就算一下
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    //重新计算hash值和容量-1的&
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //MIN_TREEIFY_CAPACITY=64;
    //如果当前哈希表为空，或者哈希表中元素的个数小于进行树形化的阈值(默认为 64)，就去新建/扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

扩容流程对比图

几个注意的问题：

HashMap在什么情况下灰扩容呢?

当map中包含的Entry的数量大于等于threshold = loadFactor * capacity的时候，且新建的Entry刚好落在一个非空的桶上，此刻触发扩容机制，将其容量扩大为2倍。

最小树形化容量阈值：即当哈希表中的容量 > 该值时，才允许树形化链表（即将链表转换成红黑树）

LinkedHashMap

HashMap 的子类，内部使用链表数据结构来记录插入的顺序，使得输入的记录顺序和输出的记录顺序是相同的。LinkedHashMap与HashMap最大的不同处在于，LinkedHashMap输入的记录和输出的记录顺序是相同的！

LinkedHashMap实现和HashMap最大的区别在于：

记录节点Entry的结构不同

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);
    }
}

LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了Entry。LinkedHashMap中的Entry增加了两个指针 before 和 after，它们分别用于维护双向链接列表。特别需要注意的是，next用于维护HashMap各个桶中Entry的连接顺序，before、after用于维护Entry插入的先后顺序的。

LinkedHashMap的put方法还是使用的HashMap的put方法，并没有进行重写。但是重写了构建新节点的newNode()方法，这个方法会在putVal()方法中被调用。

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    //如果此时加入的元素是第一个元素
    if (last == null)
        head = p;
    //否则进行链表的链接
    else {
        p.before = last;
        last.after = p;
    }
}

LinkedHashMap比较重要的一点就是其重写了三个回调函数：afterNodeRemoval afterNodeInsertion afterNodeAccess 这三个回调函数在特定的操作发生后被调用，通过这三个回调函数维持其有序性。

void afterNodeRemoval(Node<K,V> e) { // unlink
    //元素e被除移之后
    //b为前序节点（or null），a为后序节点（or null）
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //将其与前后节点的链接删除
    p.before = p.after = null;
    //如果前驱节点是null证明删除的是第一个节点，那么他的后继节点就是头节点了
    if (b == null)
        head = a;
    //否则前驱节点的下一个就是后继节点
    else
        b.after = a;
    //同理
    if (a == null)
        tail = b;
    else
        a.before = b;
}

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    //evict一直为True，且不为空链表且removeEldestEntry(first))为TRUE的话，就删除first节点，因此可以用作LRU算法
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

void afterNodeAccess(Node<K,V> e) { 
    LinkedHashMap.Entry<K,V> last;
    //accessOrder是我们构造的时候确定的，下面就是将节点移动到链表的最后面。
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

因为这三个回调方法中的afterNodeAccess和afterNodeInsertion方法与LRU缓存算法的形成密切相关，就能用作LRU算法，如下，是不是很easy?

class LRUCache extends LinkedHashMap<Integer,Integer>{
    private int size=0;

    public LRUCache(int capacity) {
        super(capacity,0.75f,true);
        this.size=capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest){
        return size()>this.size;
    }

    public int get(int key) {
        return super.getOrDefault(key,-1);
    }
    //这个也可以不写
    public void put(int key, int value) {
        super.put(key,value);
    }
}

HashTable

Hashtable，一个元老级的类，键值不能为空，与HashMap不同的是，方法都加了synchronized同步锁，是线程安全的，但是效率上，没有HashMap快！

同时，HashMap 是 HashTable 的轻量级实现，他们都完成了Map 接口，区别在于 HashMap 允许K和V为空，而HashTable不允许K和V为空，由于非线程安全，效率上可能高于 Hashtable。

如果需要在多线程环境下使用HashMap，可以使用如下的同步器来实现或者使用并发工具包中的ConcurrentHashMap类，但是建议使用ConcurrentHashMap

1	`Map<String, Object> map =Collections.synchronizedMap(new HashMap<>());`

TreeMap

能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历时，得到的记录是排过序的；如需使用排序的映射，建议使用 TreeMap。TreeMap实际使用的比较少！

常用工具类

Collection类

addAll：向指定的集合c中加入特定的一些元素elements

1	`public static <T> boolean addAll(Collection<? super T> c, T… elements)`

binarySearch：利用二分法在指定的集合中查找元素

//集合元素T实现Comparable接口的方式，进行查询
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)

//元素以外部实现Comparator接口的方式，进行查询
public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

sort：排序

//集合元素T实现Comparable接口的方式，进行排序
public static <T extends Comparable<? super T>> void sort(List<T> list)

//元素以外部实现Comparator接口的方式，进行排序
public static <T> void sort(List<T> list, Comparator<? super T> c)

reverse：集合排列反转

//直接反转集合的元素
public static void reverse(List<?> list)

//返回可以使集合反转的比较器Comparator
public static <T> Comparator<T> reverseOrder()

//集合的反转的反转，如果cmp不为null，返回cmp的反转的比较器，如果cmp为null，效果等同于第二个方法.
public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)

Arrays类

asList：将一个数组转变成一个ArrayList

1
2
3

public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
}

sort：对数组进行排序，适合byte,char,double,float,int,long,short等基本类型，还有Object类型

//基本数据类型，例子int类型数组
public static void sort(int[] a)

//Object类型数组
//如果使用Comparable进行排序，Object需要实现Comparable
//如果使用Comparator进行排序，可以使用外部比较方法实现
public static <T> void sort(T[] a, Comparator<? super T> c)
public static void sort(Object[] a)

copyOf：数组拷贝，底层采用System.arrayCopy（native方法）实现。

//基本数据类型，例子int类型数组，newLength新数组长度
public static int[] copyOf(int[] original, int newLength)

//T为泛型数组，newLength新数组长度
public static <T> T[] copyOf(T[] original, int newLength)

copyOfRange：数组拷贝，指定一定的范围，底层采用System.arrayCopy（native方法）实现。

//基本数据类型，例子int类型数组，from：开始位置，to：结束位置
public static int[] copyOfRange(int[] original, int from, int to)

//T为泛型数组，from：开始位置，to：结束位置
public static <T> T[] copyOfRange(T[] original, int from, int to)

equals和deepEquals：判断两个数组的每一个对应的元素是否相等

//基本数据类型，例子int类型数组，a为原数组，a2为目标数组
public static boolean equals(int[] a, int[] a2)

//Object数组，a为原数组，a2为目标数组
public static boolean equals(Object[] a, Object[] a2)
    
//主要针对一个数组中的元素还是数组的情况(多维数组比较)
public static boolean deepEquals(Object[] a1, Object[] a2)

toString和deepToString：将数组转换成字符串，中间用逗号隔开

//基本数据类型，例子int类型数组，a为数组
public static String toString(int[] a)

//Object数组，a为数组
public static String toString(Object[] a)

国庆和中秋终于在2020碰到一起了，国庆快乐！中秋快乐！努力吧少年！

JAVA

#JAVA基础

JAVA集合框架结构

https://dlddw.xyz/2020/07/01/集合框架复习/

作者

Deepblue

发布于

2020年7月1日

许可协议

JMM 上一篇

JAVA集合框架结构

JAVA集合框架结构

Collection

List（列表）

ArrayList

LinkedList

Vector

Stack

Set(集合)

HashSet

LinkedHashSet

TreeSet

Queue(队列)

ArrayDeque

PriorityQueue

LinkedList

重要的几个方法

Map（映射）

Map（映射）

HashMap

重要的方法

Hash算法

Put方法

Putval

几个注意的问题：

LinkedHashMap

HashTable

TreeMap

常用工具类

Collection类

binarySearch：利用二分法在指定的集合中查找元素

sort：排序

reverse：集合排列反转

Arrays类

asList：将一个数组转变成一个ArrayList

copyOf：数组拷贝，底层采用System.arrayCopy（native方法）实现。

equals和deepEquals：判断两个数组的每一个对应的元素是否相等

toString和deepToString：将数组转换成字符串，中间用逗号隔开

国庆和中秋终于在2020碰到一起了，国庆快乐！中秋快乐！努力吧少年！