集合框架复习

Posted by DeepBlue on 12-05,2020

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等实现类。下面就一个一个来进行解析。

img

Collection

List(列表)

List接口下有ArrayListLinkedList(LinkedList是实现了List接口和Deque接口的类)、VectorStack

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,现在用的很少了,因为里面的getsetadd等方法都加了synchronized,所以,执行效率会比较低,如果需要在多线程中使用,可以采用下面语句创建 ArrayList 对象

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

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

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。

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

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

image-20201001115529209

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

image-20201001114833512

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的所有功能。

我们看看他的构造函数:

image-20201001171730235

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

重要的几个方法

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(映射)

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方法
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增加了两个指针 beforeafter,它们分别用于维护双向链接列表。特别需要注意的是,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;
    }
}

因为这三个回调方法中的afterNodeAccessafterNodeInsertion方法与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

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

TreeMap

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

常用工具类

Collection类

  • addAll:向指定的集合c中加入特定的一些元素elements
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
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碰到一起了,国庆快乐!中秋快乐!努力吧少年!