Java 面经 - HashMap

[1]. 并发安全的容器都有哪些？

ConcurrentHashMap：线程安全的哈希表实现，适用于高并发的读写操作。

ConcurrentLinkedQueue：基于链表实现的非阻塞无界队列，适用于高吞吐量的并发场景。

ArrayBlockingQueue和LinkedBlockingQueue：分别是基于数组和基于链表实现的线程安全阻塞队列，支持有界和无界两种形式。适用于生产者-消费者模型。

PriorityBlockingQueue：基于优先级队列实现的阻塞队列，支持按照元素的优先级顺序出队。适用于需要按照优先级处理任务的场景。

[2]. HashMap的key如何设计？

选择Key类型时优先考虑不可变对象，避免使用易变对象，以免引发数据检索错误。

选择适当的哈希函数，将key均匀地分布在哈希表的桶中，以减少哈希冲突。

重写hashCode()和equals()方法，确保相同的对象具有相同的哈希码。

[3]. HashMap死循环问题

在JDK 1.7中，HashMap的底层实现是数组+链表的方式，并且HashMap在数据插入时采用的是头插法，因此，当发生并发扩容时，会造成死循环。

举个例子说明一下，比如存在一个旧HashMap，其转移链表元素的顺序是A→B→C。当线程T1和线程T2都准备对HashMap进行扩容操作，此时T1和T2都指向链表的头节点A，且T1和T2的下一个节点分别是T1.next和T2.next，都指向B节点。接下来开始扩容，这时，假设线程T2的时间片用完，进入了休眠状态，此时，线程T1开始执行扩容操作，线程T1执行完成之后，新HashMap的转移链表元素的顺序变成了C→B→A，当线程T1扩容完成后，线程T2被唤醒。但线程T2对于T1所执行的操作并不知晓，所以T2指向的仍然是A节点，T2.next指向的仍然是B节点。这样一来，A节点和B节点就形成了死循环。

[4]. HashMap为什么使用红黑树不使用B+树？

红黑树每个节点只包含一个键值对，节点间的指针关系简单，内存消耗较小。B+树每个非叶子节点都存储多个指针和数据，内存消耗较大。

红黑树是面向随机查找操作的设计，能够快速定位到特定的键值对。B+树更适合顺序查找和范围查询。

红黑树适合内存操作，B+树主要用于数据库索引、文件系统等场景，适合大规模数据存储和检索，比如磁盘存储。

[5]. 说一下平衡二叉树的插入、删除操作？

插入操作：

在平衡二叉树中从根节点开始查找合适的插入点。

如果新值小于根节点值，则向左子树继续查找，如果新值大于根节点值，则向右子树继续查找，直到找到一个合适的插入点。

插入新值后，从插入点开始向上遍历树，检查每个节点的平衡因子，再根据需要进行旋转操作来恢复树的平衡。

删除操作：

从根节点开始遍历树，找到需要删除的节点。

如果需要删除的节点是叶子节点，直接删除该节点；

如果需要删除的节点只有一个子节点，将该子节点提升到被删除节点的位置，并删除被删除节点；

如果需要删除的节点有两个子节点，找到该节点的中序遍历后继节点，将其值复制到需要删除的节点中，然后删除后继节点。

删除节点后，从删除点向上遍历树，检查每个节点的平衡因子，再根据需要进行旋转操作来恢复树的平衡。

[6]. 树的层序遍历说说？

树的层序遍历是按层次从上到下、从左到右依次访问节点。首先访问树的根节点，然后访问根节点的所有子节点，再访问子节点的子节点，依此类推。通常使用队列来实现。