跳至主要內容

java集合

HeChuangJun约 7917 字大约 26 分钟

1. 集合继承结构

  • Collection，主要由 List、Set、Queue 组成
    • List：存储的元素有序，可重复。动态数组的 ArrayList 和封装了链表的 LinkedList；
    • Set：存储的元素无序，不可重复。HashSet 和 TreeSet；
    • Queue：队列。双端队列 ArrayDeque，以及优先级队列 PriorityQueue。
  • Map，键值对集合。HashMap。键不能重复，每个键只能对应一个值。HashMap、LinkedHashMap、TreeMap

collection.png
map.png

2. 简单介绍一下队列 Queue

  • Java队列主要通过 java.util.Queue 接口和 java.util.concurrent.BlockingQueue 两个接口来实现。
  • PriorityQueue 是一个基于优先级堆的无界队列，它的元素按照自然顺序排序或者 Comparator 进行排序。
  • ArrayDeque 是一个基于数组的双端队列，可以在两端插入和删除元素。
  • LinkedList既可以当作 List 使用，也可以当作 Queue 使用。
  • BlockingQueue 线程安全的队列，还添加了等待/通知机制，以便在队列为空时阻塞获取元素的线程，直到队列变得可用，或者在队列满时阻塞插入元素的线程，直到队列变得可用。被广泛用于“生产者-消费者”问题中，其原因是 BlockingQueue 提供了可阻塞的插入和移除方法。当队列容器已满，生产者线程会被阻塞，直到队列未满；当队列容器为空时，消费者线程会被阻塞，直至队列非空时为止。
  • BlockingQueue 接口的实现类有 ArrayBlockingQueue、DelayQueue、LinkedBlockingDeque、LinkedBlockingQueue、LinkedTransferQueue、PriorityBlockingQueue、SynchronousQueue 等。
  • 阻塞指的是一种程序执行状态，其中某个线程在等待某个条件满足时暂停其执行（即阻塞），直到条件满足时恢复其执行。

3. 阻塞队列是如何实现的？

  • ArrayBlockingQueue是一个基于数组的有界阻塞队列，采用 ReentrantLock 锁来实现线程的互斥，而 ReentrantLock 底层采用的是 AQS 实现的队列同步，线程的阻塞调用 LockSupport.park 实现，唤醒调用 LockSupport.unpark 实现。

4. 队列和栈的区别

  • 队列是一种先进先出（FIFO, First-In-First-Out）的数据结构。在队列中，第一个加入队列的元素会是第一个被移除的。队列常用于处理按顺序来的任务。
  • 栈是一种后进先出（LIFO, Last-In-First-Out）的数据结构。在这种结构中，最后一个加入栈的元素会是第一个被移除的。这种特性使得栈非常适合于那些需要访问最新添加的数据元素的场合。

5. ArrayList和LinkedList区别？√

  • ArrayList基于数组实现，LinkedList基于双向链表实现
  • ArrayList查找快(数组下标查找)，增删慢(需要复制数组和移动元素)，适合顺序添加、随机访问场景；LinkedList查找慢(移动指针从前往后依次查找)、增删快(改变前后驱节点指向)适合多次增加删除修改场景
  • ArrayList支持随机访问，可通过下标直接获取元素，实现了RandmoAccess接口，LinkedList不支持，没有实现RandmoAccess接口
  • ArrayList基于数组，是一块连续的内存空间，扩容后空间是原来的1.5倍，可能会有空的内存空间，存在一定空间浪费，LinkedList基于链表，内存空间不连续，每个节点需要存储前驱和后继，所以会占用更多的空间

6. ArrayList扩容机制？

  • ArrayList基于数组实现，数组的容量是在定义的时候确定的，在插入时候，会先检查是否需要扩容，如果当前容量+1超过数组长度，就会进行扩容
  • 扩容是创建一个1.5倍的新数组，然后把原数组的值拷贝过去
  • 初始容量10，初始化指定容量会提升性能

7. ArrayList怎么序列化?为什么用transient修饰数组?

  • ArrayList通过两个流ObjectOutputStream和ObjectInputStream的两个方法readObject、writeObject进行序列化和反序列化。json序列化也可以
  • 因为ArrayList的数组中有部分数据是null存在内存浪费，同时减少不必要序列化和反序列化，ArrayList使用transient修饰存储元素的elementData的数组，使之不被序列化。

8. 并发修改异常和集合的快速失败(fail-fast)?

  • 快速失败(fail—fast)：Java 集合的一种错误检测机制，在用迭代器遍历一个集合对象时，如果线程A遍历过程中，线程B对集合对象的内容进行了修改（增加、删除、修改），则会抛出ConcurrentModificationException
  • 原理：迭代器在遍历时使用一个modCount变量。遍历开始时赋值给expectedmodCount，集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用 hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为 expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
  • 场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），如ArrayList
  • 解决方法：多线程下所有涉及到改变modCount值得地方全部加上synchronized。使用CopyOnWriteArrayList来替换ArrayList
  • 如何删除元素
    • 使用Iterator，顺序向下，如果找到元素使用remove方法移除
    • 倒序遍历List，如果找到元素使用remove方法移除

9. 安全失败(fail-safe)?

  • 采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历
  • 原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发ConcurrentModificationException
  • 缺点：基于拷贝内容的优点是避免了ConcurrentModificationException，但迭代器并不能访问到修改后的内容
  • 场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发修改，如CopyOnWriteArrayList

10. 如何保证ArrayList线程安全?

  • 使用Collections.synchronizedList包装ArrayList，然后操作包装后的list。
  • 使用CopyOnWriteArrayList代替ArrayList。
  • 使用ArrayList时通过同步机制去控制ArrayList读写。

11. CopyOnWriteArrayList？

  • 线程安全版本的 ArrayList。采用读写分离的并发策略。允许并发读，读操作是无锁的，性能高。写操作首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。

12. hashMap的实现原理/底层数据结构?

hashmapstructure.png
hashmapstructure.png
  • jdk1.8的数据结构是Node数组+链表+红黑树，
  • HashMap的Node数组用于存储键值对,当向 HashMap 中添加一个键值对时，会使用哈希函数计算键的哈希码，确定其在数组中的位置，当多个键经哈希处理后得到相同的索引时，会发生哈希冲突，如果键已经存在，其对应的值将被新值覆盖。否则新元素将被添加到链表的末尾。为了提升查询性能。当链表上的元素个数超过8个且数组大小>=64时，链表转化成红黑树，节点变成树节点，红黑树的查询效率是 O(logN)，比链表的 O(n) 要快。数组的查询效率是 O(1)。但是当红黑树节点个数小于6时转为链表；当从 HashMap 中获取元素时，也会使用哈希函数计算键的位置，然后根据位置在数组、链表或者红黑树中查找元素。
  • HashMap 的初始容量是 16，随着元素的不断添加，HashMap 的容量（数组大小）可能不足，需要进行扩容，阈值是capacity * loadFactor，capacity 为容量，loadFactor 为负载因子，默认为 0.75。扩容后的数组大小是原来的 2 倍，然后把原来的元素重新计算哈希值，放到新的数组中

13. 为什么使用红黑树而不使用二叉树或者平衡树呢？

mangrove.png
mangrove.png
  • 红黑树一种自平衡的二叉查找树：
    • 每个节点要么是红色，要么是黑色；
    • 根节点永远是黑色的；
    • 所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；
    • 每个红色节点的两个子节点一定都是黑色；
    • 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
  • 不用二叉树原因：二叉树容易出现极端情况，比如插入的数据是有序的，那么二叉树就会退化成链表，查询效率就会变成 O(n)。
  • 不用平衡二叉树原因：平衡二叉树插入和删除数据时，为了保持保持平衡需要旋转的次数更多，保持平衡效率比红黑树低

14. 红黑树怎么保持平衡？

  • 红黑树有两种方式保持平衡：旋转(分为左旋和右旋)和染色。
    levorotation.png
    dextrorotation.png
    dye.png

15. hashMap的put方法执行过程?

put.jpg
put.jpg
  • 1.通过 hash 方法计算 key 的哈希值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • 2.判断tab是否为空或者长度为0，如果是则进行扩容操作。
if ((tab = table) == null || (n = tab.length) == 0) 
  n = (tab = resize()).length;
  • 3.根据哈希值计算下标，如果数组对应下标正好没有存放数据，则直接插入，
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  • 4.如果对应下标已经有数据了，就需要判断是否为相同的key，是则覆盖 value，否则需要判断是否为树节点，是则向树中插入节点，否则向链表中插入数据。在链表中插入节点的时候，如果链表长度大于等于 8或者数组长度>=64，则需要把链表转换为红黑树。
else {
    Node<K,V> e; K k;
    //
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    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;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
}
  • 5.最后所有元素处理完成后，判断是否超过阈值；threshold，超过则扩容。然后rehash原数组
if (++size > threshold)
    resize();

16. 只重写 equals 没重写 hashcode，map put 的时候会发生什么?

  • 会导致 equals 相等的两个对象，hashcode 不相等，这样的话，这两个对象会被放到不同的桶中，这样就会导致 get 的时候，找不到对应的值。

17. HashMap的get方法执行过程?

get.png
get.png
  • 使用扰动函数，获取新的哈希值
  • 计算数组下标，获取节点
  • 当前节点和 key 匹配，直接返回
  • 否则，当前节点是否为树节点，查找红黑树
  • 否则，遍历链表查找

18. hashMap计算hash的方法？为什么这么设计？

  • hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) key的hashCode低16位与高16位异或
  • 降低降低hash碰撞的概率，让hashCode取值出的高位参与运算，使得数据分布更平均的操作
  • 高频操作采用位运算，算法高效

19. 为什么哈希函数能降低hash碰撞？

  • 因为高16位与低16位亦或能增加低位的随机性，减少碰撞。（在计算元素位置时把散列值和数组长度-1做与操作。同时因为数组长度为2的整数幂，数组长度-1相当于低位掩码。与操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是0000 0000 0000 0000 0000 0000 0000 1111。和某个散列值做与操作结果就是截取了最低的四位值。就算散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。如果散列本身做得不好，分布上成等差数列的漏洞，如果正好让最后几个低位呈现规律性重复，那就容易碰撞了。右移16位，32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，高位的信息也被变相保留下来）
    hash.jpg

20. hashMap计算数组的位置？为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？

  • i = (length - 1) & hash 求出hash与数组长度-1进行与(&)操作（结果就是散列值的高位全部归零，只保留低位值）
  • 原因1当数组长度为2的幂次方时，h&(length-1)等价于h%length取模,比取余操作更加有效率
  • 原因2通过取模操作解决了“哈希值与数组大小范围不匹配”的问题；key.hashCode()返回int类型范围-(2 ^ 31)~(2 ^ 31 - 1)，约40亿。而HashMap的容量范围是在16（默认初始值）~2 ^ 30，内存放不下

21. HashMap的size为什么必须是2的整数次方？

  • 充分利用数组空间，让数据更均匀分布，减少hash冲突，如果length不是2的次幂，比如15，则length–1=14，二进制为 1110，再与h与操作，最后一位都为0，而 0001，0011，0101，1001，1011，0111，1101这几个位置不能存放元素了，此时数组可用位置比数组长度少，增加了碰撞的几率，减慢了查询的效率。
  • 当size为2的n次方时，h & (length – 1) 等价于h%length取模，位运算速度快
  • 在扩容迁移的时候不需要再重新通过哈希定位新的位置了。因为每次扩容都是翻倍，与 (n-1)&hash原位置相比，只是多了一个bit位。使得扩容后的位置=原位置 or 原位置 + 旧容量

22. 如果初始化HashMap传17作为初始容量会怎么处理？

  • 初始化时不是2的倍数时，HashMap会将值转化为大于该值的最小的2次幂，所以传入17时HashMap的实际容量是32。
//MAXIMUM_CAPACITY = 1 << 30这个是临界范围，即最⼤的Map集合
//或运算主要是为了把⼆进制的各个位置都填上1，当⼆进制的各个位置都是1以后，就是标准的2的倍数减1了，最后把结果加1再返回即可
static final int tableSizeFor(int cap) {
 int n = cap - 1;
 n |= n >>> 1;
 n |= n >>> 2;
 n |= n >>> 4;
 n |= n >>> 8;
 n |= n >>> 16;
 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
hashmaptablesize.png
hashmaptablesize.png

23. 初始化 HashMap 的时候需要传入容量值吗？

  • 在创建 HashMap 时可以指定初始容量值。这个容量是指 Map 内部用于存储数据的数组大小。
  • 如果预先知道 Map 将存储大量键值对，提前指定一个足够大的初始容量可以减少因扩容导致的重哈希（rehashing）操作，从而提高性能。因为每次扩容时，HashMap 需要新分配一个更大的数组并重新将现有的元素插入到这个新数组中，这个过程相对耗时，尤其是当 Map 中已有大量数据时。
  • 过大的初始容量会浪费内存，特别是当实际存储的元素远少于初始容量时。如果不指定初始容量，则默认的初始容量 16。

24. 有什么哈希函数的构造方法呢？

  • HashMap里哈希构造函数的方法叫除留取余法：H(key)=key%p(p<=N)，关键字除以一个不大于哈希表长度的正整数p，所得余数为地址
  • 直接定址法：直接根据key来映射到对应的数组位置，例如 1232 放到下标 1232 的位置。
  • 数字分析法：取key的某些数字（例如十位和百位）作为映射的位置
  • 平方取中法：取key平方的中间几位作为映射的位置
  • 折叠法：将key分割成位数相同的几段，然后把它们的叠加和作为映射的位置

25. hashMap使用了什么方法解决Hash冲突？

  • 链地址法（使用散列表）链接相同hash值的数据
  • 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均
  • 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；

26. 解决哈希冲突有哪些方法？

  • 再哈希法：两套哈希算法，当发生哈希冲突的时候，使用另外一种哈希算法，直到找到空槽为止。设计要求高
  • 开放地址法：遇到哈希冲突的时候，就去寻找下一个空的槽。有 3 种方法：
    • 线性探测：从冲突的位置开始，依次往后找，直到找到空槽。
    • 二次探测：从冲突的位置 x 开始，第一次增加 1^2个位置，第二次增加 2^2，直到找到空槽。
    • 双重哈希：准备多个哈希函数，发生冲突的时候，使用另外一个哈希函数。
  • 链地址法，当发生哈希冲突的时候，使用链表将冲突的元素串起来。HashMap 采用的正是拉链法。

27. 怎么判断key相等呢？

  • 依赖于key的equals()方法和hashCode()方法，以及 == 运算符。
    • hashCode()：计算key的哈希码。由于不同的key可能有相同的哈希码，hashCode()只是第一步筛选。
    • equals()：当两个key的哈希码相同时，再用key的equals()方法精确比较。只有返回true时，两个key才完全相同
    • ==：如果两个key的引用指向同一个对象，那么hashCode()和equals()方法都会返回true，所以equals判断前使用==运算符判断
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))

28. 为什么桶里面的链表要转红黑树？为什么不直接使用红黑树？链表转换为红黑树阈值是8？红黑树转链表阈值是6?

  • 红黑树节点的大小大概是普通节点大小的两倍，所以转红黑树牺牲了空间换时间，是一种兜底策略，保证极端情况下的查找效率
  • 因为当负载因子是0.75服从泊松分布，当单个桶内的元素达到8个时的概率小于千万分之一，几乎不可能，更印证了转红黑树只是兜底策略
  • 因为如果这个阈值也设置成8，假如发生碰撞，节点增减刚好在8附近，会发生链表和红黑树的不断转换，导致资源浪费。

29. hash冲突后，将元素放到链表头还是尾？√

  • JDK1.7插入时采用头插法，多线程下，有链表闭环的bug。假设链表原来的元素是元素的顺序是C->B->A，此时线程1和2指向指向C，线程1和2.next指向B，当hashMap扩容并且线程2完成插入，此时链表的状态为A->B->C，此时线程1指向C，线程1.next指向B，此时线程1想要变量就变成C->B->C了，因为此时B.next->C
  • JDK1.8改成了尾插法，主要是为了减少线程安全的问题，转成红黑树后按照红黑树的规则来插了

30. HashMap哪些操作会导致扩容？ 扩容机制？resize方法的执行过程？扩容后的位置计算？为什么负载因子是0.75?

  • 为了减少哈希冲突发生的概率，当HashMap元素个数达到一个临界值threshold的时候，就会触发扩容，是一个相当耗时的操作。
  • 扩容时机
    • 第一次调用HashMap的put方法且数组为null时，会调用resize方法对table数组进行初始化，默认大小为16。
    • 当hashMap元素个数大于扩容阈值threshold = 负载因子loadFactor(0.75) * 初始容量capacity(16)时。容量变为原来的2倍，先插入数据再扩容
  • 容量范围：16-2^30个
  • 加载因子过高，扩容频率变低，hash碰撞几率变大，查找时间长，但占用空间小，空间利用率变高
  • 加载因子过低，扩容频率变高，hash碰撞几率变低，查找时间短，但占用空间大，空间利用率变低
  • 扩容机制：扩容时，HashMap 会创建一个新的数组，其容量是原数组容量的两倍。然后将键值对放到新计算出的索引位置上。根据(e.hash & oldCap)是否为0，使得扩容后的位置=原位置 or 原位置 + 旧容量（原哈希值的高位中新增的那一位是否为1，因为位置计算实际上是保留低位值，去掉所有高位值，比如原容量16则保留4位低位，扩容后32为保留5位低位，相差1位，而这1位刚好是原容量16所在的位置，因此只需hash与原容量与操作得到最新的位是1还是0决定新元素的位置，上面的推论都得益于长度是2的倍数和hash的高低位运算）

31. jdk1.8 对 HashMap 主要做了哪些优化呢？为什么？

  • 数据结构：数组+链表改成了数组+链表或红黑树 原因：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由O(n)降为O(logn)
  • 链表插入方式：链表的插入方式从头插法改成了尾插法 原因：因为头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环
  • 扩容rehash：1.7 需要对原数组中的元素进行重新hash定位在新数组的位置，1.8新的位置不变或索引+新增容量大小。原因：提高扩容的效率，更快地扩容。
  • 扩容时机：在插入时，1.7先判断是否需要扩容，再插入，1.8先插入，完成再判断是否需要扩容；
  • 散列函数：1.7 做了四次移位和四次异或，jdk1.8只做一次。原因：做4次边际效用也不大，改为一次，提升效率。

32. 你能自己设计实现一个HashMap吗？

  • 散列函数：hashCode()+除留余数法
  • 冲突解决：链地址法
  • 扩容：节点重新hash获取位置
    myhashmap.png

33. HashMap 为什么不是线程安全的？

  • JDK1.7多线程下扩容会死循环。使用头插法插入元素，在多线程的环境下，扩容时有可能导致出现环形链表，造成死循环，JDK8使用尾插法，扩容时会保持链表原来的顺序。
  • 多线程put可能会导致元素的丢失。因为计算出来的位置可能会被其他线程的put覆盖，本来哈希冲突是应该用链表的，但多线程时由于没有加锁，相同位置的元素可能就被干掉了。
  • put和get并发时，可能导致get为null。线程1执行put时，因为元素个数超出阈值而导致出现扩容，线程2此时执行get，就有可能出现这个问题，因为线程1执行完table = newTab后，线程2中的table此时也发生了变化，此时去get时当然会get到null，因为元素还没有转移。

34. 如何解决HashMap线程不安全的问题呢？

  • HashTable直接在方法上加synchronized关键字，锁住整个table数组，粒度大
  • Collections.synchronizedMap使用 Collections 集合工具的内部类，内部定义了一个对象锁，方法内通过对象锁实现；
  • ConcurrentHashMap在jdk1.7中使用分段锁，在 jdk1.8 中使用 CAS+synchronized。

35. ConcurrentHashmap的实现？

  • jdk1.8 是基于CAS+synchronized实现。
  • 数据结构和 HashMap 是一样的，数组+链表+红黑树。它实现线程安全的关键点在于 put 流程。
  • put流程
    • 首先计算 hash，遍历 node 数组，如果 node 是空的话，就通过 CAS+自旋的方式初始化
    • 如果当前数组位置是空则直接通过 CAS 自旋写入数据
    • 如果 hash==MOVED，说明需要扩容，执行扩容
    • 如果都不满足，就使用 synchronized 写入数据，写入数据同样判断链表、红黑树，链表写入和 HashMap 的方式一样，key hash 一样就覆盖，反之就尾插法，链表长度超过 8 就转换成红黑树
  • get查询：和HashMap 基本相同，通过 key 计算位置，table 该位置 key 相同就返回，如果是红黑树按照红黑树获取，否则就遍历链表获取。

36. HashMap 内部节点是有序的吗？

  • HashMap 是无序的，根据 hash 值随机插入。LinkedHashMap 或者 TreeMap有序

37. LinkedHashMap怎么实现有序的？

  • LinkedHashMap维护了一个双向链表，有头尾节点，同时节点除了继承HashMap的Node属性，还有before和after用于标识前置节点和后置节点。可以实现按插入的顺序或访问顺序排序。

38. TreeMap怎么实现有序的？

  • TreeMap按照Key自然顺序或Comprator顺序进行排序，内部是通过红黑树来实现。所以要么key所属的类实现Comparable接口，或者自定义一个实现了Comparator接口的比较器，用于key比较

39. TreeMap 和 HashMap 的区别

  • HashMap 是基于数组+链表+红黑树实现的，put 元素的时候会先计算 key 的哈希值，然后通过哈希值计算出数组的索引，然后将元素插入到数组中，如果发生哈希冲突，会使用链表来解决，如果链表长度大于 8，会转换为红黑树。get 元素的时候同样会先计算 key 的哈希值，然后通过哈希值计算出数组的索引，如果遇到链表或者红黑树，会通过 key 的 equals 方法来判断是否是要找的元素。在没有发生哈希冲突的情况下，HashMap 的查找效率是 O(1)。适用于查找操作比较频繁的场景。
  • TreeMap 是基于红黑树实现的，put 元素的时候会先判断根节点是否为空，如果为空，直接插入到根节点，如果不为空，会通过 key 的比较器来判断元素应该插入到左子树还是右子树。get 元素的时候会通过 key 的比较器来判断元素的位置，然后递归查找。TreeMap 的查找效率是 O(logn)。并且保证了元素的顺序，因此适用于需要大量范围查找或者有序遍历的场景。

40. HashSet底层实现？

  • HashSet底层基于HashMap实现（除了clone()、writeObject()、readObject()是HashSet⾃⼰实现之外，其他⽅法都是直接调⽤HashMap中的⽅法。HashSet 会自动去重，因为HashMap 的键是唯一的（哈希值），相同键的值会覆盖掉原来的值，

41. HashSet 和 ArrayList 的区别

  • ArrayList 是基于动态数组实现的，HashSet 是基于 HashMap 实现的。
  • ArrayList 允许重复元素和 null 值；HashSet 元素唯一，基于元素的 hashCode 和 equals 方法来确定元素的唯一性。
    ArrayList 保持元素的插入顺序，可以通过索引访问元素；HashSet 不保证元素的顺序，存储顺序依赖于哈希算法，并且可能随着元素的添加或删除而改变

42. HashMap与Hashtable区别√

  • HashMap可以接收null键和值。当key为null时返回的值为0，Hashtable不能接受null键和值，会抛出空指针异常
  • HashMap线程不安全，Hashtable线程安全
  • HashMap默认大小是16，扩容每次为2的指数大小，HashTable中数组默认大小是11 ，扩容方法是old*2 + 1

43. HashMap和ConcurrentHashMap的区别？

  • ConcurrentHashMap线程安全；对整个桶数组进行了分割分段(Segment)，每一个分段上都用lock锁保护，ConCurrentHashMap不允许键值对null
  • HashMap线程不安全；HashMap的键值对允许有null

44. ConcurrentHashMap和Hashtable区别？

  • ConcurrentHashMap和Hashtable区别主要体现在实现线程安全的方式上不同。
  • 底层数据结构： ConcurrentHashMap和hashMap一样。Hashtable和JDK1.7的HashMap一样
  • 实现线程安全的方式：
    • ConcurrentHashMap：（JDK1.7分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment） JDK1.8，使用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap锁的方式是稍微细粒度的
    • Hashtable(同一把锁) :使用synchronized保证线程安全，效率低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态

45. 有哪些线程不安全的集合？高并发情况下如何保证线程安全？√

  • Vector、HashTable、Properties是线程安全的；
  • ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap等都是线程不安全的。
  • 使用线程安全的类，使用synchronized关键字等
  • 普通集合变为同步集合的工具方法Collections.synchronizedList(<? extends Collection> collection);

46. 集合如何排序？

  • 排序：实现Comparator接口compare(T o1,T o2)小于、等于或者大于o2分别返回负整数、0或者正整数

47. set实现类HashSet、LinkedHashSet、TreeSet的数据结构以及各自有优点

  • HashSet：无序，唯一，底层采用HashMap来保存元素（数组机制）
  • LinkedHashSet：有序，唯一，基于 LinkedHashMap 实现 链表和哈希表组合
  • TreeSet：有序，唯一，红黑树(自平衡的排序二叉树)

49. Comparable和Comparator区别?

  • Comparable接口用于当前对象和其它对象的比较，compareTo(Object obj) 方法用来排序,在比较类上修改
  • Comparator接口用于传入的两个对象的比较，compare(Object obj1, Object obj2) 方法用来排序，新增一个类专门用于比较

50. 集合类使用注意事项

  • 基于应用的需求来选择使用正确类型的集合。如果元素的大小是固定的且已知优先级此时使用Array，而不是ArrayList
  • 指定初始大小避免重复扩容
  • 使用泛型来保证类型安全，可靠性和健壮性
  • Map中尽量使用不可变类String作为一个key，可避免hashcode的实现和我们自定义类的equals方法
  • 返回零长度的集合或者数组，而不是返回一个null ，这样可以防止底层集合是空的

51. Array与ArrayList区别与选用？

  • Array可以容纳基本类型和对象，而ArrayList只能容纳对象。
  • Array是指定大小的，而ArrayList大小是固定的，可自动扩容。
  • 列表的大小已经指定且存储和遍历推荐使用Array
  • 多维数组推荐使用Array[][]