Back
Java

Java面试之HashMap

HashMap（数组+链表）

  1. HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。
  2. 当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，然后找到bucket位置来储存值对象。
  3. 当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。

public V put(K key, V value) {
    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;
    //1. 如果当前table为空，新建默认大小的table
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //2. 获取当前key对应的节点
    if ((p = tab[i = (n - 1) & hash]) == null)
         //3. 如果不存在，新建节点
        tab[i] = newNode(hash, key, value, null);
    //4. 存在节点
    else {
        Node<K,V> e; K k;
        //5. key的hash相同，key的引用相同或者key equals，则覆盖
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //6.如果当前节点是一个红黑树树节点，则添加树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //7.不是红黑树节点，也不是相同节点，则表示为链表结构
        else {
            //遍历链表
            for (int binCount = 0; ; ++binCount) {
                //8. 找到最后那个节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //9. 如果链表长度超过8转成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //10.如果链表中有相同的节点，则覆盖
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //是否超过容量，超过需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

仔细观察哈希值的源头，我们会发现，它并不是 key 本身的 hashCode， 而是来自于HashMap 内部的另外一个 hash 方法。

为什么这里需要将高位数据移位到低位进行异或算呢？

这是因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的， 那么这种处理就可以有效避免类似情况下的哈希碰撞。

resize 方法的源码设计

final Node<K,V>[] resize() {
    // ...
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACIY &&
    oldCap >= DEFAULT_INITIAL_CAPAITY)
        newThr = oldThr << 1; // double there
    // ...
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {
        // zero initial threshold signifies using defaultsfults
        newCap = DEFAULT_INITIAL_CAPAITY;
        newThr = (int)(DEFAULT_LOAD_ATOR* DEFAULT_INITIAL_CAPACITY；
    }
    if (newThr ==0) {
        float ft = (float)newCap * loadFator;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Intege
    }
    threshold = neThr;
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newap];
    table = n；
    // 移动到新的数组结构 e 数组结构
}

依据 resize 源码，不考虑极端情况（容量理论最大极限由 MAXIMUM_CAPACITY 指定，数值为 1«30，也就是 2 的 30 次方）， 我们可以归纳为：

  • 门限值等于（负载因子）*（容量），如果构建 HashMap 的时候没有指定它们，那么就是依据相应的默认常量值。
  • 门限通常是以倍数进行调整 （newThr = oldThr « 1），我前面提到，根据 putVal 中的逻辑，当元素个数超过门限大小时，则调整 Map 大小。
  • 扩容后，需要将老的数组中的元素重新放置到新的数组，这是扩容的一个主要开销来源。

容量、负载因子和树化

容量和负载系数决定了可用的桶的数量，空桶太多会浪费空间，如果使用的太满则会严重影响操作的性能。 极端情况下，假设只有一个桶，那么它就退化成了链表，完全不能提供所谓常数时间存的性能。

如果能够知道 HashMap 要存取的键值对数量，可以考虑预先设置合适的容量大小。 具体数值我们可以根据扩容发生的条件来做简单预估，根据前面的代码分析，我们知道它需要符合计算条件：负载因子 * 容量 > 元素数量， 所以，预先设置的容量需要满足，大于“预估元素数量 / 负载因子”，同时它是 2 的幂数，结论已经非常清晰了。

对于负载因子如果没有特别需求，不要轻易进行更改，因为 JDK 自身的默认负载因子是非常符合通用场景的需求的。
如果确实需要调整，建议不要设置超过 0.75 的数值，因为会显著增加冲突，降低 HashMap的性能。
如果使用太小的负载因子，按照上面的公式，预设容量值也进行调整，否则可能会导致更加频繁的扩容，增加无谓的开销，本身访问性能也会受影响。

树化改造，对应逻辑主要在 putVal 和 treeifyBin 中。

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 树化改造逻辑
    }
}

综合这两个方法，树化改造的逻辑就非常清晰了，可以理解为，当 bin 的数量大于 TREEIFY_THRESHOLD 时：

  • 如果容量小于 MIN_TREEIFY_CAPACITY，只会进行简单的扩容。
  • 如果容量大于 MIN_TREEIFY_CAPACITY ，则会进行树化改造。

那么，为什么 HashMap 要树化呢？
本质上这是个安全问题。因为在元素放置过程中，如果一个对象哈希冲突，都被放置到同一个桶里，则会形成一个链表， 我们知道链表查询是线性的，会严重影响存取的性能。
而在现实世界，构造哈希冲突的数据并不是非常复杂的事情，恶意代码就可以利用这些数据大量与服务器端交互， 导致服务器端 CPU 大量占用，这就构成了哈希碰撞拒绝服务攻击，国内一线互联网公司就发生过类似攻击事件。

当两个对象的hashcode相同

它们会储存在同一个bucket位置的链表中。因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。 因为HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。

HashMap 内部的结构，它可以看作是数组（Node[] table）和链表结合组成的复合结构， 数组被分为一个个桶（bucket），通过哈希值决定了键值对在这个数组的寻址； 哈希值相同的键值对，则以链表形式存储。 这里需要注意的是，如果链表大小超过阈值（TREEIFY_THRESHOLD, 8），的链表就会被改造为树形结构。

两个键的hashcode相同,如何获取值对象

当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。

HashMap的大小超过了负载因子(load factor)定义的容量，会发生什么？

对象会进行rehashing，调用hash方法找到新的bucket位置。
默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。

调整HashMap大小存在什么问题

多线程的情况下，可能产生条件竞争(race condition)。如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。

为什么String, Interger这样的wrapper类适合作为键

因为wrapper类如String是不可变的，也是final的，而且重写了equals()和hashCode()方法了，防止计算hashCode()改变键值。

如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。

也可以使用自定义的对象作为键，条件是遵守equals()和hashCode()方法的定义规则，并且当对象插入到Map中之后将不会再改变了。

HashMap与HashSet

HashMap HashSet
实现了Map接口 实现了Set接口（构造new HashMap）
put()存键值对 add()存储对象
使用键对象来计算hashcode值 使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false

HashMap与Hashtable

  1. HashMap几乎等于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行)。
  2. HashMap是非synchronized，而Hashtable是synchronized。Java 5提供了ConcurrentHashMap，可以替代HashTable
  3. HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器非fail-fast。所以当有其它线程通过map对象改变了HashMap的结构（增加或者移除元素），会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出这个异常。
  4. 由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。
  5. HashMap不能保证随着时间的推移Map中的元素次序是不变的。

如何保证容器是线程安全的？ConcurrentHashMap 如何实现高效地线程安全？

Java 提供了不同层面的线程安全支持。在传统集合框架内部，除了 Hashtable 等同步容器， 还提供了所谓的同步包装器（Synchronized Wrapper），我们可以调用 Collections 工具类提供的包装方法，来获取一个同步的包装容器（如 Collections.synchronizedMap）， 但是它们都是利用非常粗粒度的同步方式，在高并发情况下，性能比较低下。

另外，更加普遍的选择是利用并发包提供的线程安全容器类，它提供了：

  • 各种并发容器，比如 ConcurrentHashMap、CopyOnWriteArrayList。
  • 各种线程安全队列（Queue/Deque），如 ArrayBlockingQueue、SynchronousQueue。
  • 各种有序容器的线程安全版本等。

具体保证线程安全的方式，包括有从简单的 synchronize 方式， 到基于更加精细化的，比如基于分离锁实现的 ConcurrentHashMap 等并发实现等。
具体选择要看开发的场景需求，总体来说，并发包内提供的容器通用场景，远优于早期的简单同步实现。

CocurrentHashMap与Hashtable (为什么需要 ConcurrentHashMap？)

Hashtable是synchronized的(基本就是将 put、get、size 等各种方法加上“synchronized”)， 简单来说，这就导致了所有并发操作都要竞争同一把锁，一个线程在进行同步操作时，其他线程只能等待，大大降低了并发操作的效率。

同步包装器只是利用输入 Map 构造了另一个同步版本，所有操作虽然不再声明成为 synchronized 方法， 但是还是利用了“this”作为互斥的 mutex，没有真正意义上的改进。

private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {
        private static final long serialVersionUID = 1978198479659022715L;

        private final Map<K,V> m;     // Backing Map
        final Object      mutex;        // Object on which to synchronize
        ...
        public int size() {
            synchronized (mutex) {return m.size();}
        }
        public boolean isEmpty() {
            synchronized (mutex) {return m.isEmpty();}
        }
        ...
}

所以Hashtable 或者同步包装版本，都只是适合在非高度并发的场景下。

ConcurrentHashMap 同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁。 ConcurrentHashMap的设计实现其实一直在演化，在 Java 8 中就发生了非常大的变化（ava 7 其实也有不少更新）。

早期 ConcurrentHashMap，其实现是基于：

  • 分离锁，也就是将内部进行分段（Segment），里面则是 HashEntry 的数组，和 HashMap类似，哈希相同的条目也是以链表形式存放。
  • HashEntry 内部使用 volatile 的 value 字段来保证可见性，也利用了不可变对象的机制以改进利用 Unsafe 提供的底层能力，比如 volatile access，去直接完成部分操作，以最优化性能，毕竟 Unsafe 中的很多操作都是 JVM intrinsic 优化过的。

在构造的时候，Segment 的数量由所谓的 concurrentcyLevel 决定，默认是 16，也可以在相应构造函数直接指定。 注意，Java 需要它是 2 的幂数值，如果输入是类似 15 这种非幂值，会被自动调整到 16 。

ConcurrentHashMap(JDK7)并发写操作时：
ConcurrentHashMap 会获取再入锁，以保证数据一致性，Segment 本身就是基于ReentrantLock 的扩展实现， 所以，在并发修改期间，相应 Segment 是被锁定的。 在最初阶段，进行重复性的扫描，以确定相应 key 值是否已经在数组里面，进而决定是更新还是放置操作。 重复扫描、检测冲突是ConcurrentHashMap 的常见技巧。 ConcurrentHashMap进行的不是整体的扩容，而是单独对 Segment进行扩容。

Map 的 size 方法同样需要关注，它的实现涉及分离锁的一个副作用。 如果不进行同步，简单的计算所有 Segment 的总值，可能会因为并发 put，导致结果不准确， 但是直接锁定所有 Segment 进行计算，就会变得非常昂贵。
所以，ConcurrentHashMap 的实现是通过重试机制（RETRIES_BEFORE_LOCK，指定重试次数 2），来试图获得可靠值。 如果没有监控到发生变化（通过对比 Segment.modCount），就直接返回，否则获取锁进行操作。

在 Java 8 和之后的版本中，ConcurrentHashMap 发生了哪些变化呢

  • 总体结构上，它的内部存储变得和 HashMap 结构非常相似，同样是大的桶（bucket）数组，然后内部也是一个个所谓的链表结构（bin），同步的粒度要更细致一些。
  • 其内部仍然有 Segment 定义，但仅仅是为了保证序列化时的兼容性而已，不再有任何结构上的用处。
  • 因为不再使用 Segment，初始化操作大大简化，修改为 lazy-load 形式，这样可以有效避免初始开销，解决了老版本很多人抱怨的这一点。
  • 数据存储利用 volatile 来保证可见性。
  • 使用 CAS 等操作，在特定场景进行无锁并发操作。
  • 使用 Unsafe、LongAdder 之类底层手段，进行极端情况的优化。
HashMap
Licensed under CC BY-NC-SA 4.0
comments powered by Disqus