Java 集合类源码笔记(JDK1.7)

ArrayList

数组作为内部的存储结构。非线程安全

ArrayList 是最常用的数据结构，一般没有特殊需求的话ArrayList的效率是最高的。

数据存储

private transient Object[] elementData;

private : 该属性只能再该类内部被访问
transient：序列化的时候不序列化该对象

动态删除问题

结论：不能通过任何方法对内部的elementData同时进行遍历和增删操作

有时候需要在遍历的时候对结构作调整，比如增加或者删除，都会引发size的变化。所以要是直接操作list的话有明显的错误，但是使用iterator的时候也要注意，像如下代码。

ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(10);
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            Integer integer = iterator.next();
            if (integer == 10) {
                list.remove(integer);//fix: iterator.remove()
            }
        }

通过看源码可以发现这个异常是主动抛出的，modCount记录了增删elementData的次数，而生成iterator的时候会将初始的modCount记录在iterator内部。每次调用next()方法的时候都会检查modCount的值，确保遍历的时候没有元素数组增删操作。修改的方法也很简单，就是使用iterator的remove()方法来解决，这个方法会保证一致性。

多线程方案：

在使用iterator迭代的时候使用synchronized或者Lock进行同步；

使用并发容器CopyOnWriteArrayList代替ArrayList和Vector。

这种情况也可以推广到多线程，一个线程用iterator遍历数组，另一个线程来做增删操作，也会发生同样的问题。：

public class Test {
    static ArrayList<Integer> list = new ArrayList<Integer>();
    public static void main(String[] args)  {
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        Thread thread1 = new Thread(){
            public void run() {
                Iterator<Integer> iterator = list.iterator();
                while(iterator.hasNext()){
                    Integer integer = iterator.next();
                    System.out.println(integer);
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            };
        };
        Thread thread2 = new Thread(){
            public void run() {
                Iterator<Integer> iterator = list.iterator();
                while(iterator.hasNext()){
                    Integer integer = iterator.next();
                    if(integer==2)
                        iterator.remove(); 
                }
            };
        };
        thread1.start();
        thread2.start();
    }
}

参考连接

ConcurrentModificationException异常原因和解决方法

LinkedList

内部是Node类型，存储上一个节点和下一个节点，是一个双向链表

存储结构

transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
}

与ArrayList对比

主要是两种数据结构的对比。一个是数组，一个链表。以数组为基本数据结构的话都涉及到一个扩容的问题，ArrayList是每次增加两倍，时间复杂度上与使用链表也是不同的。链表的特性更易于删除和增加，而数组更易于访问下标。所以随机访问的时间复杂度很高

HashMap

数组+链表的存储结构，HashSet内部也是用HashMap来实现的，非线程安全

数据存储

static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
}

HashMap实现原理
 resize()导致的多线程死循环问题

hash算法

final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

JDK1.7异或了很多次，而JDK1.8的话是只异或了一次。首先先看一下indexFor函数：

    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

这里利用了如果length是2的整次幂的话，这样length-1就正好相当于一个“低位掩码”， “与”操作的结果就是散列值的高位全部为零，如果length=16的话，那么就是只留后四位。这样的方式比直接取摸要快。但是只使用后四位的话，直接丢弃到前面所有位数的信息，就很容易产生冲突，影响散列的效果。这个时候就会使用到上面的hash()算法中使用的异或，将hashCode前几位通过右移之后和原始hashCode进行异或操作，这样就使用了前面部分抛弃的位数信息，减少了冲突的概率。

下面这幅图是JDK1.8的过程，hashCode()返回的是一个int值，JDK1.8简化了异或的过程，直接取32位中前16和后16位异或。

hash过程

LinkedHashMap

这个是HashMap的子类，其本质就是将HashMap的基础上增加了双向链表，在Entry里面加了一个before和after引用，内部集成了LRU算法，可以直接使用，每次访问的数据都将其放在链表的头

HashSet && LinkedHashSet

遍历的时候，LinkedHashSet是按照插入的顺序遍历的，而HashSet是无序的。HashSet的内部是使用HashMap来实现的，而LinkedHashSet内部是用LinkedHashMap来实现的。所以这两个的区别最终还是表现在HashMap和LinkedHashMap的区别上。

//HashMap
void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }
void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e); //直接将其插在最前面
        size++;
    }
    
//LinkedHashMap
@overwrite
void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }
@overwrite
void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header); //额外的操作
        size++;
    }
    
private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }
}

通过以上的比较可以看到，在HashMap的基础上，LinkedHashMap中的Entry增加了一个before和after的引用，在createEntry方法里面做了一步双向链表插入的操作，这样的话就是插入的对象就形成了一个环，每个节点有指向上一个和下一个的引用。下面看一下遍历时候的操作：

        //HashMap
        HashIterator() {
            expectedModCount = modCount;
            if (size > 0) { // advance to first entry
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }
        
        final Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();

            if ((next = e.next) == null) {
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
            current = e;
            return e;
        }
        
        //LinkedHashMap  
      private abstract class LinkedHashIterator<T> implements Iterator<T> {
        Entry<K,V> nextEntry    = header.after;
        Entry<K,V> lastReturned = null;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        int expectedModCount = modCount;

        public boolean hasNext() {
            return nextEntry != header;
        }

        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
        }

        Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }
    }

对于遍历的操作，LinkedHashMap是从header开始，到header结尾，是通过双向链表的环进行遍历的，和数组没有关系，所以是可以保证插入顺序的。而HashMap的遍历是从数组里找的，取第一个不为null的作为next，不能保证顺序性。

Java 集合类源码笔记(JDK1.7)

ArrayList

数据存储

动态删除问题

参考连接

LinkedList

存储结构

与ArrayList对比

HashMap

数据存储

hash算法

LinkedHashMap

HashSet && LinkedHashSet

推荐阅读更多精彩内容