HashMap的桶位为什么是2的N次方（源码分析----1.8）

本文主要是介绍HashMap的桶位为什么是2的N次方（源码分析----1.8），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

内部类Node，实现Map.Entry（jdk1.8初次出现Node）

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }
}

HashMap实体中常量部分

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    /**
     * 初始化容量，必须是2的N次方
     * 
     * 1<<4即：1转换为二进制，向左移4位，右侧补零。00001（1） ----> 10000（16）
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    /**
     * 最大容量为1左移30位，即1+30个0共31位，大约为int最大值的一半
     * int共32位，首位0位正数 1位负数，不参与运算。因此最大值为2^31-1：共31个1
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认负载因子0.75
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 阈值，当拉链超过8，转换为红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 扩容后，若某个红黑树长度<6，则转换回链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 当map容量整体>64，才考虑转换红黑树
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
}

构造方法

    /**
     * 可指定初始化长度及负载因子
     *
     * 长度必须在0到1 << 30之间，否则报错
     * 长度若合法，则根据tableSizeFor计算长度
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

    /**
     * 将一个给定初始值，返回接近2的N次方数值，例如：2->2,3->4,7->8等，若小于0直接返回0，大于最大值返回最大值
     * 
     * 进来一个数，-1后，不断的向右无符号移动后和自己按位取或，
     * 例如：3，-1=2（0010），右移1（0001），按位取或：0011 = 3
     *     3继续右移2（0000），| 0011 = 0011（3），因此到最后一句之前都是3
     *     最后一句3+1=4，最终返回4
     */
    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;
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

从tableSizeFor方法可以看出，不论入参初始化hashMap长度为多少，其内部均会将其转换为一个2的N次方数值，这是为什么呢？

HashMap寻址使用的除留余数法，即位置 = hash%size，而对于计算机来说，位运算速度会更快，若要把取余运算优化为位运算，即：hash%size == hash&(size-1)，size必须为2的N次方。

因为：2^n-1的数字为全1，但最高位为0；若hash比size大，则高位与变0，低位全1与不变，相当于做了模除运算。

例如：9%8=1；

9（1001）& 7（0111） ---> 0001，即1

这篇关于HashMap的桶位为什么是2的N次方（源码分析----1.8）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！