Java容器

目标

本文解决以下问题

• 什么是容器类？

• 为什么需要容器？
• 如何让你去实现集合类，你将如何实现？将提供哪些功能的集合？
• 集合类的概览
• 如何使用？
• 如何正确使用？使用时的考虑标准是什么？
• 是如何实现的？

看完本篇后希望读者对Java 容器有一个整体的认识，并知道如何在你的程序中存储对象的引用。

什么是Java集合容器？

用于存储数量不定的对象引用的工具类，你可以将任意数量的对象放置到容器中，并且不需要担心容器应该设置为多大。

为什么需要容器

在日常编程过程中，经常需要存储数量不确定的对象（对象引用）所以需要容器工具类来存储这些对象。

通常，程序总是根据运行时才知道的某些条件去创建新对象。在此之前，不会知道所需对象的数量（数组创建时必须制定大小），甚至不知道确切的类型（泛型的意义）。为解决这个普遍的编程问题，需要在任意时刻和任意位置创建任意数量的对象。所以，就不能依靠创建命名的引用来持有每一个对象：

 MyType aReference;

因为你不知道实际上会需要多少这样的引用。

大多数语言都提供某种方法来解决这个基本问题。Java有多重方式保存对象（应该说是对象的引用）。例如前面曾经学习过的数组，它是编译器支持的类型。数组是保存一组对象的最有效的方式，如果你想保存一组基本类型数据，也推荐使用这种方式。但是数组具有固定的尺寸，而在一般的情况中，你在写程序时并不知道将需要多少个对象，或者是需要更富在的方式来存储对象，因此数组尺寸固定这一限制显得过于受限了。 ©Java编程思想(第四版)

如何让你去实现集合类，你将如何实现？将提供哪些功能的集合？

知道了容器的定以后，那么存储对象的容器应该提供哪些功能呢？或者说如何实现会更方便我们日常的开发？

集合容器将要提供哪些功能？

• 集合的顺序 有序或无序
• 是否可重复？
• 常用的数据结构是否要实现？如队列、栈
• 以何种方式查看内容
• 字典类型数据结构的支持

容器概览

Java容器分为Collection与Map

Collection

###　List

有顺序的集合

ArrayList

以数组实现。节约空间，但数组有容量限制。超出限制会扩容，使用System.arraycopy()复制到新的数组。初始容量为10，超出容量后会扩容。扩容机制原先的长度扩容50%

private int newCapatity(int minCapacity){
    int oldCapacity = elementData.length;
    // 扩容50%
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果新的容量小于或等于要求扩容的最小容量
    //则使用最小容量
    if(newCapacity - minCapacity <= 0){
        if(elementData == DEFAULTCAPACITY_EMPTY_ELEMNTDATA){//如果数组未初始化，则将数组初始化为，扩容最小值与默认初始值的最大的那个。
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        if(minCapacity < 0){
            throw new OutOfMemoryError();
        }
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

按数组下标访问get(i);set(i,e)性能很高。

但是如果插入元素、删除元素 add(i,e);remove(i);remove(e),则要使用System.arraycopy()`来赋值移动受影响的部分，性能就变差了。

LinkList

以双向链表实现。链表无容量限制，但双向链表本身使用了更多的空间，每插入一个元素都要构造额外的Node对象和额外的链表指针。

按下表访问元素get(i)、set(i,e)要遍历链表到指针移动到具体的位置（如果i>数组大小的一半，会从末尾开始遍历）。

插入、删除元素时修改前后指针即可，不需要复制或移动。但需要部分遍历链表的指针才能移动到指定下标的位置。

CopyOnWriterArrayList

并发优化的ArrayList（同样使用数组实现）。基于不可变对象策略，在修改时先复制出一个数组快照来修改，改好了，在让内部指针指向新数组。

public boolean add(E e){
    synchronized(lock){
        Object[] es = getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);
        es[len] = e;
        setArrray(es);
        return true;
    }
}

适合读多写少的场景。

Collections.synchronizedList(list);

通过这个方法返回线程安全的List，该方法通过代理对象对代理对象的方法加锁来实现线程安全。

遗憾

无论哪种实现，涉及到按值查找都需要遍历所有元素，性能不会太好。

没有按元素值排序的SortedList(排序可以使用Collections.sort)。

除了CopyOnWriteArrayList，再没有其他线程安全又并发优化的数组实现，如ConcurrentLinkeList。凑合着使用Set与Queue中的等价类时，会缺少一些List特有的方法如get(i).如果更新频率较高，或者数组较大时，需要使用Collection.synchronizedList(list),对所有操作使用一把锁来保证线程安全。

Set

结构

Map

将键映射到值对象上，映射不能包含重复的键，每个键只能映射到一个值。

HashMap

JDK 1.7 采用数组加链表的方式实现。

JDK 1.8 采用数组加红黑树（如果筒中元素大于8）的方式实现。

put方法的实现

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
    	// 判断 数组是否初始化，如未初始化则初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
    	// 如果该key的hash筒为空，则创建一个Node放入到里边。
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {// 如果不为空
            Node<K,V> e; K k;
            // p为哈希筒中的第一个第一个节点
            // 当第一个node的key与要放入的key相等时
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果为树节点
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {// 如果链表节点
                for (int binCount = 0; ; ++binCount) {// 遍历节点
                    if ((e = p.next) == null) {// 如果节点遍历完毕后为发现
                        p.next = newNode(hash, key, value, null);// 创建新节点
                        // 判断是否需要转为红黑树  默认 TREEIFY_THRESHOLD = 8
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);// 调整链表结构为树结构
                        break;
                    }
                    // 判断是否为已存在的key
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 存在已有的key
            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;
    }

hash处理:将key的hash无符号右移16位后与原hash取异或。

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

扩容机制

当数组容量达到75%时，哈希冲突已经比较严重，数组容量会扩容为原来的2倍，并重新分配原来所有的Node(由于数组容量都是成倍数扩容，所以扩容时，Node节点重新分配时只会落在原来的地方或者原来下标乘以2的地方)。扩容成本不低，所以最好有个预估值。

iterator()

iterator()遍历时顺着哈希桶数组来遍历，看起来是个乱序。

LinkedHashMap

有序的HashMap

实现原理

重写了HashMap中的 newNode方法, 并在HashMap.Node中添加 before, after两个引用。来存储元素顺序。

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

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

TreeMap

使用红黑树实现。该映射根据其键的自然顺序排序，或者根据创建映射时提供的Comparator进行排序，具体取决于使用的构造方法。

EnumMap

• EnumMap是一个与枚举类一起使用的Map实现，所有Key都必须是单个枚举类的枚举值。创建EnumMap时必须显示或隐式指定它对应的枚举类。

• EnumMap内部以数组形式保存，初始化时会创建于枚举值数量相等的数组。

• EnumMap中的顺手是枚举中值得的顺序。

ConcurrentHashMap

ConcurrentSkipListMap

---

参考

Java编程思想(第四版)

关于Java集合的小抄