Java 容器---实现

“工欲善其事,必先利其器”。Java 容器就是我们开发中的利器。

然而,之前在开发中使用仅仅是容器的一小部分。这次从源码的角度进行深入的理解,一点总结分享给大家。

这里只列举了非阻塞式的容器;阻塞式的容器,会在后面的并发篇补。

如果有什么理解不对的地方,欢迎大家在评论中指正~

ArrayList


实现: 数组实现

线程安全: 非线性安全,fail-fast 机制保护

容量: 初始容量为10;随后每次增加都会变成之前的1.5倍(批量添加除外)。源码如下:

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 这里是扩容的关键
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 批量添加,也有可能会直接等于相加之后的容量
    if(newCapacity - minCapacity < 0) newCapacity = minCapacity;
    if(newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

效率:

操作

平均

最好

最差

size()

O(1)

O(1)

O(1)

isEmpty()

O(1)

O(1)

O(1)

contains(Object o)

O(n)

O(1)

O(n)

indexOf(Object o)

O(n)

O(1)

O(n)

lastIndexOf(Object o)

O(n)

O(1)

O(n)

toArray()

O(n)

O(n)

O(n)

get(int index)

O(1)

O(1)

O(1)

set(int index, E e)

O(1)

O(1)

O(1)

add(E e)

O(1)

O(1)

O(1)

add(int index, E e)

O(n)

O(1)

O(n)

remove(int index)

O(n)

O(1)

O(n)

remove(Object o)

O(n)

O(1)

O(n)

clear()

O(n)

O(n)

O(n)

addAll(Collection c)

O(m)

O(m)

O(m)

removeAll(Collection c)

O(m*n)

O(m)

O(m*n)

retainAll(Collection c)

O(m*n)

O(m)

O(m*n)

除了模型中的操作外还有一些特殊的操作:

// 缩小容器的容量到元素的数量
public void trimToSize();
// 确保容量能覆盖 minCapacity 个元素
public synchronized void ensureCapacity(int minCapacity) ;

Vector


实现: 数组

线程安全: 是;fast-fail 保护

容量: 初始容量为10;根据指定的扩容数量或者*2(批量添加除外);核心代码:

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // capacityIncrement 是构造函数中指定的值, 默认为0
    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);
}

效率:

效率与ArrayList相似,但是每一个操作都需要获取锁,时间开销要比ArrayList大。

操作

平均

最好

最差

add(E e)

O(1)

O(1)

O(1)

add(int index, E e)

O(n)

O(1)

O(n)

get(int index)

O(1)

O(1)

O(1)

remove(int index)

O(n)

O(1)

O(n)

remove(Object o)

O(n)

O(1)

O(n)

removeAll(Collection c)

O(n)

O(n)

O(n)

retainAll(Collection)

O(n)

O(n)

O(n)

indexOf(Object)

O(n)

O(1)

O(n)

Stack


实现: Vector

线程安全: 是;fast-fail保护

容量: 同Vector

效率:

操作

平均

最好

最差

push(E e)

O(1)

O(1)

O(1)

pop()

O(1)

O(1)

O(1)

peek()

O(1)

O(1)

O(1)

empty()

O(1)

O(1)

O(1)

LinkedList


实现: 双指针链表

线程安全:否;fast-fail保护

容量: 有size();无容量

效率:

作为 List 来说:

操作

平均

最好

最差

size()

O(1)

O(1)

O(1)

isEmpty()

O(1)

O(1)

O(1)

contains

O(n)

O(1)

O(n)

add(E e)

O(1)

O(1)

O(1)

remove(Object o)

O(n)

O(1)

O(n)

containsAll(Collection c)

O(m*n)

O(m)

O(m*n)

toArray()

O(n)

O(n)

O(n)

removeAll(Collection c)

O(m*n)

O(m)

O(m*n)

retainAll(Collection c)

O(m*n)

O(m)

O(m*n)

removeAll(Collection c)

O(m*n)

O(m)

O(m*n)

retainAll(Collection c)

O(m*n)

O(m)

O(m*n)

clear()

O(1)

O(1)

O(1)

get(int index)

O(n)

O(1)

O(n)

set(int index,E e)

O(n)

O(1)

O(n)

add(int index, E e)

O(n)

O(1)

O(n)

remove(int index)

O(n)

O(1)

O(n)

indexOf(Object o)

O(n)

O(1)

O(n)

lastIndexOf(Object o)

O(n)

O(1)

O(n)

作为 Queue 来说:

操作

平均

最好

最差

add(E e)

O(1)

O(1)

O(1)

offer(E e)

O(1)

O(1)

O(1)

remove()

O(1)

O(1)

O(1)

poll()

O(1)

O(1)

O(1)

element()

O(1)

O(1)

O(1)

peek()

O(1)

O(1)

O(1)

作为 Deque 来说:

操作

平均

最好

最差

xxxFisrt

O(1)

O(1)

O(1)

xxxLast

O(1)

O(1)

O(1)

removeFirstOccurrence(Object o)

O(n)

O(1)

O(n)

removeLastOccurrence(Object o)

O(n)

O(1)

O(n)

pop

O(1)

O(1)

O(1)

push

O(1)

O(1)

O(1)

PriorityQueue


特征: 容器中元素的 出顺序 不是元素的 插入顺序,而是一个大小顺序中的最值。

实现方式: 小顶堆

线程安全: 否;fail-fast保护

容量: 默认初始容量11;容量小的时候*2,容量大的时候+50%。核心代码如下:

private void grow(int minCapacity) {
int oldCapacity = queue.length;
// 小于64的时候增倍;大于64的时候增加50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));
if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
// queue是存放元素的数组
queue = Arrays.copyOf(queue, newCapacity);

效率:

如果只是用到确定数量个元素的情况下,它是比列表排序的效率要高的。随机数列的排序平均都要O(n*log(n))了,而它最高的复杂度仅为O(log(n))

但是,如果所有元素都要遍历一次取出来,那效率与就跟堆排序是一样的O(n*log(n))

操作

平均

最好

最差

add(E e)

O(log(n))

O(1)

O(log(n))

offer(E e)

O(log(n))

O(1)

O(log(n))

remove()

O(log(n))

O(log(n))

O(log(n))

poll()

O(log(n))

O(log(n))

O(log(n))

peek()

O(1)

O(1)

O(1)

element()

O(1)

O(1)

O(1)

toArray()

O(n)

O(n)

O(n)

clear()

O(n)

O(n)

O(n)

HashSet


特征: 高效率的集合容器

实现: HashMap

线程安全: 否;failfast保护

容量: 同HashMap

效率:同HashMap

LinkedHashSet


特征: 高效率的集合容器,能保存插入顺序

实现:LinkedHashMap

线程安全:否; failfast保护

容量: 同LinkedHashMap

效率: 同LinkedHashMap

TreeSet


特征: 带全排序的集合容器

实现:TreeMap

线程安全:否;failfast保护

容量:无

效率:同TreeMap

HashMap


特征:高效率的映射表

实现: 开散列

线程安全:否;fail-fast保护

是否支持null: 是

容量: 默认初始容量16;容量总是2的幂;默认加载因子0.75;扩容后的容量由当前容量和加载因子决定,这里的扩容代码不是很直接,需要联系几个方法来看:

// 添加一组映射的时候
void addEntry(int hash, K key, V value, int bucketIndex) {
    // 容量超过threshold并且对应的hash值存在在冲突的时候,开始扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 扩展为之前的2倍
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

// 这个方法的作用在于将数组扩展到相应的容量,
// 并把原数组中的元素全部重新计算位置,转移到新数组中
// 重新计算下一个threshold
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

// 这个方法在容器第一次添加元素的时候调用,使用toSize做参数的目的是避免第一次添加元素的时候多次扩容
private void inflateTable(int toSize) {
    int capacity = roundUpToPowerOf2(toSize);
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

效率:

操作

平均

最好

最差

size()

O(1)

O(1)

O(1)

isEmpty()

O(1)

O(1)

O(1)

get

O(1)

O(1)

O(n)

getEntry(Object key)

O(1)

O(1)

O(n)

put(K key, V value)

O(1)

O(1)

O(n)

remove

O(1)

O(1)

O(n)

clear

O(n)

O(n)

O(n)

containsValue

O(n)

O(1)

O(n)

putAll(Collection c)

O(m)

O(m)

O(m*n)

LinkedHashMap


特征: 在HashMap的基础上添加了,特定规则的顺序保存

实现:开散列 + 双指针链表环

线程安全: 否;fast-fail保护

是否支持null: 是

容量: 同HashMap

特征:它在HashMap的基础上,对Entry的封装中加了两个指针记录顺序。也就是说,这里既有散列保证随机访问效率,又有链表记录顺序。

这里的顺序不是指大小顺序。而是插入顺序,或者访问次数的顺序。所以它可以用来做LRU缓存容器,不过在此之前需要对他做一些封装,需要定义缓存的体积和重写一些方法:

//这里的accessOrder要设置为true
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
}
// 缓存容量
private static final int MAX_ENTRIES = 100;
// 设置为超容量即删除
protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > MAX_ENTRIES;
}

TreeMap


特征: 全排序的映射表

实现:红黑树

线程安全: 否,fastfail保护

是否支持null:是

容量:无

特征:访问的时候根据二叉查找树来查找,插入,删除的时候需要根据红黑树的规则来平衡树。

效率:

操作

平均

最好

最差

size()

O(1)

O(1)

O(1)

isEmpty()

O(1)

O(1)

O(1)

containsKey(Object key)

O(log(n))

O(1)

O(log(n))

containsValue(Object value)

O(n)

O(1)

O(n)

get(Object key)

O(log(n))

O(log(n))

O(log(n))

put(K key, V value)

O(log(n))

O(log(n))

O(log(n))

remove(Object key)

O(log(n))

O(log(n))

O(log(n))

clear()

O(1)

O(1)

O(1)

firstKey()

O(log(n))

O(log(n))

O(log(n))

lastKey()

O(log(n))

O(log(n))

O(log(n))

putAll(Map map)

O(log(n))

O(log(n))

O(log(n))

firstEntry()

O(log(n))

O(log(n))

O(log(n))

lastEntry()

O(log(n))

O(log(n))

O(log(n))

pollFirstEntry()

O(log(n))

O(log(n))

O(log(n))

pollLastEntry()

O(log(n))

O(log(n))

O(log(n))

lowerXXX(K key)

O(log(n))

O(log(n))

O(log(n))

floorXXX(K key)

O(log(n))

O(log(n))

O(log(n))

ceilingXXX(K key)

O(log(n))

O(log(n))

O(log(n))

higherXXX(K key)

O(log(n))

O(log(n))

O(log(n))

Hashtable


特征:线程安全的高效映射表

实现: 开散列

线程安全: 是;fail-fast保护

是否支持null:

容量:默认初始容量11;加载因子0.75;由加载因子决定扩容时机,默认size超过容量的0.75需要扩容。核心代码如下:

public synchronized V put(K key, V value) {
    // ...
    // 容器中元素数量超过threshold时,扩容并重新计算hash,然后再添加元素
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();
        tab = table;
        hash = hash(key);
        index = (hash & 0x7FFFFFFF) % tab.length;
    }
    // ...
}

protected void rehash() {
    int oldCapacity = table.length;
    Entry<K,V>[] oldMap = table;
    // 新容量是旧容量的2倍
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<K,V>[] newMap = new Entry[newCapacity];
    modCount++;
    // 这里计算新的阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    boolean rehash = initHashSeedAsNeeded(newCapacity);
    table = newMap;
    // 然后重新计算hash对应的位置
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;
            if (rehash) {
                e.hash = hash(e.key);
            }
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = newMap[index];
            newMap[index] = e;
        }
    }
}

效率:

操作

平均

最好

最差

size()

O(1)

O(1)

O(1)

isEmpty()

O(1)

O(1)

O(1)

get

O(1)

O(1)

O(n)

getEntry(Object key)

O(1)

O(1)

O(n)

put(K key, V value)

O(1)

O(1)

O(n)

remove

O(1)

O(1)

O(n)

clear

O(n)

O(n)

O(n)

containsValue

O(n)

O(1)

O(n)

putAll(Collection c)

O(m)

O(m)

O(m*n)

WeakHashMap


特征: 它的Map.Entry类设计的比较特殊继承了弱引用类。key是作为弱引用持有的对象。这意味着容器中的对象在没有外部引用持有的时候随时都有可能被GC回收。所以它可以被用来做缓存。

    private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
        V value;
        int hash;
        Entry<K,V> next;

        /**
         * Creates new entry.
         */
        Entry(Object key, V value,
              ReferenceQueue<Object> queue,
              int hash, Entry<K,V> next) {
            // key是弱引用持有的对象
            super(key, queue);
            this.value = value;
            this.hash  = hash;
            this.next  = next;
        }
    }

实现: 开散列 + WeakReference + ReferenceQueue

线程安全: 否; fast-fail保护

是否支持null:是

容量:默认初始容量16;默认加载因子0.75;容量总是2的幂,每次扩容都*2;如果在扩容过程中发现大量的元素被回收,可能会终止扩容,继续使用之前的容量。核心代码如下:

public V put(K key, V value) {
    // ...
    tab[i] = new Entry<>(k, value, queue, h, e);
    if (++size >= threshold)
        resize(tab.length * 2);
}

void resize(int newCapacity) {
    Entry<K,V>[] oldTable = getTable();
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry<K,V>[] newTable = newTable(newCapacity);
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    transfer(oldTable, newTable, rehash);
    table = newTable;
    /*
     * 如果在扩容过程中删除的元素非常的多,填充数不到阈值的一半的时候
     * 使用回之前容量的数组
     */
    if (size >= threshold / 2) {
        threshold = (int)(newCapacity * loadFactor);
    } else {
        expungeStaleEntries();
        transfer(newTable, oldTable, false);
        table = oldTable;
    }
}

/** Transfers all entries from src to dest tables */
private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest, boolean rehash) {
    for (int j = 0; j < src.length; ++j) {
        Entry<K,V> e = src[j];
        src[j] = null;
        while (e != null) {
            Entry<K,V> next = e.next;
            Object key = e.get();
            // 注意,这里在转移元素的过程中会删除一些已经被垃圾回收的元素
            if (key == null) {
                e.next = null;  // Help GC
                e.value = null; //  "   "
                size--;
            } else {
                if (rehash) {
                    e.hash = hash(key);
                }
                int i = indexFor(e.hash, dest.length);
                e.next = dest[i];
                dest[i] = e;
            }
            e = next;
        }
    }
}

效率:

操作

平均

最好

最差

size()

O(n)

O(n)

O(n)

isEmpty()

O(n)

O(n)

O(n)

get

O(1)

O(1)

O(n)

getEntry(Object key)

O(1)

O(1)

O(n)

put(K key, V value)

O(1)

O(1)

O(n)

remove

O(1)

O(1)

O(n)

clear

O(n)

O(n)

O(n)

containsValue

O(n)

O(1)

O(n)

putAll(Collection c)

O(m)

O(m)

O(m*n)

IdentityHashMap


特征: 使用“引用相等”而非equals相等。只有两个 key 完全是同一个对象的时候才判定为相等。

实现: 闭散列;没有用Map.Entry类,数组偶数位置放 key,奇数位置放 value

线程安全: 否;fast-fail保护

是否支持null:是

容量:默认初始容量32;加载因子2/3;容量一定为2的幂;核心代码:

    public V put(K key, V value) {
        // ...
        // 超过阈值,扩容
        if (++size >= threshold)
            resize(len); // len == 2 * current capacity.
        // ...
    }

    private void resize(int newCapacity) {
        // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
        // 原容量*2
        int newLength = newCapacity * 2;

        Object[] oldTable = table;
        int oldLength = oldTable.length;
        // 这里重新计算阈值
        if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any further
            if (threshold == MAXIMUM_CAPACITY-1)
                throw new IllegalStateException("Capacity exhausted.");
            threshold = MAXIMUM_CAPACITY-1;  // Gigantic map!
            return;
        }
        if (oldLength >= newLength)
            return;

        Object[] newTable = new Object[newLength];
        threshold = newLength / 3;
        // 重新计算位置, 由于这是闭散列,需要对所有元素重新计算
        for (int j = 0; j < oldLength; j += 2) {
            Object key = oldTable[j];
            if (key != null) {
                Object value = oldTable[j+1];
                oldTable[j] = null;
                oldTable[j+1] = null;
                int i = hash(key, newLength);
                while (newTable[i] != null)
                    i = nextKeyIndex(i, newLength);
                newTable[i] = key;
                newTable[i + 1] = value;
            }
        }
        table = newTable;
    }

效率:

操作

平均

最好

最差

size()

O(1)

O(1)

O(1)

isEmpty()

O(1)

O(1)

O(1)

get

O(1)

O(1)

O(n)

getEntry(Object key)

O(1)

O(1)

O(n)

put(K key, V value)

O(1)

O(1)

O(n)

remove

O(1)

O(1)

O(n)

clear

O(n)

O(n)

O(n)

containsKey(Object key)

O(1)

O(1)

O(n)

containsValue(Object value)

O(n)

O(1)

O(n)

putAll(Collection c)

O(m)

O(m)

O(m*n)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习入门

LWC 62:742. Closest Leaf in a Binary Tree

LWC 62:742. Closest Leaf in a Binary Tree 传送门:742. Closest Leaf in a Binary Tree...

30610
来自专栏数据结构与算法

约瑟夫环 队列+链表

设有n个人依次围成一圈,从第1个人开始报数,数到第m个人出列,然后从出列的下一个人开始报数,数到第m个人又出列,…,如此反复到所有的人全部出列为止。设n个人的编...

3867
来自专栏JavaQ

HashMap死循环精简说

在JDK1.8之前的版本中,HashMap的底层实现是数组+链表。当调用HashMap的put方法添加元素时,如果新元素的hash值或key在原Map中不存在,...

1063
来自专栏java小白

LinkHashMap源码详解

1994
来自专栏向治洪

HashMap原理解析

1. HashMap的数据结构 数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。       数组 数组存储区间是连续的,占用内存严...

1959
来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

52410
来自专栏Java呓语

迭代器模式(控制访问集合中的元素)

现在我们需要思索,JDK是怎么做到这一切的?现在让我们先利用迭代器实现一个数组类型Array,这个类型需要支持添加、移除、遍历操作。

1052
来自专栏武培轩的专栏

Hashtable源码解析(JDK1.8)

1 package java.util; 2 3 import java.io.*; 4 import java.util.concu...

3074
来自专栏racaljk

[数据结构]C语言二叉树的实现

树和图是数据结构中比较麻烦的东西,里面涉及的概念比较多,也最有用, 就比如一般树广泛应用于人工智能的博弈上,而基于图的广度优先和深度优先搜索也广泛应用于人工智能...

3072
来自专栏Android机器圈

数据结构与算法 -- 二叉树链式详解((非)/递归遍历,叶子个数,深度计算)

PS:树型结构是一种重要的非线性数据结构,教科书上一般都是树与二叉树,由此可见,树和二叉树是有区别和联系的,网上有人说二叉树是树的一种特殊形式,但经过查资料,树...

1015

扫码关注云+社区

领取腾讯云代金券