关于java:Java容器集合面试精选

1.1 说说汇合容器罕用的汇合类？

Java汇合框架次要包含两种类型的容器，一种是汇合（Collection），存储一个元素汇合 ，另一种是图（Map），存储键/值对映射。

• Collection汇合的子接口有Set、List、Queue三种子接口,罕用的List接口和Set接口。
• List接口次要实现类：ArrayList、LinkedList、Vector及Stack。
• Set接口的次要实现类：HashSet、TreeSet、LinkedHashSet等
• Map接口的次要实现类：HashMap、TreeMap、Hashtable、LinkedHashMap、ConcurrentHashMap以及Properties等

1.2 List，Set，Map三者的区别？List、Map、Set 三个接口存取元素时，各有什么特点？

• List：一个有序（元素存入汇合的程序和取出的程序统一）容器，元素能够反复，能够插入多个null元素，元素都有索引。
• Set：一个无序（存入和取出程序有可能不统一）容器，不能够存储反复元素，只容许存入一个null元素，必须保障元素唯一性。
• Map：是一个键值对汇合，存储键、值和之间的映射。Key无序，惟一；value 不要求有序，容许反复。

1.3 ArrayList 和 LinkedList 的区别是什么？

• 底层数据结构实现：ArrayList 底层应用的是动静数组，而 LinkedList 底层应用的是双向链表。双向链表
• 随机拜访效率：ArrayList 比 LinkedList 在随机拜访的时候效率要高，ArrayList 实现了 RandomAccess 接口，而LinkedList 是线性的数据存储形式，所以须要挪动指针从前往后顺次查找。
• 插入和删除效率：ArrayList 底层采纳数组存储，所以插入和删除元素 的工夫复杂度受元素地位的影响。 比方:执行add(E e)办法的时候， ArrayList 会默认在将指定的元素追加到此列表的开端，这种状况工夫复杂度就是O(1)。然而如果要在指定地位 i 插入和删除元素的话(add(int index, E element))工夫复杂度就为 O(n-i)。因为在进 行上述操作的时候汇合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的 操作。 LinkedList 底层采纳链表存储，所以对于add(E e)办法的插入，删除元素工夫简单 度不受元素地位的影响，近似 O(1)，如果是要在指定地位i插入和删除元素的话 add(int index, E element)工夫复杂度近似为o(n)因为须要先挪动到指定地位 再插入。
• 内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个援用，一个指向前一个元素，一个指向后一个元素。
• 线程平安：ArrayList 和 LinkedList 都是不同步的，也就是不保障线程平安。

补充内容:RandomAccess接口

public interface RandomAccess {}

查看源码咱们发现实际上 RandomAccess 接口中什么都没有定义。所以，在我看来 RandomAccess 接口不过是一个标识罢了。标识什么? 标识实现这个接口的类具备随机拜访性能。

在 binarySearch( )办法中，它要判断传入的list 是否 RamdomAccess 的实例，如果是，调用 indexedBinarySearch() 办法，如果不是，那么调用 iteratorBinarySearch() 办法

 public static <T>    int binarySearch(List<? extends Comparable<? super Tjk list, T key){if (list instanceof RandomAccess || list.size() <BINARYSEARCH_THRESHOLD)return Collections.indexedBinarySearch(list, key); else}return Collections.iteratorBinarySearch(list, key);                 

ArrayList 实现了 RandomAccess 接口， 而 LinkedList 没有实现。为什么呢?我感觉还是 和底层数据结构无关! ArrayList 底层是数组，而 LinkedList 底层是链表。数组人造反对随机 拜访，工夫复杂度为 O(1)，所以称为疾速随机拜访。链表须要遍历到特定地位能力拜访特定地位的 元素，工夫复杂度为 O(n)，所以不反对疾速随机拜访。， ArrayList 实现了 RandomAccess 接 口，就表明了他具备疾速随机拜访性能。 RandomAccess 接口只是标识，并不是说 ArrayList 实 现 RandomAccess 接口才具备疾速随机拜访性能的!

上面再总结一下 list 的遍历形式抉择:

• 实现了 RandomAccess 接口的list，优先选择一般 for 循环 ，其次 foreach。
• 未实现 RandomAccess 接口的list，优先选择iterator遍历(foreach遍历底层也是通过 iterator实现的,)，大size的数据，千万不要应用一般for循环。

1.4 ArrayList 和 Vector 的区别是什么？

• 线程平安：Vector 应用了 Synchronized 来实现线程同步，是线程平安的，而 ArrayList 是非线程平安的。
• 性能：ArrayList 在性能方面要优于 Vector。
• 扩容：ArrayList和Vector 都会依据理论的须要动静的调整容量，只不过在 Vector 扩容每次会减少 1 倍，而 ArrayList 只会减少 50%。

综上所述：

• ArrayList、Vector 底层的实现是数组， 反对随机拜访，所以适宜做查问的操作。然而Vector 中的办法因为加了 synchronized 润饰，因而 Vector 是线程平安容器，但性能上较ArrayList差。
• LinkedList 应用双向链表实现存储，按序号索引数据须要进行前向或后向遍历，但插入数据时只须要记录以后项的前后项即可，所以 LinkedList 插入速度较快。

补充阐明：为什么 ArrayList 的 elementData 加上 transient 润饰

ArrayList 中的数组定义如下：

private transient Object[] elementData;

再看一下 ArrayList 的定义：

public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

能够看到 ArrayList 实现了 Serializable 接口，这意味着 ArrayList 反对序列化。transient 的作用是说不心愿 elementData 数组被序列化，重写了 writeObject 实现：

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{    *// Write out element count, and any hidden stuff*        int expectedModCount = modCount;    s.defaultWriteObject();    *// Write out array length*        s.writeInt(elementData.length);    *// Write out all elements in the proper order.*        for (int i=0; i<size; i++)            s.writeObject(elementData[i]);    if (modCount != expectedModCount) {        throw new ConcurrentModificationException();}

每次序列化时，先调用 defaultWriteObject() 办法序列化 ArrayList 中的非 transient 元素，而后遍历 elementData，只序列化已存入的元素，这样既放慢了序列化的速度，又减小了序列化之后的文件大小。

1.5 HashSet如何查看反复？HashSet是如何保证数据不可反复的？

向HashSet 中add ()元素时，判断元素是否存在的根据，不仅要比拟hash值，同时还要联合equles 办法比拟。HashSet 中的add ()办法会应用HashMap 的put()办法。

HashMap 的 key 是惟一的，由源码能够看出 HashSet 增加进去的值就是作为HashMap 的key，并且在HashMap中如果K/V雷同时，会用新的V笼罩掉旧的V，而后返回旧的V。所以不会反复（ HashMap 比拟key是否相等是先比拟hashcode 再比拟equals ）。

以下是HashSet 局部源码：

private static final Object PRESENT = new Object();private transient HashMap<E,Object> map;public HashSet() {    map = new HashMap<>();}public boolean add(E e) {    // 调用HashMap的put办法,PRESENT是一个至始至终都雷同的虚值    return map.put(e, PRESENT)==null;}

hashCode（）与equals（）的相干规定：

• 如果两个对象相等，则hashcode肯定也是雷同的
• 两个对象相等,对两个equals办法返回true
• 两个对象有雷同的hashcode值，它们也不肯定是相等的
• 综上，equals办法被笼罩过，则hashCode办法也必须被笼罩
• hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即便这两个对象指向雷同的数据）。

深刻了解可参考：Java中hashCode() 和 equals()的问题解答

1.6 HashSet与HashMap的区别

如果你看过 HashSet 源码的话就应该晓得:HashSet 底层就是基于 HashMap 实现的。(HashSet 的 源码十分非常少，因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet 本人不得不 实现之外，其余办法都是间接调用 HashMap 中的办法。

1.7 HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底层实现

在Java中，保留数据有两种比较简单的数据结构：数组和链表。「数组的特点是：寻址容易，插入和删除艰难；链表的特点是：寻址艰难，但插入和删除容易；*所以咱们将数组和链表联合在一起，施展两者各自的劣势，应用一种叫做**拉链法」的形式能够解决哈希抵触。

JDK1.8之前

JDK1.8 之前 HashMap 底层是 数组和链表 联合在一起应用也就是 链表散列即采纳的是拉链法。拉链法：将链表和数组相结合。也就是说创立一个链表数组，数组中每一格就是一个链表。若遇到哈希抵触，则将抵触的值加到链表中即可。

jdk1.7中HashMap数据结构

JDK1.8之后

相比于之前的版本，jdk1.8在解决哈希抵触时有了较大的变动，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以缩小搜寻工夫。

jdk1.8中HashMap数据结构

JDK1.7 VS JDK1.8 比拟

JDK1.8次要解决或优化了一下问题：

• resize 扩容优化
• 引入了红黑树，目标是防止单条链表过长而影响查问效率，红黑树算法请参考
• 解决了多线程死循环问题，但仍是非线程平安的，多线程时可能会造成数据失落问题。

1.8 HashMap的put办法的具体流程？

当咱们put的时候，首先计算 key的hash值，这里调用了 hash办法，hash办法理论是让key.hashCode()与key.hashCode()>>>16进行异或操作，高16bit补0，一个数和0异或不变，所以 hash 函数大略的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目标是缩小碰撞。依照函数正文，因为bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash，如果不做 hash 解决，相当于散列失效的只有几个低 bit 位，为了缩小散列的碰撞，设计者综合思考了速度、作用、品质之后，应用高16bit和低16bit异或来简略解决缩小碰撞，而且JDK8中用了复杂度 O（logn）的树结构来晋升碰撞下的性能。

putVal办法执行流程图

public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}static final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}//实现Map.put和相干办法final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    Node<K,V>[] tab; Node<K,V> p; int n, i;    // 步骤①：tab为空则创立     // table未初始化或者长度为0，进行扩容    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    // 步骤②：计算index，并对null做解决      // (n - 1) & hash 确定元素寄存在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);        // 桶中曾经存在元素    else {        Node<K,V> e; K k;        // 步骤③：节点key存在，间接笼罩value         // 比拟桶中第一个元素(数组中的结点)的hash值相等，key相等        if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))            // 将第一个元素赋值给e，用e来记录            e = p;            // 步骤④：判断该链为红黑树             // hash值不相等，即key不相等；为红黑树结点            // 如果以后元素类型为TreeNode，示意为红黑树，putTreeVal返回待寄存的node, e可能为null        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);                    //判断链表的长度是否达到转化红黑树的临界值，临界值为8                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        //链表构造转树形构造                        treeifyBin(tab, hash);                    // 跳出循环                    break;                }                // 判断链表中结点的key值与插入的元素的key值是否相等                if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                    // 相等，跳出循环                    break;                // 用于遍历桶中的链表，与后面的e = p.next组合，能够遍历链表                p = e;            }        }        //判断以后的key曾经存在的状况下，再来一个雷同的hash值、key值时，返回新来的value这个值        if (e != null) {            // 记录e的value            V oldValue = e.value;            // onlyIfAbsent为false或者旧值为null            if (!onlyIfAbsent || oldValue == null)                //用新值替换旧值                e.value = value;            // 拜访后回调            afterNodeAccess(e);            // 返回旧值            return oldValue;        }    }    // 结构性批改    ++modCount;    // 步骤⑥：超过最大容量就扩容     // 理论大小大于阈值则扩容    if (++size > threshold)        resize();    // 插入后回调    afterNodeInsertion(evict);    return null;}

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②.依据键值key计算hash值得到插入的数组索引i，如果table[i]==null，间接新建节点增加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果雷同间接笼罩value，否则转向④，这里的雷同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则间接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key曾经存在间接笼罩value即可；

⑥.插入胜利后，判断理论存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

1.9 HashMap的扩容操作是怎么实现的？

①.在jdk1.8中，resize办法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize办法进行扩容；

②.每次扩大的时候，都是扩大2倍；

③.扩大后Node对象的地位要么在原地位，要么挪动到原偏移量两倍的地位。

在putVal()中，咱们看到在这个函数外面应用到了2次resize()办法，resize()办法示意的在进行第一次初始化时会对其进行扩容，或者当该数组的理论大小大于其临界值值(第一次为12),这个时候在扩容的同时也会随同的桶下面的元素进行从新散发，这也是JDK1.8版本的一个优化的中央，在1.7中，扩容之后须要从新去计算其Hash值，依据Hash值对其进行散发，但在1.8版本中，则是依据在同一个桶的地位中进行判断(e.hash & oldCap)是否为0，从新进行hash调配后，该元素的地位要么停留在原始地位，要么挪动到原始地位+减少的数组大小这个地位上

final Node<K,V>[] resize() {    Node<K,V>[] oldTab = table;//oldTab指向hash桶数组    int oldCap = (oldTab == null) ? 0 : oldTab.length;    int oldThr = threshold;    int newCap, newThr = 0;    if (oldCap > 0) {//如果oldCap不为空的话，就是hash桶数组不为空        if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了，就赋值为整数最大的阀值            threshold = Integer.MAX_VALUE;            return oldTab;//返回        }//如果以后hash桶数组的长度在扩容后依然小于最大容量 并且oldCap大于默认值16        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                oldCap >= DEFAULT_INITIAL_CAPACITY)            newThr = oldThr << 1; // double threshold 双倍扩容阀值threshold    }    // 旧的容量为0，但threshold大于零，代表有参结构有cap传入，threshold曾经被初始化成最小2的n次幂    // 间接将该值赋给新的容量    else if (oldThr > 0) // initial capacity was placed in threshold        newCap = oldThr;        // 无参结构创立的map，给出默认容量和threshold 16, 16*0.75    else {               // zero initial threshold signifies using defaults        newCap = DEFAULT_INITIAL_CAPACITY;        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);    }    // 新的threshold = 新的cap * 0.75    if (newThr == 0) {        float ft = (float)newCap * loadFactor;        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                (int)ft : Integer.MAX_VALUE);    }    threshold = newThr;    // 计算出新的数组长度后赋给以后成员变量table    @SuppressWarnings({"rawtypes","unchecked"})    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶数组    table = newTab;//将新数组的值复制给旧的hash桶数组    // 如果原先的数组没有初始化，那么resize的初始化工作到此结束，否则进入扩容元素重排逻辑，使其平均的扩散    if (oldTab != null) {        // 遍历新数组的所有桶下标        for (int j = 0; j < oldCap; ++j) {            Node<K,V> e;            if ((e = oldTab[j]) != null) {                // 旧数组的桶下标赋给长期变量e，并且解除旧数组中的援用，否则就数组无奈被GC回收                oldTab[j] = null;                // 如果e.next==null，代表桶中就一个元素，不存在链表或者红黑树                if (e.next == null)                    // 用同样的hash映射算法把该元素退出新的数组                    newTab[e.hash & (newCap - 1)] = e;                    // 如果e是TreeNode并且e.next!=null，那么解决树中元素的重排                else if (e instanceof TreeNode)                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);                    // e是链表的头并且e.next!=null，那么解决链表中元素重排                else { // preserve order                    // loHead,loTail 代表扩容后不必变换下标，见注1                    Node<K,V> loHead = null, loTail = null;                    // hiHead,hiTail 代表扩容后变换下标，见注1                    Node<K,V> hiHead = null, hiTail = null;                    Node<K,V> next;                    // 遍历链表                    do {                        next = e.next;                        if ((e.hash & oldCap) == 0) {                            if (loTail == null)                                // 初始化head指向链表以后元素e，e不肯定是链表的第一个元素，初始化后loHead                                // 代表下标放弃不变的链表的头元素                                loHead = e;                            else                                // loTail.next指向以后e                                loTail.next = e;                            // loTail指向以后的元素e                            // 初始化后，loTail和loHead指向雷同的内存，所以当loTail.next指向下一个元素时，                            // 底层数组中的元素的next援用也相应发生变化，造成lowHead.next.next.....                            // 追随loTail同步，使得lowHead能够链接到所有属于该链表的元素。                            loTail = e;                        }                        else {                            if (hiTail == null)                                // 初始化head指向链表以后元素e, 初始化后hiHead代表下标更改的链表头元素                                hiHead = e;                            else                                hiTail.next = e;                            hiTail = e;                        }                    } while ((e = next) != null);                    // 遍历完结, 将tail指向null，并把链表头放入新数组的相应下标，造成新的映射。                    if (loTail != null) {                        loTail.next = null;                        newTab[j] = loHead;                    }                    if (hiTail != null) {                        hiTail.next = null;                        newTab[j + oldCap] = hiHead;                    }                }            }        }    }    return newTab;}

1.10 HashMap是怎么解决哈希抵触的？

什么是哈希？

Hash，个别翻译为“散列”，也有间接音译为“哈希”的，这就是把任意长度的输出通过散列算法，变换成固定长度的输入，该输入就是散列值（哈希值）；这种转换是一种压缩映射，也就是，散列值的空间通常远小于输出的空间，不同的输出可能会散列成雷同的输入，所以不可能从散列值来惟一的确定输出值。简略的说就是一种将任意长度的消息压缩到某一固定长度的音讯摘要的函数。

所有散列函数都有如下一个根本个性：依据同一散列函数计算出的散列值如果不同，那么输出值必定也不同。然而，依据同一散列函数计算出的散列值如果雷同，输出值不肯定雷同。

什么是哈希抵触？

当两个不同的输出值，依据同一散列函数计算出雷同的散列值的景象，咱们就把它叫做碰撞（哈希碰撞）。

这样咱们就能够将领有雷同哈希值的对象组织成一个链表放在hash值所对应的bucket下，但相比于hashCode返回的int类型，咱们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要远小于int类型的范畴，所以咱们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最坏状况下还会将HashMap变成一个单链表，所以咱们还须要对hashCode作肯定的优化。

hash()函数

下面提到的问题，次要是因为如果应用hashCode取余，那么相当于参加运算的只有hashCode的低位，高位是没有起到任何作用的，所以咱们的思路就是让hashCode取值出的高位也参加运算，进一步升高hash碰撞的概率，使得数据分布更均匀，咱们把这样的操作称为扰动，在JDK 1.8中的hash()函数如下：

static final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与本人右移16位进行异或运算（高下位异或）}

这比在JDK 1.7中，更为简洁，相比在1.7中的4次位运算，5次异或运算（9次扰动），在1.8中，只进行了1次位运算和1次异或运算（2次扰动）；

「JDK1.8新增红黑树」

通过下面的链地址法（应用散列表）和扰动函数咱们胜利让咱们的数据分布更均匀，哈希碰撞缩小，然而当咱们的HashMap中存在大量数据时，退出咱们某个bucket下对应的链表有n个元素，那么遍历工夫复杂度就为O(n)，为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使得遍历复杂度升高至O(logn)；总结 简略总结一下HashMap是应用了哪些办法来无效解决哈希抵触的：

• 应用链地址法（应用散列表）来链接领有雷同hash值的数据；
• 应用2次扰动函数（hash函数）来升高哈希抵触的概率，使得数据分布更均匀；
• 引入红黑树进一步升高遍历的工夫复杂度，使得遍历更快；

1.11 HashMap为什么不间接应用hashCode()解决后的哈希值间接作为table的下标？

答：hashCode()办法返回的是int整数类型，其范畴为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空间，而HashMap的容量范畴是在16（初始化默认值）~2 ^ 30，HashMap通常状况下是取不到最大值的，并且设施上也难以提供这么多的存储空间，从而导致通过hashCode()计算出的哈希值可能不在数组大小范畴内，进而无奈匹配存储地位；

那怎么解决呢？

• HashMap本人实现了本人的hash()办法，通过两次扰动使得它本人的哈希值高下位自行进行异或运算，升高哈希碰撞概率也使得数据分布更均匀；
• 在保障数组长度为2的幂次方的时候，应用hash()运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的形式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范畴不匹配”的问题；

1.12 HashMap 的长度为什么是2的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据调配平均，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

这个算法应该如何设计呢？

咱们首先可能会想到采纳%取余的操作来实现。然而，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采纳二进制位操作 &，绝对于%可能进步运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

那为什么是两次扰动呢？

答：这样就是加大哈希值低位的随s机性，使得散布更平均，从而进步对应数组存储下标地位的随机性&平均性，最终缩小Hash抵触，两次就够了，曾经达到了高位低位同时参加运算的目标；

1.13 HashMap 与 HashTable 有什么区别？

• 线程平安：HashMap 是非线程平安的，HashTable 是线程平安的；HashTable 外部的办法根本都通过 synchronized 润饰。（多线程能够应用 ConcurrentHashMap 吧！）；
• 效率：因为线程平安的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 根本被淘汰，不要在代码中应用它；对Null key 和Null value的反对：HashMap 中，null 能够作为键，这样的键只有一个，能够有一个或多个键所对应的值为 null。然而在 HashTable 中 put 进的键值只有有一个 null，间接抛NullPointerException。
• 初始容量大小和每次裁减容量大小的不同 ：①创立时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次裁减，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次裁减，容量变为原来的2倍。②创立时如果给定了容量初始值，那么 Hashtable 会间接应用你给定的大小，而 HashMap 会将其裁减为2的幂次方大小。也就是说 HashMap 总是应用2的幂作为哈希表的大小。底层数据结构：JDK1.8 当前的 HashMap 在解决哈希抵触时有了较大的变动，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以缩小搜寻工夫。Hashtable 没有这样的机制。

1.14 HashMap 和 ConcurrentHashMap 的区别

• ConcurrentHashMap对整个桶数组进行了宰割分段(Segment)，而后在每一个分段上都用lock锁进行爱护，绝对于HashTable的synchronized锁的粒度更精密了一些，并发性能更好，而HashMap没有锁机制，不是线程平安的。（JDK1.8之后ConcurrentHashMap启用了一种全新的形式实现,利用CAS算法。）
• HashMap的键值对容许有null，然而ConCurrentHashMap都不容许。

1.15 ConcurrentHashMap 和 Hashtable 的区别？

ConcurrentHashMap 和 Hashtable 的区别次要体现在实现线程平安的形式上不同。

• 「底层数据结构」：JDK1.7的 ConcurrentHashMap 底层采纳 分段的数组+链表 实现，JDK1.8 采纳的数据结构跟HashMap1.8的构造一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构相似都是采纳 数组+链表 的模式，数组是 HashMap 的主体，链表则是次要为了解决哈希抵触而存在的；
• 「实现线程平安的形式」（重要）：① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了宰割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程拜访容器里不同数据段的数据，就不会存在锁竞争，进步并发访问率。（默认调配16个Segment，比Hashtable效率进步16倍。） 到了 JDK1.8 的时候曾经摒弃了Segment的概念，而是间接用 Node 数组+链表+红黑树的数据结构来实现，并发管制应用 synchronized 和 CAS 来操作。（JDK1.6当前 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程平安的 HashMap，尽管在JDK1.8中还能看到 Segment 的数据结构，然而曾经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :应用 synchronized 来保障线程平安，效率十分低下。当一个线程拜访同步办法时，其余线程也拜访同步办法，可能会进入阻塞或轮询状态，如应用 put 增加元素，另一个线程不能应用 put 增加元素，也不能应用 get，竞争会越来越强烈效率越低。

「两者的比照图」：

HashTable:

JDK1.7的ConcurrentHashMap：

JDK1.8的ConcurrentHashMap（TreeBin: 红黑二叉树节点 Node: 链表节点）：

答：ConcurrentHashMap 联合了 HashMap 和 HashTable 二者的劣势。HashMap 没有思考同步，HashTable 思考了同步的问题。然而 HashTable 在每次同步执行时都要锁住整个构造。ConcurrentHashMap 锁的形式是略微细粒度的。

1.16 ConcurrentHashMap 底层具体实现晓得吗？实现原理是什么？

JDK1.7

首先将数据分为一段一段的存储，而后给每一段数据配一把锁，当一个线程占用锁拜访其中一个段数据时，其余段的数据也能被其余线程拜访。

在JDK1.7中，ConcurrentHashMap采纳Segment + HashEntry的形式进行实现，构造如下：

一个 ConcurrentHashMap 里蕴含一个 Segment 数组。Segment 的构造和HashMap相似，是一种数组和链表构造，一个 Segment 蕴含一个 HashEntry 数组，每个 HashEntry 是一个链表构造的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行批改时，必须首先取得对应的 Segment的锁。

• 该类蕴含两个动态外部类 HashEntry 和 Segment ；前者用来封装映射表的键值对，后者用来充当锁的角色；
• Segment 是一种可重入的锁 ReentrantLock，每个 Segment 守护一个HashEntry 数组里得元素，当对 HashEntry 数组的数据进行批改时，必须首先取得对应的 Segment 锁。

JDK1.8

在JDK1.8中，放弃了Segment臃肿的设计，取而代之的是采纳Node + CAS + Synchronized来保障并发平安进行实现，synchronized只锁定以后链表或红黑二叉树的首节点，这样只有hash不抵触，就不会产生并发，效率又晋升N倍。

构造如下：

1.17Array 和 ArrayList 有何区别？

• Array 能够存储根本数据类型和对象，ArrayList 只能存储对象。
• Array 是指定固定大小的，而 ArrayList 大小是主动扩大的。
• Array 内置办法没有 ArrayList 多，比方 addAll、removeAll、iteration 等办法只有 ArrayList 有。

对于根本类型数据，汇合应用主动装箱来缩小编码工作量。然而，当解决固定大小的根本数据类型的时候，这种形式绝对比较慢。

1.18 如何实现 Array 和 List 之间的转换？

• Array 转 List：Arrays. asList(array) ；
• List 转 Array：List 的 toArray() 办法。

1.19 comparable 和 comparator的区别？

• comparable接口实际上是出自java.lang包，它有一个 compareTo(Object obj)办法用来排序
• comparator接口实际上是出自 java.util 包，它有一个compare(Object obj1, Object obj2)办法用来排序

个别咱们须要对一个汇合应用自定义排序时，咱们就要重写compareTo办法或compare办法，当咱们须要对某一个汇合实现两种排序形式，比方一个song对象中的歌名和歌手名别离采纳一种排序办法的话，咱们能够重写compareTo办法和应用自制的Comparator办法或者以两个Comparator来实现歌名排序和歌星名排序，第二种代表咱们只能应用两个参数版的Collections.sort()。

Comparator定制排序

ArrayList<Integer> arrayList = new ArrayList<Integer>(); arrayList.add(-1);arrayList.add(3);arrayList.add(3);arrayList.add(-5);arrayList.add(7);arrayList.add(4);arrayList.add(-9);arrayList.add(-7);System.out.println("原始数组:"); System.out.println(arrayList);// void reverse(List list):反转 Collections.reverse(arrayList); System.out.println("Collections.reverse(arrayList):"); System.out.println(arrayList);// void sort(List list),按天然排序的升序排序 Collections.sort(arrayList); System.out.println("Collections.sort(arrayList):"); System.out.println(arrayList);// 定制排序的用法Collections.sort(arrayList, new Comparator<Integer>() {        @Override        public int compare(Integer o1, Integer o2) { return o2.compareTo(o1);        } });System.out.println("定制排序后:"); System.out.println(arrayList);

原始数组:[-1, 3, 3, -5, 7, 4, -9, -7]Collections.reverse(arrayList):[-7, -9, 4, 7, -5, 3, 3, -1] Collections.sort(arrayList): [-9, -7, -5, -1, 3, 3, 4, 7] 定制排序后:[7, 4, 3, 3, -1, -5, -7, -9]

重写compareTo办法实现按年龄来排序

 // person对象没有实现Comparable接口，所以必须实现，这样才不会出错，才可 以使treemap中的数据按顺序排列// 后面一个例子的String类曾经默认实现了Comparable接口，具体能够查看 String类的API文档，另外其余// 像Integer类等都曾经实现了Comparable接口，所以不须要另外实现了public  class Person implements Comparable<Person> {    private String name;    private int age;    public Person(String name, int age) {        super();        this.name = name;        this.age = age;    }    public String getName() {        return name;    }    public void setName(String name) { this.name = name;    }    public int getAge() {        return age;    }    public void setAge(int age) { this.age = age;    }    /**     * TODO重写compareTo办法实现按年龄来排序     */    @Override    public int compareTo(Person o) {              if (this.age > o.getAge()) {          return 1;       } else if (this.age < o.getAge()) {          return -1;        }        return age;     }}

public static void main(String[] args) {        TreeMap<Person, String> pdata = new TreeMap<Person, String>(); pdata.put(new Person("张三", 30), "zhangsan");        pdata.put(new Person("李四", 20), "lisi");        pdata.put(new Person("王五", 10), "wangwu");        pdata.put(new Person("小红", 5), "xiaohong");// 失去key的值的同时失去key所对应的值        Set<Person> keys = pdata.keySet();        for (Person key : keys) {        System.out.println(key.getAge() + "-" + key.getName()); }}

5-小红 10-王五 20-李四 30-张三

1.20 Collection 和 Collections 有什么区别？

• java.util.Collection 是一个汇合接口（汇合类的一个顶级接口）。它提供了对汇合对象进行基本操作的通用接口办法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的汇合提供了最大化的对立操作形式，其间接继承接口有List与Set。
• Collections则是汇合类的一个工具类/帮忙类，其中提供了一系列静态方法，用于对汇合中元素进行排序、搜寻以及线程平安等各种操作。

1.21 TreeMap 和 TreeSet 在排序时如何比拟元素？Collections 工具类中的 sort()办法如何比拟元素？

TreeSet 要求寄存的对象所属的类必须实现 Comparable 接口，该接口提供了比拟元素的 compareTo()办法，当插入元素时会回调该办法比拟元素的大小。TreeMap 要求寄存的键值对映射的键必须实现 Comparable 接口从而依据键对元素进 行排 序。

Collections 工具类的 sort 办法有两种重载的模式，

第一种要求传入的待排序容器中寄存的对象比拟实现 Comparable 接口以实现元素的比拟；

第二种不强制性的要求容器中的元素必须可比拟，然而要求传入第二个参数，参数是Comparator 接口的子类型（须要重写 compare 办法实现元素的比拟），相当于一个长期定义的排序规定，其实就是通过接口注入比拟元素大小的算法，也是对回调模式的利用（Java 中对函数式编程的反对）。

文章参考：

Java 8系列之重新认识HashMap

Java汇合容器面试题

看到这里明天的分享就完结了，如果感觉这篇文章还不错，来个分享、点赞、在看三连吧，让更多的人也看到～

欢送关注集体公众号 「JavaClub」，定期为你分享一些面试干货。