面试容器

hashmap实现的数据结构，数组、桶等。

image.png

如图所示 JDK 1.7，是以数组+链表组成的，链表为相同hash的键值对，表头储存在数组中，形成以拉链的结构，这就是他的数据结构，当有新的键值对插入的时候， hash函数得到数组的位置，如果根据位置找到放入键值对，如果该位置存在键值对，就遍历到表尾，进行放入。
桶就是上述的链表的，数组被叫做桶数组。
在JDK1.8后，链表长度大于8后，会树化变为红黑树。相当于数组+链表+红黑树组成。

hashmap是空的情况下，map.get(a) 得到的是啥

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 1. 定位键值对所在桶的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 2. 如果 first 是 TreeNode 类型，则调用黑红树查找方法
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                
            // 2. 对链表进行查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

来自JDK 1.8 get方法，内部会调用getNode，因为未被初始化，（初始化时在put操作时候进行的），table==null，return null。

HashMap怎么手写实现？

理解到就是数组+链表的实现
https://blog.csdn.net/it_lihongmin/article/details/76377229

hashmap如何put数据（从hashmap源码角度讲解）？

环境JDK1.8
插入操作的入口方法是 put(K,V)，

public V put(K key, V value) {
    return putVal(hash(key), 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;
    // 初始化桶数组 table，table 被延迟到插入新数据时再进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果桶中不包含键值对节点引用，则将新键值对节点的引用存入桶中即可
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
            
        // 如果桶中的引用类型为 TreeNode，则调用红黑树的插入方法
        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);
                    // 如果链表长度大于或等于树化阈值，则进行树化操作
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                // 条件为 true，表示当前链表包含要插入的键值对，终止遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 判断要插入的键值对是否存在 HashMap 中
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 键值对数量超过阈值时，则进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
  }

当桶数组 table 为空时，通过扩容的方式初始化 table
查找要插入的键值对是否已经存在，存在的话根据条件判断是否用新值替换旧值
如果不存在，则将键值对链入链表中，并根据链表长度决定是否将链表转为红黑树
判断键值对数量是否大于阈值，大于的话则进行扩容操作

Resize操作的过程。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果 table 不为空，表明已经初始化过了
    if (oldCap > 0) {
        // 当 table 容量超过容量最大值，则不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } 
        // 按旧容量和阈值的2倍计算新容量和阈值的大小
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    } else if (oldThr > 0) // initial capacity was placed in threshold
        /*
         * 初始化时，将 threshold 的值赋值给 newCap，
         * HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
         */ 
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        /*
         * 调用无参构造方法时，桶数组容量为默认容量，
         * 阈值为默认容量与默认负载因子乘积
         */
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // newThr 为 0 时，按阈值计算公式进行计算
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 创建新的桶数组，桶数组的初始化也是在这里完成的
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 如果旧的桶数组不为空，则遍历桶数组，并将键值对映射到新的桶数组中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 重新映射时，需要对红黑树进行拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍历链表，并将链表节点按原顺序进行分组
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 将分组后的链表映射到新桶中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

计算新桶数组的容量 newCap 和新阈值 newThr
根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的
将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。

- 简单说说 JDK1.7 中 HashMap 什么情况下会发生扩容？如何扩容？

JDK1.7中HashMap扩容比较简单，键值对的数量 >=threshold = capacity * loadFactor就达到扩容的条件，
1.先模运算定位我们要插入这个桶的位置
2.判断插入的桶子是否为空，为空就将键值对存入即可，不为空则遍历到表的最后一个存入，或者更新Node.

- 简单说说 JDK1.7 中 HashMap 什么情况下会发生扩容？如何扩容？

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

通过以上代码能够得知，当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容.扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍.

扩容操作发生在resize（int newCapacity）

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
    
    
void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
　　　　　//for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
　　　　　　　　　 //将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

这个方法就是将每个Node遍历出来，通过key值进行hash扰乱运算后，与length-1取余得到新的下标，放入的流程和put一样。
http://www.cnblogs.com/chengxiao/p/6059914.html

hashmap容量为2次幂的原因。

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-1 ，比如length=16，得到就是15，为11111，这样的低位和高位的或运算得到得到的可能会更多，所以分布就更为均匀，从而减少了碰撞的几率。
https://blog.csdn.net/qq_36523667/article/details/79657400
http://www.cnblogs.com/chengxiao/p/6059914.html

HashMap的实现，与HashSet的区别

HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

当两个不同的键对象的hashcode相同时会发生什么？它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。

https://www.cnblogs.com/beatIteWeNerverGiveUp/p/5709841.html
https://www.cnblogs.com/beatIteWeNerverGiveUp/p/5709841.html

HashSet与HashMap怎么判断集合元素重复

发现HashSet是借助HashMap来实现的，存入的元素作为key，利用HashMap中Key的唯一性，来保证HashSet中不出现重复值，所以最终得看HashMap源码如何判断元素重复的。

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    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;
        }
    }
}

在put可以看见先的得到下标，然后遍历每一个元素比较hashcode（）和equal（）来判断是否唯一。
注意：为了保证对象不会出现重复值，被存方的元素必须重写equal（）。
https://blog.csdn.net/ning109314/article/details/17354839

简单说说 HashMap 和 LinkedHashMap 的区别

LinkedHashMap 实现与 HashMap 的不同之处在于，LinkedHashMap 维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。该迭代顺序通常就是将键插入到映射中的顺序，如果在映射中重新插入键，则插入的顺序将不受影响。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比 LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。

https://www.cnblogs.com/hubingxu/archive/2012/02/21/2361281.html
http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html
https://blog.csdn.net/xiyuan1999/article/details/6198394
https://blog.csdn.net/qq_33535433/article/details/80035383
https://blog.csdn.net/lzm1340458776/article/details/37816073

说说你对 LinkedHashSet 的理解及其与 HashSet 的关系？

LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。

关系LinkedHashSet继承与HashSet,但只是在构造函数里调用父类的构造函数并且传入LinkedHashMap，而LinkedHashMap内部维护的双向链表，这让LinkedHashSet具有保存迭代顺序顺序的功能，LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。
https://www.cnblogs.com/Terry-greener/archive/2011/12/02/2271707.html

HashMap是如何解决hash碰撞的？拉链法的优缺点

利用（JDK1.7以下）拉链法，解决hash冲突

hash:散列，是把任意长度的输入，通过散列算法，变成固定长度的输出，该输出就是散列值。这种转换是一种 压缩映射，也就是说，散列值的空间通常远小于输入的空间。不同的输入可能会散列成相同的输出，从而不可能从散列值来唯一的确定输入值。简单的说，就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
hash冲突：就是根据key即经过一个哈希函数f(key)运算得到的结果i的作为地址去存放当前的key value键值对(这个是hashmap的存值方式)，但是却发现算出来的地址上存在另外的键值对（不为空），这就成为hash冲突。
链地址法（拉链法）：JDK1.7 hashmap用的拉链法，将哈希值相同的元素以链表形式排列，并且表头的地址为hash表的第i个元素
，在JDK1.8之后则是一个混合模式，如果单链表的节点大于8，单链表会树化为红黑树储存具有相同hash的元素。
[图片上传失败...(image-50d3cd-1535258600772)]

优点：
解决了线性探测所导致的太多的哈希冲突。
删除结点相比于开放定址法更容易实现（在线性探测中如果删除结点，后面的结点无法访问）。
由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点

缺陷：如果相同元素过多，元素在一个桶内部链接过长，反而导致时间复杂度上升。解决思路是桶中元素不再指向链表，而指向一个红黑树
指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

Hash怎么防止碰撞

防止还是难以防止，但是可以减少Hash碰撞

构造hash时增大initialCapacity，减少loadFactor
重写hashCode方法，增加得到hash的复杂度
传入类的时候按照规则重写自定义类equal方法

hashmap的参数及影响性能的关键参数：加载因子和初始容量。

简单说说你对 HashMap 构造方法中 initialCapacity（初始容量）、loadFactor（加载因子）的理解

initialCapacity：初始化hashTable的长度，是影响扩容阀值因素之一，默认16，扩容时候数组长度会变成2倍，不管如何内部会调用tableSizeFor（）使用位运算找到大于或等于该值的最小2的幂，作为Capacity储存，而initialCapacity将会被弃用。
loadFactor：
在节点均匀分布在桶数组中的条件下，可以调节负载因子。
节负载因子低时，HashMap容纳的键值对变少了，扩容时候，重写将键值对储存新的通数组里，这样hash碰撞就降低了，链表变短了，增删查改的操作效率就会变高。
节负载因子高的时候，HashMap容纳的键值对变高，空间利用率变高，链表边长，效率变低，时间和空间的互换

HashSet 和 TreeSet

HashSet、LinkedHashSet与TreeSet有什么区别，应用场景是什么？

https://www.cnblogs.com/Terry-greener/archive/2011/12/02/2271707.html
https://blog.csdn.net/StemQ/article/details/66477615
https://www.jianshu.com/p/14bd5d9654fe
http://www.coolblog.xyz/2018/01/11/TreeMap%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/

HashSet使用哈希表实现的，元素是无序的。添加、删除操作时间复杂度都是O(1)。
TreeSet内部结构是一个树结构(红黑树)，元素是有序的，添加、删除操作时间复杂度为O(log(n))，并且提供了first(), last(), headSet(), tailSet()等方法来处理有序集合。
TreeSet不允许重复，不允许null值（如果有基于null的比较器，就可以允许为null），默认按升序排列。
LinkedHashSet是HashSet的子类，是介于HashSet 和 TreeSet之间，内部是一个双向链表结构，时间复杂度是O(1)。允许null值，保留插入顺序，非线程安全。

简而言之,如何你需要的是一个快速的集合，建议你使用HashSet，如果你需要的是一个排序集合，请选择TreeSet，如果你需要一套能够存储插入顺序的集合,请使用LinkedHashSet。

请使用 Java 集合实现一个简约优雅的 LRU 容器

由于 LinkedHashMap 天生支持插入顺序或者访问顺序的 key-value 对，而 LRU 算法的核心恰巧用到它的访问顺序特性，即对一个键执行 get、put 操作后其对应的键值对会移到链表末尾，所以最末尾的是最近访问的，最开始的是最久没被访问的。LinkedHashMap 有一个 boolean 类型的 accessOrder 参数，当该参数为 true 时则按照元素最后访问时间在双向链表中排序，为 false 则按照插入顺序排序，默认为 false，所以这里需要的操作就是 accessOrder 为 true 的情况。
。

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
            private int maxEntries;//maxEntries 最大缓存个数

            public LRUCache(int maxEntries) {
                super(16, 0.75f, true);
                this.maxEntries = maxEntries;
            }

            //在添加元素到LinkedHashMap后会调用这个方法，传递的参数是最久没被访问的键值对，
            // 如果这个方法返回true则这个最久的键值对就会被删除，LinkedHashMap的实现总是返回false，
            // 所以容量没有限制。
            @Override
            protected boolean removeEldestEntry(Entry<K, V> eldest) {
                return size() > maxEntries;
            }
        }

可以看见实现的简约 LRU 容器核心优雅点就是充分利用了 LinkedHashMap 的有序性特性和容量限制特性。

- List/Set/Map三者的区别.

简单说说你理解的 List 、Map、Set、Queue 的区别和关系

List 和 Map 的实现方式以及存储方式

List,Set,Map的区别，实现方式以及存储方式。

集合的接口和具体实现类，介绍

容器类介绍以及之间的区别

Collection

一组"对立"的元素，通常这些元素都服从某种规则

List必须保持元素特定的顺序
Set不能有重复元素
Queue保持一个队列(先进先出)的顺序

2) Map

一组成对的"键值对"对象

Collection和Map的区别在于容器中每个位置保存的元素个数:

Collection 每个位置只能保存一个元素(对象)
Map保存的是"键值对"，就像一个小型数据库。我们可以通过"键"找到该键对应的"值"

List

共性：有序可以重复
List集合特征：

允许重复元素添加
有序：放入的顺序和取出的顺序是一样的
一个List可以生成ListIterator,使用它可以从两个方向遍历List,也可以从List中间插入和移除元素。

List接口主要实现类包括：

ArrayList() 代表长度可以改变得数组。可以对元素进行随机的访问，向ArrayList()中插入与删除元素的速度慢。没有线程安全，性能高
LinkedList()双向链表式算法: 在实现中采用链表数据结构。每次操作插入删除，只需要修改元素的后置节点引用，不需要后面元素移动位置，插入和删除速度快，每次都要从开始往后依次查找，访问速度慢。

List接口对Collection进行了简单的扩充，它的具体实现类常用的有ArrayList和LinkedList。你可以将任何东西放到一个List容器中，并在需要时从中取出。ArrayList从其命名中可以看出它是一种类似数组的形式进行存储，因此它的随机访问速度极快，而LinkedList的内部实现是链表，它适合于在链表中间需要频繁进行插入和删除操作。在具体应用时可以根据需要自由选择。前面说的Iterator只能对容器进行向前遍历，而ListIterator则继承了Iterator的思想，并提供了对List进行双向遍历的方法。

Set集合

对象元素不能重复，Set的元素必须定义equals()方法以确保对象的唯一性。
可排序
也是Collection的一种扩展加入，Set与Collection有完全一样的接口

set接口主要实现类包括：

HashSet：能快速定位一个元素，但是你放到HashSet中的对象需要实现hashCode()方法，它使用了前面说过的哈希码的算法。该也是线程不安全的，它不允许出现重复元素；允许包含值为null的元素，但最多只能有一个null元素。不能保证元素的插入顺序，添加也是通过add进行添加的，而输出则是通过迭代Iteratori=hash.iterator();来实现的。
而TreeSet则将放入其中的元素按序存放，这就要求你放入其中的对象是可排序的，这就用到了集合框架提供的另外两个实用类Comparable和Comparator。一个类是可排序的，它就应该实现Comparable接口。有时多个类具有相同的排序算法，那就不需要在每分别重复定义相同的排序算法，只要实现Comparator接口即可。

map接口：

是一种把键对象和值对象进行关联的容器，而一个值对象又可以是一个Map，依次类推，这样就可形成一个多级映射。一个Map容器中的键对象不允许重复。当然在使用过程中，某个键所对应的值对象可能会发生变化，这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求。你可以将任意多个键都映射到一个值对象上，这不会发生任何问题（不过对你的使用却可能会造成不便，你不知道你得到的到底是那一个键所对应的值对象）。
Map有两种比较常用的实现：

HashMap HashMap也用到了哈希码的算法，以便快速查找一个键，无序
TreeMap。TreeMap则是对键按序存放，因此它便有一些扩展的方法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。键和值的关联很简单，用pub(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。

Queue

用于模拟"队列"这种数据结构(先进先出 FIFO)。队列的头部保存着队列中存放时间最长的元素，队列的尾部保存着队列中存放时间最短的元素。新元素插入(offer)到队列的尾部，访问元素(poll)操作会返回队列头部的元素，队列不允许随机访问队列中的元素。结合生活中常见的排队就会很好理解这个概念。

PriorityQueue
PriorityQueue并不是一个比较标准的队列实现，PriorityQueue保存队列元素的顺序并不是按照加入队列的顺序，而是按照队列元素的大小进行重新排序，这点从它的类名也可以看出来
Deque
Deque接口代表一个"双端队列"，双端队列可以同时从两端来添加、删除元素，因此Deque的实现类既可以当成队列使用、也可以当成栈使用
ArrayDeque
是一个基于数组的双端队列，和ArrayList类似，它们的底层都采用一个动态的、可重分配的Object[]数组来存储集合元素，当集合元素超出该数组的容量时，系统会在底层重新分配一个Object[]数组来存储集合元素

这篇文章赞：https://blog.csdn.net/KingCat666/article/details/75579632

List, Set, Map是否继承自Collection接口?

List, Set继承Collection接口，List接口对Collection进行了简单的扩充，而Set也是Collection的一种扩展加入，Set与Collection有完全一样的接口，Collection 每个位置只能保存一个元素(对象)。
Map 是一种把键对象和值对象进行关联的容器，没有继承于Collection接口，Map就像一个小型数据库。我们可以通过"键"找到该键对应的"值"。

Collection 和 Collections的区别

java.util.Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式。
java.util.Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于Java的Collection框架。
http://pengcqu.iteye.com/blog/492196

hashtable和hashmap异同。

HashTable 基于 Dictionary 类，而 HashMap 是基于 AbstractMap。Dictionary 是任何可将键映射到相应值的类- 的抽象父类，而 AbstractMap 是基于 Map 接口的实现，它以最大限度地减少实现此接口所需的工作。
HashMap 的 key 和 value 都允许为 null，而 Hashtable 的 key 和 value 都不允许为 null。HashMap 遇到 key 为 null 的时候，调用 putForNullKey 方法进行处理，而对 value 没有处理；Hashtable遇到 null，直接返回 NullPointerException。
Hashtable 方法是同步，而HashMap则不是。我们可以看一下源码，Hashtable 中的几乎所有的 public 的方法都是 synchronized 的，而有些方法也是在内部通过 synchronized 代码块来实现。所以有人一般都建议如果是涉及到多线程同步时采用 HashTable，没有涉及就采用 HashMap，但是在 Collections 类中存在一个静态方法：synchronizedMap()，该方法创建了一个线程安全的 Map 对象，并把它作为一个封装的对象来返回。HashTable是线程安全的.

为什么hashtable被弃用？

hashtable的线程安全的策略实现代价太大，而且简单粗暴，get/put的方法操作都是synchronized，这相当于给整个hash表加了一个大大的锁，多线程访问时候所有操作都得串行，在激烈的并发场景的性能会变得相当的差。

hashtable线程安全、synchronized加锁

hashtable线程是安全，他和hashmap类似内部也是实现了拉链法的hash表，但是像put/get操作方法加上去synchronized关键词，使得多线程操作该容器时串行，保证了线程安全。

concurrenthashmap的插入操作是直接操作数组中的链表吗？

JDK1.7 版本第一步定位Segment并且确定Segemnt已经初始化、 2，调用segment这个加锁的put的方法3.重新定位hash在数组的位置，如果在Buket位置上已存在链表就得操作链表进行遍历插入到表尾
JDK1.8 版本

第一步根据hash定位索引位置，并且获取对应的索引位置（用Usafe.getObjectVolatile直接获得指定内存的数据保证拿到最新的数据）
如果 f ==null 用CAS直接插入Node
- 如果CAS成功，说明已经插入，然后判断是不是要扩容
- 如果失败，自旋尝试在插入
如果f的hash是-1 ，则说明其他线程正在扩容，
其余情况把新的Node节点按链表或红黑树的方式插入到合适的位置，这个过程采用同步内置锁实现并发。

说明1.7版本是先确定sgement的位置然后上锁调用其put方法插入链表，而1.8版本则是直接插入，不过如果是链表插入上的是同步锁

https://www.cnblogs.com/chengxiao/p/6842045.html
https://www.jianshu.com/p/c0642afe03e0

concurrenthashmap相比于hashtable做的优化、segment的概念、concurrenthashmap高效的原因

HashTable的线程安全使用的是一个单独的全部Map范围的锁，ConcurrentHashMap抛弃了HashTable的单锁机制，使用了锁分离技术，使得多个修改操作能够并发进行,只有进行SIZE()操作时ConcurrentHashMap会锁住整张表。
HashTable的put和get方法都是同步方法，而ConcurrentHashMap的get方法多数情况都不用锁，put方法需要锁。

但是ConcurrentHashMap不能替代HashTable,因为两者的迭代器的一致性不同的，hash table的迭代器是强一致性的，而concurrenthashmap是弱一致的。 ConcurrentHashMap的get，clear，iterator 都是弱一致性的。
hashtable是全局采用一个大锁，使用synchronized来保证线程安全，但是在竞争激烈的情况下HashTable的效率非常低下，但是在concurrenthashmap中则是把桶数组分为多个sgement，并给每个segment上重入锁ReentrantLock锁的分段锁形式

Segment继承了ReentrantLock，所以它就是一种可重入锁（ReentrantLock)。在ConcurrentHashMap，一个Segment就是一个子哈希表，Segment里维护了一个HashEntry数组，并发环境下，对于不同Segment的数据进行操作是不用考虑锁竞争的。（就按默认的ConcurrentLeve为16来讲，理论上就允许16个线程并发执行，有木有很酷）

ConcurrentHashMap之所以高效是因为它，把map表划分为了多个Segemnt，并且每个Segment继承了ReentrantLock，这样更好的降低了锁的粒度，
http://www.cnblogs.com/ynyhl/p/9317688.html
https://blog.csdn.net/MBuger/article/details/62418754
https://blog.csdn.net/hitxueliang/article/details/24734861

SpareArray做了哪些优化？

使用int[]数组存放key，避免了HashMap中基本数据类型需要装箱的步骤
不需要额外的结构体，单个元素的存储成本更低
数据量小的情况下，随机访问的效率更高

简单说一说SpareArray的插入流程？

public void put(int key, E value) {
    // 首先通过二分查找去 key 数组中查找要插入的 key，返回索引
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) {
      // 如果 i>=0 说明数组中已经有了该key，则直接覆盖原来的值
        mValues[i] = value;
    } else {
      // 取反，这里得到的i应该是最适合该key的插入位置，具体怎么得到的，后面会说
        i = ~i;
        // 如果索引小于当前已经存放的长度，并且这个位置上的值为DELETED(即被标记为删除的值)
        if (i < mSize && mValues[i] == DELETED) {
          // 直接赋值并返回，注意 size 不需要增加
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        // 到这一步说明直接赋值失败，检查当前是否被标记待回收且当前存放的长度已经大于或等于了数组长度
        if (mGarbage && mSize >= mKeys.length) {
            // 回收数组中应该被干掉的值
            gc();
            // 重新再获取一下索引，因为数组发生了变化
            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        // 最终在 i 位置上插入键与值，并且size ＋1
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

http://extremej.itscoder.com/sparsearray_source_analyse/

为什么 ArrayList 的增加或删除操作相对来说效率比较低？能简单解释下为什么吗？

只有删除，或者是添加插入指定的位置时候才会出现效率变低的问题，因为不管添加删除，都得移动添加删除位置后面得元素导致时间复杂度急剧上升。

image

http://www.coolblog.xyz/2018/01/28/ArrayList%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/#24-%E9%81%8D%E5%8E%86

ArrayList和Vector的区别，ArrayList与LinkedList有什么区别

- 简单说说 ArrayList 和 Vector 的区别

ArrayList和Vector的区别

ArrayList和Vector都实现了List接口，底层都是基于Java数组来存储集合元素
ArrayList使用transient修饰了elementData数组，而Vector则没有
Vector是ArrayList的线程安全版本，用synchronized上同步锁实现的，一个个大大的锁了解一下
容量扩充 ArrayList为0.5倍+1，而Vector若指定了增长系数，则新的容量=”原始容量+增长系数”, 否则增长为原来的1倍
https://www.cnblogs.com/skywang12345/p/3308833.html#a4
https://blog.csdn.net/itmyhome1990/article/details/76033175

ArrayList与LinkedList有什么区别

ArrayList是实现了基于动态数组的数据结构，而LinkedList是基于链表的数据结构；
对于随机访问get和set，ArrayList要优于LinkedList，因为LinkedList要移动指针；
对于添加和删除操作add和remove，一般大家都会说LinkedList要比ArrayList快，因为ArrayList要移动数据。但是实际情况并非这样，对于添加或删除，LinkedList和ArrayList并不能明确说明谁快谁慢。

添加删除情况：从源码可以看出来linkedhashmap耗时的地方主要是链表的遍历（尽管以及判断是否从左右边开始了）
而arrayList耗时的地方就是System.arraycopy，让index后面的元素的所有元素都移动。
所以当插入的数据量很小时，两者区别不太大，当插入的数据量大时，大约在容量的1/10之前，LinkedList会优于ArrayList，在其后就劣与ArrayList，且越靠近后面越差。

https://blog.csdn.net/eson_15/article/details/51145788

ArrayList 与 LinkedList 使用普通 for 循环遍历谁快谁慢？为什么？

https://blog.csdn.net/zhzzhz123456/article/details/53323093

Arraylist 的动态扩容机制是如何自动增加的？简单说说你理解的流程

在add方法里面判断是不是需要扩容（size+1），如果是需要就开始扩容，扩容计算出最小的容量，一般是初始化的开始，算出当然容量的下限，如果当前容量减去数组的长度大于0就开始扩容，扩容采用位运算得到扩容后的容量大小，然后进行边界检查，最后把老数组的元素copy到新的数组中，这样扩容就完成了，因为ArrayList的底部容器本身是数组，所以位置完全相同，就不存在计算扩容后还需要重新计算位置的问题。
http://www.coolblog.xyz/2018/01/28/ArrayList%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/
https://blog.csdn.net/u010176014/article/details/52073339

简单说说 Array 和 ArrayList 的区别？

应该是完美的答案：
http://blog.qianlicao.cn/translate/2016/03/09/array-vs-arraylist/

http://www.coolblog.xyz/2018/01/18/HashMap-%E6%BA%90%E7%A0%81%E8%AF%A6%E7%BB%86%E5%88%86%E6%9E%90-JDK1-8/
https://blog.csdn.net/caisini_vc/article/details/52452498

为什么现在都不提倡使用 Vector 了

答：因为 Vector 实现并发安全的原理是在每个操作方法上加锁，这些锁并不是必须要的，在实际开发中一般都是通过锁一系列的操作来实现线程安全，也就是说将需要同步的资源放一起加锁来保证线程安全，如果多个 Thread 并发执行一个已经加锁的方法，但是在该方法中又有 Vector 的存在，Vector 本身实现中已经加锁了，双重锁会造成额外的开销，即 Vector 同 ArrayList 一样有 fail-fast 问题（即无法保证遍历安全），所以在遍历 Vector 操作时又得额外加锁保证安全，还不如直接用 ArrayList 加锁性能好，所以在 JDK 1.5 之后推荐使用 java.util.concurrent 包下的并发类。此外 Vector 是一个从 JDK1.0 就有的古老集合，那时候 Java 还没有提供系统的集合框架，所以在 Vector 里提供了一些方法名很长的方法（如 addElement(Object obj)，实际上这个方法和 add(Object obj) 没什么区别），从 JDK1.2 以后 Java 提供了集合框架，然后就将 Vector 改为实现 List 接口，从而导致 Vector 里有一些重复的方法。

- 为什么使用 for-each 时调用 List 的 remove 方法元素会抛出ConcurrentModificationException 异常？

 int expectedModCount = modCount;
 
  final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
    
  public E remove(int index) {
    rangeCheck(index);

    modCount++;
    // 返回被删除的元素值
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 将 index + 1 及之后的元素向前移动一位，覆盖被删除值
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将最后一个元素置空，并将 size 值减1                
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

问题出在迭代器，其实for-each循环会在编译的时候转换为迭代器，在迭代的过程中remove会调用使得modcount增加，而在代码中expectedModCount的值还是原来那个modcount的值，导致抛出异常。
这篇文章的结尾做了具体的阐述：
http://www.coolblog.xyz/2018/01/28/ArrayList%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/

什么是 Vector 和 Stack，各有什么特点？

Vector 是线程安全的动态数组，同 ArrayList 一样继承自 AbstractList 且实现了 List、RandomAccess、Cloneable、Serializable 接口，内部实现依然基于数组，Vector 与 ArrayList 基本是一致的，唯一不同的是 Vector 是线程安全的，会在可能出现线程安全的方法前面加上 synchronized 关键字，其和 ArrayList 类似，随机访问速度快，插入和移除性能较差（数组原因），支持 null 元素，有顺序，元素可以重复，线程安全。

Stack 是继承自 Vector 基于动态数组实现的线程安全栈，不过现在已经不推荐使用了，Stack 是并发安全的后进先出，实现了一些栈基本操作的方法（其实并不是只能后进先出，因为继承自 Vector，所以可以有很多操作，严格说不是一个栈）。其共同点都是使用了方法锁（即 synchronized）来保证并发安全的。

Collections.emptyList() 与 new ArrayList() 有什么区别

在这篇文章中提到如果你想返回一个空的List最好的方式就是返回Collections.emptyList（），且支持泛型，但是如果是return new ArrayList（）的话，ArrayList()在初始化时会占用一定的资源增加开销，这不是一个好的选择。
https://blog.csdn.net/liyuming0000/article/details/49474659

容器类中fastfail的概念

fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。

例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。
解决方法:改换成线程安全的类。
若 “modCount 不等于 expectedModCount”，则抛出ConcurrentModificationException异常，产生fail-fast事件。

https://blog.csdn.net/coslay/article/details/44891035

CopyOnWriteArrayList的了解。

CopyOnWriteArrayList这是一个ArrayList的线程安全的变体，其原理大概可以通俗的理解为:初始化的时候只有一个容器，很常一段时间，这个容器数据、数量等没有发生变化的时候，大家(多个线程)，都是读取(假设这段时间里只发生读取的操作)同一个容器中的数据，所以这样大家读到的数据都是唯一、一致、安全的，但是后来有人往里面增加了一个数据，这个时候CopyOnWriteArrayList 底层实现添加的原理是先copy出一个容器(可以简称副本)，再往新的容器里添加这个新的数据，最后把新的容器的引用地址赋值给了之前那个旧的的容器地址，但是在添加这个数据的期间，其他线程如果要去读取数据，仍然是读取到旧的容器里的数据。
https://blog.csdn.net/likailonghaha/article/details/53405895
https://blog.csdn.net/hua631150873/article/details/51306021

并发集合了解哪些

之前聊到的hashtable concurrentHashmap CopyOnWriteArrayList Vector ..都可以聊
http://youyu4.iteye.com/blog/2352846

简单说说 Comparable 和 Comparator 的区别和场景？

区别

Comparable可以认为是一个内比较器，实现了Comparable接口的类有一个特点，就是这些类是可以和自己比较的，至于具体和另一个实现了Comparable接口的类如何比较，则依赖compareTo方法的实现，compareTo方法也被称为自然比较方法。如果开发者add进入一个Collection的对象想要Collections的sort方法帮你自动进行排序的话，那么这个对象必须实现Comparable接口。
Comparator可以认为是是一个外比较器，个人认为有两种情况可以使用实现Comparator接口的方式：
1、一个对象不支持自己和自己比较（没有实现Comparable接口），但是又想对两个对象进行比较
2、一个对象实现了Comparable接口，但是开发者认为compareTo方法中的比较方式并不是自己想要的那种比较方式

场景

如果实现类没有实现Comparable接口，又想对两个类进行比较（或者实现类实现了Comparable接口，但是对compareTo方法内的比较算法不满意），那么可以实现Comparator接口，自定义一个比较器，写比较算法
如果比较的方法只要用在一个类中，用该类实现Comparable接口就可以。
如果比较的方法在很多类中需要用到，就自己写个类实现Comparator接口，这样当要比较的时候把实现了Comparator接口的类传过去就可以，省得重复造轮子。这也是为什么Comparator会在java.util包下的原因。

https://blog.csdn.net/u011240877/article/details/53399019
https://www.cnblogs.com/linbingdong/p/5300720.html

简单说说 EnumMap 的实现原理

简单谈谈你对 EnumMap 的理解及其特点与应用场景？

简单说说 EnumMap 的实现原理

https://www.jianshu.com/p/d842893c4cb2
https://mp.weixin.qq.com/s?__biz=MzIxOTI1NTk5Nw==&mid=2650047360&idx=1&sn=129ffbc5b963b5d6a692aae595e2b402&chksm=8fde2652b8a9af446be044953353fc89ea69627e472969fc7b4e9f32d10565c80b584d785ff5&scene=21#wechat_redirect

说说 EnumSet 怎么用，其基本原理是什么

https://www.cnblogs.com/swiftma/p/6044718.html
https://blog.csdn.net/bolink5/article/details/4201384

简单说说什么是 Deque 以及 ArrayDeque 与 LinkedList 的区别及特点

Deque 是一个双端队列接口，Deque 扩展了 Queue，有队列的所有方法，还可以看做栈，有栈的基本方法 push/pop/peek，还有明确的操作两端的方法 addFirst/removeLast 等，主要如下：

//将指定元素插入双向队列开头
        void addFirst (Object e );
        // 将指定元素插入双向队列末尾
        void addLast (Object e );
        // 返回对应的迭代器，以逆向顺序来迭代队列中的元素
        Iterator descendingIterator ();
        // 获取但不删除双向队列的第一个元素
        Object getFirst ();
        // 获取但不删除双向队列的最后一个元素 
        Object getLast ();
        // 将指定元素插入双向队列开头 
        boolean offerFirst (Object e );
        // 将指定元素插入双向队列结尾 
        boolean offerLast (Object e );
        // 获取但不删除双向队列的第一个元素，如果双端队列为空则返回 null 
        Object peekFirst ();
        // 获取但不删除双向队列的最后一个元素，如果此双端队列为空则返回 null 
        Object peekLast ();
        // 获取并删除双向队列的第一个元素，如果此双端队列为空则返回 null
        Object pollFirst ();
        // 获取并删除双向队列的最后一个元素，如果此双端队列为空则返 null 
        Object pollLast ();
        // 退栈出该双向队列中的第一个元素 
        Object pop ();
        // 将元素入栈进双向队列栈中
        void push (Object e );
        // 获取并删除该双向队列的第一个元素 
        Object removeFirst ();
        // 删除双向队列第一次出现的元素 e 
        Object removeFirstOccurrence (Object e );
        // 获取并删除双向队列的最后一个元素 
        removeLast();
        // 删除双向队列最后一次出现的元素 e 
        removeLastOccurrence(Object e);

LinkedList 是一个比较奇怪的类，其即实现了 List 接口又实现了 Deque 接口（Deque 是 Queue 的子接口），而 LinkedList 的实现是基于双向链表结构的，其容量没有限制，是非并发安全的队列，所以不仅可以当成列表使用，还可以当做双向队列使用，同时也可以当成栈使用（因为还实现了 pop 和 push 方法）。此外 LinkedList 的元素可以为 null 值。

ArrayDeque 是一个用数组实现的双端队列 Deque，为满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点，ArrayDeque 是非线程安全的，当多个线程同时使用的时候需要手动同步，此外该容器不允许放 null 元素，同时与 ArrayList 和 LinkedList 不同的是没有索引位置的概念，不能根据索引位置进行操作。
https://www.jianshu.com/p/d842893c4cb2

简单说说 ArrayDeque 与 LinkedList 的适用场景？

ArrayDeque 和 LinkedList 都实现了 Deque 接口，如果只需要 Deque 接口且从两端进行操作则一般来说 ArrayDeque 效率更高一些，如果同时需要根据索引位置进行操作或经常需要在中间进行插入和删除操作则应该优先选 LinkedList 效率高些，因为 ArrayDeque 实现是循环数组结构（即一个动态扩容数组，默认容量 16，然后通过一个 head 和 tail 索引记录首尾相连），而 LinkedList 是基于双向链表结构的。

https://www.jianshu.com/p/d842893c4cb2

简单说说什么是 Queue 以及 PriorityQueue 与 LinkedList 的区别及特点？

首先 Queue 是一种模拟 FIFO 队列的数据结构，新元素插入（offer）到队列的尾部，访问元素（poll）返回队列头部，一般队列不允许随机访问队列中的元素。Queue 接口主要定义了如下几个方法：

//将指定元素加入队列尾部 
        void add (Object e );
// 获取队列头部元素，但是不删除该元素，如果队列为空抛出 NoSuchElementException 异常
        Object element ();
// 将指定元素加入队列尾部（当使用有容量限制的队列时此方法比 add(Object e) 更好）
        boolean offer (Object e );
// 获取队列头部元素，但是不删除该元素，如果队列为空返回 null 
        Object peek ();
// 获取队列头部元素并删除该元素，如果队列为空则返回 null 
        Object poll ();
// 获取队列头部元素并删除该元素，如果队列为空抛出 NoSuchElementException 异常 
        Object remove ();

PriorityQueue 是一个优先级列表队列，因为 PriorityQueue 保存队列元素的顺序并不是按加入队列的顺序，而是按队列元素的大小进行重新排序，所以当调用 peek 或者 pull 方法从队列头取元素时并不是取出最先进入队列的元素，而是取出队列中最小的元素（默认顺序），所以说 PriorityQueue 实质违反了 FIFO 队列的基本原则，从而成了优先级列表实现，同时 PriorityQueue 的实现是基于动态扩容数组的二叉树堆结构，其最大容量长度为 Int 大小，是非并发安全的队列。此外 PriorityQueue 的元素不可为 null 值。

PriorityQueue 是怎么确定哪一个元素的优先级最高的？

PriorityQueue 确定最高优先级元素使用的是堆数据结构，因为堆是一棵完全树，堆中某个节点的值总是不大于或不小于其父节点值的，常见的堆有二叉堆、斐波那契堆等，二叉堆是完全二叉树或者是近似完全二叉树的一种特殊堆，其分为最大堆和最小堆，最大堆中父结点值总是大于或等于任何一个子节点值，最小堆中父结点值总是小于或等于任何一个子节点值，由于二叉堆一直是自左向右自上向下一层层填充的，所以其可以用数组来表示而不是用链表，PriorityQueue 就是采用了基于动态数组的二叉堆来确定优先级。

谈谈你对二叉堆数据结构的理解及在 PriorityQueue 中的实现？

https://www.jianshu.com/p/b308d23f3775

谈你对 ArrayDeque 主要方法实现原理的认识？

https://www.jianshu.com/p/5763d9c1c321

http://www.cnblogs.com/chengxiao/p/6059914.html
https://blog.csdn.net/qq_27093465/article/details/52269862
https://blog.csdn.net/justloveyou_/article/details/52464440
https://www.jianshu.com/p/4d3cb99d7580
https://www.jianshu.com/p/550cea8c25ef

nextTable 是新的两倍数组
ForwardingNode

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,230评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,261评论 2赞 380
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,089评论 0赞 336
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,542评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,542评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,544评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,922评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,578评论 0赞 257
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,816评论 1赞 296
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,576评论 2赞 320
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,658评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,359评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,937评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,920评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,156评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,859评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,381评论 2赞 342

面试容器

hashmap实现的数据结构，数组、桶等。

hashmap是空的情况下，map.get(a) 得到的是啥

HashMap怎么手写实现？

hashmap如何put数据（从hashmap源码角度讲解）？

Resize操作的过程。

- 简单说说 JDK1.7 中 HashMap 什么情况下会发生扩容？如何扩容？

- 简单说说 JDK1.7 中 HashMap 什么情况下会发生扩容？如何扩容？

hashmap容量为2次幂的原因。

HashMap的实现，与HashSet的区别

HashSet与HashMap怎么判断集合元素重复

简单说说 HashMap 和 LinkedHashMap 的区别

说说你对 LinkedHashSet 的理解及其与 HashSet 的关系？

HashMap是如何解决hash碰撞的？拉链法的优缺点

Hash怎么防止碰撞

hashmap的参数及影响性能的关键参数：加载因子和初始容量。

简单说说你对 HashMap 构造方法中 initialCapacity（初始容量）、loadFactor（加载因子）的理解

HashSet 和 TreeSet

HashSet、LinkedHashSet与TreeSet有什么区别，应用场景是什么？

请使用 Java 集合实现一个简约优雅的 LRU 容器

- List/Set/Map三者的区别.

简单说说你理解的 List 、Map、Set、Queue 的区别和关系

List 和 Map 的实现方式以及存储方式

List,Set,Map的区别，实现方式以及存储方式。

集合的接口和具体实现类，介绍

容器类介绍以及之间的区别

集合类相关over

Collection

2) Map

List

Set集合

map接口：

Queue

List, Set, Map是否继承自Collection接口?

Collection 和 Collections的区别

hashtable和hashmap异同。

为什么hashtable被弃用？

hashtable线程安全、synchronized加锁

concurrenthashmap的插入操作是直接操作数组中的链表吗？

concurrenthashmap相比于hashtable做的优化、segment的概念、concurrenthashmap高效的原因

SpareArray做了哪些优化？

简单说一说SpareArray的插入流程？

为什么 ArrayList 的增加或删除操作相对来说效率比较低？能简单解释下为什么吗？

ArrayList和Vector的区别 ，ArrayList与LinkedList有什么区别

- 简单说说 ArrayList 和 Vector 的区别

ArrayList和Vector的区别

ArrayList与LinkedList有什么区别

ArrayList 与 LinkedList 使用普通 for 循环遍历谁快谁慢？为什么？

Arraylist 的动态扩容机制是如何自动增加的？简单说说你理解的流程

简单说说 Array 和 ArrayList 的区别？

为什么现在都不提倡使用 Vector 了

- 为什么使用 for-each 时调用 List 的 remove 方法元素会抛出ConcurrentModificationException 异常？

什么是 Vector 和 Stack，各有什么特点？

Collections.emptyList() 与 new ArrayList() 有什么区别

容器类中fastfail的概念

CopyOnWriteArrayList的了解。

请使用 LinkedList 模拟一个堆栈或队列的数据结构

简单说说 Iterator 和 ListIterator 的区别？

为什么说集合的不同列表应该选择不同的遍历方式，举例谈谈你的认识？

并发集合了解哪些

简单说说 Comparable 和 Comparator 的区别和场景？

区别

场景

简单说说 EnumMap 的实现原理

简单谈谈你对 EnumMap 的理解及其特点与应用场景？

简单谈谈你对 EnumMap 的理解及其特点与应用场景？

简单说说 EnumMap 的实现原理

说说 EnumSet 怎么用，其基本原理是什么

简单说说什么是 Deque 以及 ArrayDeque 与 LinkedList 的区别及特点

简单说说 ArrayDeque 与 LinkedList 的适用场景？

简单说说什么是 Queue 以及 PriorityQueue 与 LinkedList 的区别及特点？

PriorityQueue 是怎么确定哪一个元素的优先级最高的？

谈谈你对二叉堆数据结构的理解及在 PriorityQueue 中的实现？

谈你对 ArrayDeque 主要方法实现原理的认识？

推荐阅读更多精彩内容

ArrayList和Vector的区别，ArrayList与LinkedList有什么区别