[数据结构与算法] 面试中的HashMap

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 面试中的HashMap -> 正文阅读

[数据结构与算法]面试中的HashMap

关键常量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

默认初始bucket容量
static final int MAXIMUM_CAPACITY = 1 << 30;

默认最大bucket容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认负载因子，当元素数量超过负载因子 * bucket容量时，就会触发扩容
static final int TREEIFY_THRESHOLD = 8;

默认树化元素容量，如果某个bucket中元素数目超过此值，则会转化成树
static final int UNTREEIFY_THRESHOLD = 6;

默认树退化为链表容量，如果某个bucket中元素数目少于此值，则会退化为链表
static final int MIN_TREEIFY_CAPACITY = 64;

最小树化bucket容量。链表树化之前还有一次判断，只有bucket数组的长度大于等于64才会触发树化操作。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。如果确实发生了这种情况，HashMap会进行resize扩容。

关键问题

hash函数如何做到尽可能平均？

hash函数的实现方法（扰动函数）：(h = key.hashCode()) ^ (h >>> 16)

实际上就是将key的高16位与低16位进行异或运算（相同为0，相异为1），从而让尽可能多的位参与到hash中，降低hash冲突概率

数组容量大小为什么是2的n次方？

元素在bucket数组中的定位方法：hash & (capacity - 1)

其实等价于 hash % capacity，但是对计算机更加友好

只有 capacity 是2的n次方，（capacity - 1）的结果必定是 011...11这种形式，这样数组定位方法就能尽可能平均地占用每一个数组的格子，从而发挥我们hash函数的效果。

为什么链表转红黑树的阈值是8？

时间和空间权衡的结果。

红黑树节点数约为链表节点数的2倍，当节点太少的时候，红黑树的查找性能优势并不明显，付出2倍的空间代价不值得。

理想情况下，使用随机的哈希码，节点分布在hash桶中的概率服从泊松分布。链表中的节点个数为8的概率约为 0.00000006，这个概率足够低了。并且到8时，红黑树的性能优势也能展现出来了。

为什么红黑树转链表的阈值不是8，而是6呢？

因为如果阈值也是8的话，当节点个数在8附近徘徊时，会频繁进行链表和红黑树的转换，造成性能的损耗。

当以一个初始容量创建HashMap时，HashMap的容量是如何计算的？

采用以下的公式进行计算

/**
 * Returns a power of two size for the given target capacity.
 */
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;
}

先通过将最高位移动和或，获取到一个低位全是1的值，然后将这个值+1，就会得到一个比cap大的2的N次方的数。

至于cap-1，是为了处理cap本身就是2的N次方的情况（那样的话，cap本身就是最终的容量了）

threshold有什么用？

存储扩容阈值
在新建HashMap对象时，threshold还会被用来存储初始化的容量。因为HashMap只有在第一次插入节点时，才会初始化table。

链表结构数据迁移之后的位置在哪里？为什么？

链表数据迁移之后，节点只有可能在两个位置：原来数组下标的位置，以及原来数组下标位置*2

因为扩容之后，容量变为原来的两倍。进行hash计算时，使用的公式：hash & （newCapacity-1） 中，(newCapacity - 1) 的二进制相较于 (oldCapacity - 1 )只是前面多了一个1。如果hash函数计算出来的结果中该位为0，则为原来数组下标位置不变，否则会变为原来数组下标位置*2。

所以在resize扩容代码中，有了如下判断：

if ((e.hash & oldCap) == 0) {
    // 扩容后，新位置依然在原下标位置
    if (loTail == null)
        loHead = e;
    else
        loTail.next = e; // 尾插法
    loTail = e;
}
else {
    // 扩容后，新位置在原下标位置*2处
    if (hiTail == null)
        hiHead = e;
    else
        hiTail.next = e; // 尾插法
    hiTail = e;
}

HashMap有哪些问题？

并发情况下存在数据覆盖问题
并发情况下遍历的同时修改会抛出 ConcurrentModificationException 异常
JDK1.8之前还存在死循环问题

JDK1.7为什么会有死循环问题？

JDK1.7时，HashMap插入采用 “头插法”，会导致同一索引位置的节点在扩容后顺序反掉。

使用自定义对象作为HashMap的键时，需要注意什么？

需要重新自定义对象类的equals方法和hashCode方法。

HashMap定位元素在数组中的位置时，是使用该元素类的hashCode算的。如果该类没有定义hashCode方法，那么就会使用Object类的hashCode方法。而Object类的hashCode方法默认取的是对象的内存地址，这很可能不符合预期。
HashMap在比较元素时，是使用该元素类的equals比较的。如果该类没有定义equals方法，那么就会使用Obejct类的equals方法。而Object类的equals方法默认取得是对象的内存地址，这很可能不符合预期。

源码分析（jdk1.8）

get

public V get(Object key) {
    Node<K,V> e;
    // 需要获取key的hash，来定位在bucket数组中哪一个位置
    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;
    // 判断bucket是否为null && 指定bucket数组位置是否为null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判断该bucket数组位置上第一个元素是否就是要查询的元素
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 第一个元素不是要查询的元素，继续查询该位置下的链表/红黑树
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

put

HashMap插入流程

public V put(K key, V value) {
    // 同样先计算hash值，计算要放的bucket数组位置
    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;
    // 判断数组是否未初始化，如果是，则初始化（懒初始化）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 判断该bucket数组位置是否为null，如果没有元素，则直接创建一个新元素放进去就ok了
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 该bucket数组位置已经有元素了
        Node<K,V> e; K k;
        // 该bucket数组位置上第一个元素就是要put的位置，直接覆盖
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 该bucket数组位置上第一个元素不是要put的位置，且是一棵红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 该bucket数组位置上第一个元素不是要put的位置，且是一个链表
        else {
            for (int binCount = 0; ; ++binCount) {
                // 没有找到重复key的值，则在链表末尾新增一个节点，挂上去
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表的长度超过了树化的阈值，则进行树化（树化操作内部还判断了bucket数组length）
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果找到了重复key值的元素，则需要覆盖
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // e不为null，则代表要put的元素key已经存在，直接覆盖即可
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 操作计数（每次涉及到写操作，都+1，可以帮助判断是否存在并发写）
    ++modCount;
    // 元素put之后，若大于threshold，则需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

链表树化的时候，还会判断bucket数组length是否达到了阈值，代码如下：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // bucket数组的length是否达到阈值（不是map中的节点数组size哦），如果未达到，则进行resize
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 否则进行树化操作
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

resize

扩容流程

上面的代码中多次看到了resize操作。事实上，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;
    // 如果旧的bucket长度大于0（非初始化），则需要扩容
    if (oldCap > 0) {
        // 下面计算bucket扩容后的容量，一般是*2，但不能超过Integer.MAX_VALUE
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 初始化时，如果threshold>0，先将bucket数组容量设置为threshold（threshold在惰性初始化时，临时充当容量的角色）
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 初始化时，啥都没有配，则都赋默认值
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 创建出新bucket数组
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 旧bucket数组不为空，进行扩容
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 旧bucket数组中，若当前遍历到的位置不为null，则需要处理扩容
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 如果该位置只有一个元素，则直接计算挂载到新bucket中
                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;
                        }
                        // 扩容后，新位置在原下标位置*2处
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;// 尾插法
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 将转移好的链表，挂载到新bucket中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}