Java集合包面试题

你知道HashMap底层的数据结构是什么吗?

底层就是数组,每个数组存放Node<K,V>.

初始化时数组长度默认就是16,扩容因子是0.75.

Node,是一个单向链表,当链表长度达到8的时候,会转换成红黑树.

使用注意:最好指定hashmap的一个预估大小,如果预估大小相对准确,负载因子可以设置为1

你知道HashMap是如何解决hash碰撞问题的吗?

HashMap从两个方面解决hash碰撞问题:

1. 优化hash算法

HashMap计算存储位置是 hash(key)%table.length

hash(key)%table.length,从数学角度看,等同于hash(key)&(table.length-1).这是寻址算法的优化.求余%性能比较差,位运算&性能非常好.

table.length是int,表示32bit.

当table.length-1小于2的16次方的时候,那么高16位&运算永远等于0,这样的话hash(key)的高16位没有参与运算,hash碰撞的概率就会提高.为了减少hash碰撞的概率,可以通过高16位和低16位异或,同时计算出高16位和低16位的特征.

因此,hash算法的优化减少了hash碰撞的概率.

1. 链表+红黑树存储hash碰撞的数据

当计算出的存储位置相同时,会用链表的方式存储,此时查找时间复杂度是O(n);

当链表长度大于8时,会转换成红黑树,查找时间复杂度是O(logn).

说说HashMap是如何进行扩容的可以吗?

HashMap每次都是2倍扩容.

为什么2倍扩容这种设计呢?判断是否数据迁移以及迁移性能比较高.

假设HashMap的长度table.legth,默认等于16,那么table.legth-1=15,对应二进制数据为:

0000 0000 0000 0000 0000 0000 0000 1111

有2个元素的hash(key)对应二进制数据分别为:

# 元素A
0000 0000 0000 0000 0000 0000 0000 1001
# 元素B
0000 0000 0000 0000 0000 0000 0001 1001

计算存储位置hash(key)&(table.length-1)结果为:

0000 0000 0000 0000  0000 0000 0000 1001
0000 0000 0000 0000  0000 0000 0000 1001

现在HashMap的长度扩容为32位,table.length-1对应二进制数据为:

0000 0000 0000 0000 0000 0000 0001 1111

重新计算存储位置hash(key)&(table.length-1)结果为:

# 元素A
0000 0000 0000 0000  0000 0000 0000 1001
# 元素B
0000 0000 0000 0000  0000 0000 0001 1001

可以看得出,元素A的新存储位置没有变化,但是元素B在右起5位变成1.

那么只要判断右起第五位是否变化就可以判断是否需要数据迁移,同时只需要赋值到旧位置+16的新位置即可.

说说TreeMap和LinkedHashMap的实现原理?

// TreeMap  红黑树
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;
}
// HashMap 数组+链表(链表长度超过8转换红黑树)
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}
// LinkedHashMap 数组+链表
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

那你说一说红黑树的特性和优势,在什么情况下需要变色?什么情况下需要旋转?

红黑树是一种平衡二叉树,不会出现二叉查找树极端的链式结构,查找的最大次数等同于红黑树的高度.

红黑树(Red Black Tree)是一种自平衡的二叉查找树。除了符合二叉查找树的基本特征外,它还具有下列的附加特性:

1.节点是红色或黑色。

2.根节点是黑色。

3.每个叶子节点都是黑色的空节点（NIL节点）。

4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

第一次插入，由于原树为空，所以只会违反红-黑树的规则2，所以只要把根节点涂黑即可。

如果插入的节点的父节点是黑色的，那不会违反红-黑树的规则，什么也不需要做

如果插入的节点的父节点是红色的,需要通过变色和旋转维持平衡.