Java 8 HashMap

hashmap 使用数组、链表和红黑树存储键值对，当链表足够长时，会转换为红黑树。hashmap 是非线程安全的。

hashmap 中的常量

static final int default_initial_capacity = 1 << 4;
static final int maximum_capacity = 1 << 30;
static final float default_load_factor = 0.75f;
static final int treeify_threshold = 8;
static final int untreeify_threshold = 6;
static final int min_treeify_capacity = 64;

• default_initial_capacity 初始容量为 16。
• maximum_capacity 最大容量为 2³⁰ 。
• default_load_factor 默认装填因子。初始情况下，当键值对数量大于 16 * 装填因子时，就会扩容为原来的 2 倍。
• treeify_threshold 当链表的长度达到该值时，有可能会转化为树。
• untreeify_threshold 当链表长度小于该值时，会从树退化为链表。
• min_treeify_capacity 在转变为树前，会做一次判断，只有键值对的数量大于该值时，才会转化为红黑树，若小于该值，只触发扩容。

hashmap 中的容量用到了移位操作，将一个数 a 左移 n 位相当于：a = a * 2ⁿ ，所以 1 << 4 => 1 * 2⁴ = 16 。因此，hashmap 的容量总是 2 的 n 次幂。

使用有参构造方法可以指定初始容量和装填因子，指定的容量会被向上调整为 2 的 n 次幂（比如给定容量为13，则会调整为 16）。

hashmap 中键值对的值可以为 null，可以存在一个 key 为 null 的键值对。

hashmap 的部分方法

treeifybin 方法

/**
 * replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 */
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) {
        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);
    }
}

在调用 put 方法添加键值对时，如果数量达到了 treeify_threshold ，就会调用 treeifybin 方法，该方法会再判断一次表长度是否达到 min_treeify_capacity，如果没有达到，就只做扩容操作，否则将表转化为树。

这里的 (n - 1) & hash 就是求余操作，相当于 hash % n，因为 hashmap 的长度总是 2 的 n 次幂。

replaceall 方法

@override
public void replaceall(bifunction<? super k, ? super v, ? extends v> function) {
    node<k,v>[] tab;
    if (function == null)
        throw new nullpointerexception();
    if (size > 0 && (tab = table) != null) {
        int mc = modcount;
        for (int i = 0; i < tab.length; ++i) {
            for (node<k,v> e = tab[i]; e != null; e = e.next) {
                e.value = function.apply(e.key, e.value);
            }
        }
        if (modcount != mc)
            throw new concurrentmodificationexception();
    }
}

该方法接受一个 lambda 表达式，将满足给定条件的值替换掉，比如：

hashmap<integer, string> map = ...;
// 将 key 为偶数的所有键值对的值替换为 "foo"
map.replaceall((k, v) -> k % 2 == 0 ? "foo" : v);

foreach 方法

@override
public void foreach(biconsumer<? super k, ? super v> action) {
    node<k,v>[] tab;
    if (action == null)
        throw new nullpointerexception();
    if (size > 0 && (tab = table) != null) {
        int mc = modcount;
        for (int i = 0; i < tab.length; ++i) {
            for (node<k,v> e = tab[i]; e != null; e = e.next)
                action.accept(e.key, e.value);
        }
        if (modcount != mc)
            throw new concurrentmodificationexception();
    }
}

该方法也接受一个 lambda 表达式，用于消费键值对：

// 打印所有键值对
map.foreach(
    (k, v) -> system.out.println(k + ": " + v)
);

// 打印所有 key 为偶数的键值对
map.foreach(
    (k, v) -> {
        if (k % 2 == 0)
            system.out.println(k + ": " + v)
    }
);