Java 集合

java集合

fail-fast机制

在java集合类中,使用modCount来检查数组的状态.
当在迭代集合的时候,(通常会实现 iterator()方法来获取迭代对象,或者 foreach),
集合里面的数据,在其他地方被修改了,这个时候 modCount就会被修改,与迭代过程的modCount不一致.将抛出ConcurrentModificationException异常,这个过程就叫 fail-fast

List 篇

主要介绍 ArrayList,Vector和LinkedList,CopyOnWriteArrayList

ArrayList

是一个数组长度可自增长的线程不安全的列表.内部使用数组实现. Object[] elementData.

1. 默认的长度为 10.
2. fail-fast
3. 自动扩容(每次扩容为原来的1.5倍)
4. 线程不安全
5. 使用连续控件存储
6. 继承自 List,RandomAccess等.
7. 允许添加 null值

时间复杂度 :

根据索引查询,复杂度为 O(1).
根据元素查询,复杂度为 O(N).
插入和删除,如果在列首复杂度为 O(N);在列尾复杂度为 O(1);平均复杂为 O(N)

插入和删除非列尾数据, 将会导致数组移动数据.

RandomAccess 接口

RandomAccess 是一个标记接口(没有任何方法).
如果实现了 RandomAccess 接口,表示该集合可以进行随机快速访问(通常底层是 数组形式的集合),如 ArrayList.
可以快速访问的集合,使用

for (int i=0, n<size; i++)
    list.get(i);

未实现 RandomAccess接口的集合,如LinkedList,使用迭代器效率更高.

for (Iterator i=list.iterator(); i.hasNext(); )
    i.next();

使用 instanceof RandomAccess来判断是否 支持随机快速访问.

Vector

是一个数组长度可自增长的线程安全的列表,内部使用数组实现.

1. 默认的长度为 10.
2. fail-fast
3. 自动扩容(可设置每次扩容的增量值,默认扩容为原来的2倍.)
4. 线程安全(synchronized)
5. 使用连续控件存储
6. 继承自 RandomAccess,List
7. 允许添加 null值

线程安全的vector,照样可以触发 fail-fast.
时间复杂度与 arraylist 一样.

在不涉及线程安全的前提下,arraylist效率更高.

fun main(args: Array<String>) {
    val vector = Vector(listOf(1, 2, 3, 4, 5))

    singleThread(vector)
    multiThread(vector)
    multiThreadSynchronized(vector)
}

/**
 * 单线程下,迭代抛出 ConcurrentModificationException
 */
fun singleThread(vector: Vector<Int>) {
    val it = vector.iterator()
    while (it.hasNext()) {
        println(it.next())
        vector.add(1)
    }
}

/**
 * 多线程下,迭代抛出 ConcurrentModificationException
 */
fun multiThread(vector: Vector<Int>) {
    thread {
        repeat(10000) {
            vector.add(it)
        }
    }

    thread {
        vector.forEach { println(it) }
    }
}

/**
 * 多线程下,修改vector是添加同步锁,避免同时迭代同时修改
 */
fun multiThreadSynchronized(vector: Vector<Int>) {
    thread {
        synchronized(vector) {
            repeat(10000) {
                vector.add(it)
            }
        }
    }

    thread {
        vector.forEach { println(it) }
    }
}

Stack

继承自 vector,线程安全,栈结构,先进后出.

LinkedList

是以双向链表方式实现的非线程安全的集合.

1. 一个元素节点包含 上一个节点和下一个节点的引用,以及自身的值.
2. 内存空间可不连续
3. 线程不安全
4. fail-fast
5. 继承自 List,Deque等.
6. 允许添加 null值

时间复杂度:

删除和插入元素,复杂度为 O(1).
查询时,由于采用双向链表,判断离哪头近,从哪头开始找.
最糟糕的情况是O(N/2),所以它的复杂度为 O(N).

CopyOnWriteArrayList

CopyOnWriteArrayList是并发包中的实现.使用 ReenterLock和System.arraycopy来实现数组读写的线程安全.

在读取的时不加锁,所以可以支持多线程同时读取数据,并且同时读取数不受限制.

在写入(add,set,remove等操作)的时候,使用 ReenterLock锁住方法,然后操作数据时先将原数组拷贝一份,对拷贝数据进行操作,操作完后将拷贝的原来的数据引用指向拷贝的数组引用,实现数据的更新操作,更新完后释放锁. 和其名字操作一致(写时拷贝).

没有设置初始长度的方法和扩容的策略. 因为该数组在每次 添加数据是, 都会使用 System.arraycopy拷贝一份比当前数据 +1 的数组.

    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

ArrayList,Vector和LinkedList的区别

ArrayList和Vector内部都是使用数组实现的.它们的主要区别在于

1. ArrayList 是线程不安全的,Vector是线程安全的.
2. ArrayList 自动扩容时固定增长为原来的1.5倍,不可指定增量值. Vector可指定每次的增量值,如果没指定,则扩容为原来的2倍.

在不考虑线程安全的情况下,优先使用 ArrayList,如果在使用前,能够预估大概有元素,创建时指定个数,效果更好.

LinkedList 使用双向链表实现,也是线程不安全的.与ArrayList的区别在于

1. 实现方式不同.ArrayList使用数组,Vector使用双向链表.
2. 内存空间管理不同,LinkedList可以是不连续的空间,ArrayList需要连续的内存空间.
3. LinkedList 在删除和插入上的性能较好, ArrayList在查询上的效率更好.
4. ArrayList 一个item只存自己的值,比较省空间, LinkedList一个item除了自己的值,还需要存放上一个和下一个元素的引用,比较费空间.

如果主要需要对列表进行遍历,以及增删操作,使用LinkedList其他情况使用ArrayList.

如果需要用到线程安全的列表,请使用 CopyOnWriteArrayList

Map篇

Map 是以键值对形式存储的集合.

主要介绍 HashMap,TreeMap和 Hashtable,ConcurrentHashMap

HashMap

HashMap 内部混合使用数组,链表,红黑树的结构来构建的键值对集合.

HashMap的本质基础是基于数组的. 数组的各个元素,使用单向链表的结构.(Node(int hash, K key, V value, Node<K,V> next)).

HashMap通过哈希函数(hash())来完成key对index的映射.

当出现hash后index冲突(index位置已经存在不同的key的键值对)时,数据将在index位置,使用单向链表或红黑树(当链表长度大于等8个时,链表中的所有元素改用红黑树存放)来存放元素.

当使用掉的索引 占用了 数组长度的一定比例时(填装因子),HashMap将进行扩容(扩容为原来的两倍,key与index重新映射).

HashMap的性能瓶颈:

1. 优良的 哈希函数.

理想的状态是,每一个键值对的存放,能够比较均匀适当的分布在数组的索引上,尽量避免过多的hash值冲突.

    // java 8 中的实现
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
// index = (n - 1) & hash , 2的次方来说就是取余操作.
// 由于 (n -1)的二进制 高位都是0,地位都是1.
// hashcode 与 它进行 & 操作的话, hashcode的高位变化低位不变,则计算出来的index值讲不变.
// 为了消除高位变化 不影响 index 的值, 于是将 hashcode 的 高16位 移动到低16位,再和 hashcode进行 ^ 操作.
// 这样高位的变化,也能影响index值, 降低了冲突的概率.

1. 填装因子

过低的填装因子,如填装因子=0.5,容量剩余一半的时候就扩容,可能导致空间上的浪费.
过高的填装因子,可能导致为了命中未使用的索引,而频繁出现 冲突.
HashMap实现中,填装因子默认使用 0.75的值.

特点 :

1. 默认的长度为 16,默认填装因子为 0.75.
2. fail-fast
3. 自动扩容(默认扩容为原来的2倍.)
4. 线程不安全
5. 混合使用数组,链表和红黑树
6. 继承自Map
7. key和value都可以添加 null
8. 插入和遍历顺序不一致

时间复杂度 :

查询,插入和删除操作的平均时间复杂度为 O(1).
极端情况下(全部发生冲突),若长度小于8,使用单项链表,复杂度为 O(n),如果长度大于等于8,使用红黑树,复杂度为O(logn)

LinkedHashMap

继承自 HashMap, 底层使用哈希表与双向链表来保存元素,与HashMap的差异就在于 访问顺序上.
构造中,accessOrder 默认为 false，代表按照插入顺序进行迭代；为 true，代表以访问顺序进行迭代(最常访问的在前,最不经常访问的在后LRU)。

TreeMap

TreeMap内部使用 红黑树来实现的键值对集合.与HashMap相比，TreeMap是一个能比较元素大小的Map集合，会对传入的key进行了大小排序。其中，可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序.

特点 :

1. fail-fast
2. 线程不安全
3. 使用红黑树实现
4. key和value都可以添加 null
5. 插入和遍历顺序不一致
6. 支持对key排序
7. 继承自NavigableMap,拥有强大的搜索功能.

时间复杂度 :

红黑树是自平衡的二叉搜索树, 查询,添加删除 效率都是 O(logn).

HashTable

HashTable 内部使用数组和单项链表实现的键值对集合.

HashTable的哈希函数 (hash & 0x7FFFFFFF) % tab.length,只是对key的hashcod进行取整和取余操作.

HashTable默认的初始大小为11，之后每次扩充为原来的2n+1。
也就是说，HashTable的链表数组的默认大小是一个素数、奇数。之后的每次扩充结果也都是奇数。
由于HashTable会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。（这个是可以证明出来 的，可参考：http://zhaox.github.io/algorithm/2015/06/29/hash）

特点 :

1. 默认的长度为 11,默认填装因子为 0.75.
2. fail-fast
3. 自动扩容(扩容为原来的2n+1)
4. 线程安全
5. 混合使用数组,链表
6. 继承自Map
7. key和value都不能使用null值,否则抛出空指针异常.
8. 插入和遍历顺序不一致

时间复杂度 :

和HashMap一致

ConcurrentHashMap (java.util.concurrent)

和HashMap一样,是内部使用数组,链表,红黑树的结构来构建的键值对集合,因为需要保证线程安全,所以内部实现更加复杂.

哈希函数 (h ^ (h >>> 16)) & HASH_BITS , 和HashMap类似,与高位进行异或操作的方式,来消除高位数据变化导致索引不变的情况,多加了一步正数的操作.

当冲突的链表中个数超过8个, 如果数组长度小于64,则扩容,否则,将链表数据转化为 红黑树结构存储.

ConcurrentHashMap 采用 CAS(Compare and Swap)原子类型操作,来保证线程的安全性. 较 jdk1.7 的分段锁机制性能更好.

特点 :

1. 默认长度为16,无默认的装填因子

构造函数为 : ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)
没有默认的装填因子,传入 初始容量和装填因子后,会被算法调整为 2次方,最小容量为 16.
并发级别,表示 可以同时对数据进行写操作的线程数, 最大可达16. 读取不受限制.

1. 没有 fail-fast, 将保证线程安全.
2. 自动扩容为原来的 2 倍.
3. 线程安全
4. 混合使用数组,链表和红黑树
5. 继承自ConcurrentMap
6. key和value都不可以添加 null
7. 插入和遍历顺序不一致

时间复杂度 :

和HashMap一致

HashMap和HashTable , ConcurrentHashMap对比

HashMap 线程不安全 , HashTable线程安全,但还是存在fail-fast问题 , ConcurrentHashMap线程安全,不存在fail-fast问题.

HashMap 和 ConcurrentHashMap 内部都是用 数组,链表 加红黑树来构建.(较高效) HashTable 使用数组加链表.

HashMap 和 ConcurrentHashMap 都是用 高位异或的哈希算法. HashTable 采用 数组长度为素数,直接取余的哈希算法.

HashMap 允许插入 null键值对, HashTable , ConcurrentHashMap 不允许.

结论 : 不考虑线程安全的情况下使用 HashMap, 线程安全则使用 ConcurrentHashMap.
如果知道 大概会存多少数据,指定 初始容量 会更高效, 避免扩容和重新hash映射产生的效率问题.

Set篇

Set 是没有重复元素的单元素集合.

TreeSet 内部使用 TreeMap实现.

HashSet 内部使用 HashMap实现. 当构造参数为三个时 LinkedHashMap实现.

LinkedHashSet 继承自 HashSet,但是都是调用 HashSet中有三个构造参数的LinkedHashMap来实现.