面试总结----java集合

春节刚过，打算换一份工作，于是就开始了一段准备面试的生活，准备的这段时间内，学到很

多知识，现在做个总结，总共分java集合、java虚拟机、多线程、spring等四个部分，由于个

人知识有限，在总结过程中，难免出现不当地方，如发现，请指出。
下面就开始第一部分：java集合

一、集合结构图
图中蓝色字体标示的是接口，黑色字体标示的是具体实现
1.Collection结构图



2.Map结构图



说明：
  a.List表示列表，里面的元素可重复，有顺序
   

Vector为List的线程安全实现，底层采用数组的作为存储结构，方法上使用synchronized来实现同步，并发性差，因为这里采用的是对象的内部锁，一个对象只有一个内部锁，当一个线程获取了这个对象(这里的对象即为Vector类型的对象)的内部锁之后，其他线程想要获取这个对象的内部锁的时候，只能等待了，关于线程安全问题，在线程部分讲解。与Vector相对应的非线程安全实现为ArrayList.

   

ArrayList底层采用数组作为存储结构来实现List的，当执行add操作的时候，如果数组已经装满数据了，这时就需要数组容量扩展为原来的1.5倍。

   

LinkedList底层使用双向链表作为存储结构，传入的泛型参数一定要是基本类型除外的其他类型，链表中的每个节点使用Node来存储，Node的定义如下：

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

每次进行add操作的时候默认是插在链表的末尾，也可以指定插入位置。
  b.Set表示集合，即里面的元素不能重复，重复与否是通过泛型类型的实际类型的比较器来实现的，底层是通过Map来实现的，利用Map的key不能重复的特性来实现。
  

HashSet底层使用HashMap来实现，HashSet里面的所有元素，对应到HashMap里面就是一个Key，向HashSet里面添加元素的代码如下：

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

PRESENT为Object对象。
  

TreeSet是通过TreeMap来存储数据和排序的。

  c.Queue为队列，即满足FIFO规则，对应有单向队列（从一边进，从另一边出），双向队列（两边都可以进出，从一边进，可以从两边出）。ArrayBlockingQueue、LinkedBlockingQueue主要用来实现生产者消费者模式的应用。
  

ArrayBlockingQueue,数组实现的单向队列，底层通过数组来实现。ArrayBlockingQueue里面的属性有：

    /** The queued items */
    final Object[] items;

    /** items index for next take, poll, peek or remove */
    int takeIndex;

    /** items index for next put, offer, or add */
    int putIndex;

    /** Number of elements in the queue */
    int count;

    /*
     * Concurrency control uses the classic two-condition algorithm
     * found in any textbook.
     */

    /** Main lock guarding all access */
    final ReentrantLock lock;
    /** Condition for waiting takes */
    private final Condition notEmpty;
    /** Condition for waiting puts */
    private final Condition notFull;

Object数组用来存储数据，takeIndex用来存放下一个可以取得数据的索引位置，每次进行取出数据时，需要进行如下操作：

 takeIndex = inc(takeIndex);

    final int inc(int i) {
        return (++i == items.length) ? 0 : i;
    }

putIndex用来存放下一个可以存放元素的索引位置，存储操作时，putIndex的设置为：

 putIndex = inc(putIndex);
    final int inc(int i) {
        return (++i == items.length) ? 0 : i;
    }

lock和condition主要用来保证线程安全。

 

LinkedBlockingQueue使用双向链表来实现，底层数据结构为：

    static class Node<E> {
        E item;

        /**
         * One of:
         * - the real successor Node
         * - this Node, meaning the successor is head.next
         * - null, meaning there is no successor (this is the last node)
         */
        Node<E> next;

        Node(E x) { item = x; }
    }

    /**
     * Head of linked list.
     * Invariant: head.item == null
     */
    private transient Node<E> head;

    /**
     * Tail of linked list.
     * Invariant: last.next == null
     */
    private transient Node<E> last;

每次元素进入队列时都是接在last的后面，出队列时，都是从head那里出。
使用java.util.concurrent包下面的ReentrantLock、Condition、AtomicInteger来保证线程安全。

  d.Deque即为double ended queue，双端队列，两边都可以进出队列。
   

ArrayDeque底层使用数组来实现，部分代码为：

    private transient E[] elements;

    /**
     * The index of the element at the head of the deque (which is the
     * element that would be removed by remove() or pop()); or an
     * arbitrary number equal to tail if the deque is empty.
     */
    private transient int head;

    /**
     * The index at which the next element would be added to the tail
     * of the deque (via addLast(E), add(E), or push(E)).
     */
    private transient int tail;

非线程安全的双端队列实现。
 

LinkedBlockingDeque底层采用双向链表来实现，部分代码为：

    /** Doubly-linked list node class */
    static final class Node<E> {
        /**
         * The item, or null if this node has been removed.
         */
        E item;

        /**
         * One of:
         * - the real predecessor Node
         * - this Node, meaning the predecessor is tail
         * - null, meaning there is no predecessor
         */
        Node<E> prev;

        /**
         * One of:
         * - the real successor Node
         * - this Node, meaning the successor is head
         * - null, meaning there is no successor
         */
        Node<E> next;

        Node(E x) {
            item = x;
        }
    }

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

使用ReentrantLock、Condition来保证线程安全。
e.Map的实现常用的有三种，HashMap、Hashtable、TreeMap.Map没有继承Collection，原因为：Collection一次只存储单个元素，Map一次存储需要存储Key和Value。
 

HashMap底层是一个数组，数组里面的类型是Entry，Entry的定义如下：

    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
        }
     //省略部分代码
    }

   可以看出，每个Entry里面有key、hash、value、next为Entry的属性。数组中的每个位置都是一个Entry类型的数据，这个数据含有指向下一个Entry的属性，即next.在进行put操作的时候，如果当前数组里面存储的元素数量超出了事先设置的阈值，则需要进行容量扩展，需要进行数组元素值复制、rehash等操作。底层的数组及链表的数据结构为：



HashMap中的Key需要重写hashCode和equals,hashCode用来定位，equals用来比较，及hashCode的作用为将需要插入的元素的位置定位到数组的哪个索引上，equals用来和链表上的元素进行比较，看是要插入的值的key是否已经存在，如果存在，则将新value替换老value值。

 

Hashtable为HashMap的线程安全实现，但是有如下不同：

     HashMap的key和value都可以为null，Hashtable的key和value不能为null，否则抛出异常，原因是Hashtable继承了Dictionary，Dictionary中的key和value不允许为null。
     hash算法不一样。HashMap的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);
    }

Hashtable的hash算法实现如下：

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

    Hashtable在多数方法上加上了synchronized，即多线程下不会产生并发问题，HashMap会在多线程下产生并发问题。
   

TreeMap是红黑树理论的一种实现，维护一个Comparator和一个Entry，Comparator为构造实例时传进来的比较器，红黑树中的每一个节点对应一个Entry，Entry的实现如下：

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left = null;
        Entry<K,V> right = null;
        Entry<K,V> parent;
        boolean color = BLACK;
   //省略部分代码
}

     可以看出一个Entry有指向父节点，左右子节点的引用。TreeMap的Key需要实现一个比较器，比较好的做法是，构造TreeMap时传入一个比较器，比较器是基于key实现的。