Java数据结构

java集合类主要分为两大体系，继承自Collection的List和Set,还有自己作为根的Map.大体的结构如下.

Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│　└Stack
└Set
 ├HashSet
 ├TreeSet
Map
├Hashtable
├HashMap
└TreeMap
└WeakHashMap

Map

HashMap通过hash表实现的key-value存储，按照key的hashCode存储，可以有null key,
TreeMap是有序的，通过key的Comparable比较器实现key-value的有序存储
LinkedHashMap也是有序的，也是通过key的hashCode存储，但是遍历是增加了有序属性，即与加入的顺序保持一致

HashMap

HashMap是基于hash算法实现的，通过hash因子的作用，将元素"比较平均"的分散，以提高元素查找的命中率.具体的实现原理如下图：

HashMap是非线程安全的，允许null key,当threshold=capacity*loadfactor时会扩容为capacity<<1,这里capacity为桶的数量.

以下是put<k,v>()方法：

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

可以看到优先判断null key，然后计算key的hash值，通过hash值与capacity结合判断位于Hash桶的位置,然后判断是否有当前key的Entry,如果存在，替换value为新值，并返回旧的value，否则添加一个新的Entry,并且返回null，如果一个桶已有至少一个Entry，则会作为链表的第一个元素插入.

HashTable

HashTable的原理与HashMap原理类似，只是比较特殊的所有操作加上了对当前对象操作的synchronized,以达到同步锁的功能，从而实现线程同步.

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = hash(key);
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

    modCount++;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = hash(key);
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    Entry<K,V> e = tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
    return null;
}

 private int hash(Object k) {
        // hashSeed will be zero if alternative hashing is disabled.
        return hashSeed ^ k.hashCode();
    }

从上可知,HashTable不允许加入null key,null value.

还有一个就是，HashTable初始容量是11.

Collection

Hashset

Hashset本应不在map系列,但由于Hashset的实现是基于HashMap实现的，所以这里列出，

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 */
public HashSet() {
    map = new HashMap<>();
}

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

从上可以看出,每次add一个元素，其实是将该元素当做一个key存入Hashmap中,value为一个"dummy value"(一个Object对象).所以其实是通过Hashmap保证了元素的唯一.

LinkedList与Queue

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

可知LinkedList实现了Deque，而Deque是丰富了父接口Queue，
Queue是Collection接口的子类，Collection实现了Iterable,所以是可遍历的。

而Map没有实现Iterable，但是通过一系列方法如entrySet()等转换成集合类Set来实现遍历功能.

Arraylist

Arraylist的实现是基于数组的，初始数组大小为10,容量不足时扩展为原来的1.5倍.

Collections

Collections主要是作为集合方法的一些扩展，有大量的static方法，来帮助我们方便的处理集合，在其中主要摘两点做一些研究：

不变的empty集合

Collections含有很多的静态空集合方法，其实我们使用这些特性的地方无非有两处：

1. 在自己的方法中return null处return Collections.emptyList(),这样可以避免上层调用使用时发生NullPointException.
   2.返回一个不可变(引用不可变)的集合实例.

  @SuppressWarnings("unchecked")
   public static final <T> List<T> emptyList() {
       return (List<T>) EMPTY_LIST;
   }

  @SuppressWarnings("unchecked")
   public static final List EMPTY_LIST = new EmptyList<>();

上面是返回emptyList的源码.

不变的empty迭代器

大多数空方法返回的是不变空集合，但是有以下三个方法返回的是空迭代器：<T> Enumeration<T> emptyEnumeration() (classic iteration method), <T> Iterator<T> emptyIterator(), and <T> ListIterator<T> emptyListIterator()
作用也无非上面返回空集合的那些作用.

    @SuppressWarnings("unchecked")
    public static <T> Iterator<T> emptyIterator() {
        return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
    }

    private static class EmptyIterator<E> implements Iterator<E> {
        static final EmptyIterator<Object> EMPTY_ITERATOR
            = new EmptyIterator<>();

        public boolean hasNext() { return false; }
        public E next() { throw new NoSuchElementException(); }
        public void remove() { throw new IllegalStateException(); }
    }

综上，我们可以得出结论，这些空方法可以帮助我们让编码更安全，防止空引用的发生。

Extend

ConcurrentModificationException while Iterating over ArrayList

3 ways to find duplicate elements in an array Java