hashmap里面的重要字段及方法：

capacity & size

capacity是指当前hashmap的容量，注意是当前，因为hashmap本身存在扩容。

size则是指当前hashmap中的实际元素个数。

注意这里两个值都不是table数组的长度，而是hashmap 数组 + 链表作为一个整体的元素。

其在hashmap.java中的定义如下：

    /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

    .......
        
    final int capacity() {
        return (table != null) ? table.length :
            (threshold > 0) ? threshold :
            DEFAULT_INITIAL_CAPACITY;
    }

    // 这里实现用到的table\threshold\DEFAULT_INITIAL_CAPACITY详见下文 

下面代码说明：

        hashmap map = new hashmap();
        map.put("jin", "alan");

        // 获取map的类-类型
        Class mapClazz = map.getClass();

        /*
            capacity，当前容量，是个方法，其实现是：
        */
        // 通过反射获取其当前的capacity,默认会是16
        Method capacityMethod = mapClazz.getDeclaredMethod("capacity");
        // 设置访问权限
        capacityMethod.setAccessible(true);

        System.out.println("map capacity = " + capacityMethod.invoke(map));


        // 通过反射获取其 size，也就是目前hashmap中有多少元素，刚刚put了一个，所以会是1
        // 也可以用Method，因为有一个 int size()方法
        Field sizeField = mapClazz.getDeclaredField("size");
        sizeField.setAccessible(true);
        System.out.println("map size = " + sizeField.get(map));

通过反射取到其方法、字段，执行后得到对应的值，印证了注释中预估的结果。

但是需要注意，如果刚开始指定了大小，那么threshold的值就是tableSizeFor的值，也就是初始化的hashmap容量（2^n），jdk中源代码如下：

    /**
     * Constructs an empty <tt>hashmap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    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);
    }

看最后一行代码对threshold的赋值就知道了，下面写测试代码验证下：

        Map giveSizeMap = new hashmap(14);
        System.out.println("giveSizeMap capacity = " + capacityMethod.invoke(giveSizeMap)); //16
        System.out.println("giveSizeMap size = " + sizeField.get(giveSizeMap)); // 0
        System.out.println("giveSizeMap loadFactor = " + loadFactorField.get(giveSizeMap)); // 0.75
        System.out.println("giveSizeMap threldold =" + thresholdField.get(giveSizeMap)); // ?  = 16

不出所料，打印出来threshold的值是16.

但是下面往这个map中添加值，如下：

        giveSizeMap.put("1", "a");
 
        System.out.println("now giveSizeMap capacity = " + capacityMethod.invoke(giveSizeMap)); //16
        System.out.println("now giveSizeMap size = " + sizeField.get(giveSizeMap)); // 0
        System.out.println("now giveSizeMap loadFactor = " + loadFactorField.get(giveSizeMap)); // 0.75
        System.out.println("now giveSizeMap threldold =" + thresholdField.get(giveSizeMap)); // 12

就会看到，一但向其中put数据，threshold的值就会变成 capacity * loadFactor，具体put的实现下面会详细分析。

loadFactor & threshold

loadFactor的意思是装载因子，是一个小于等于1的小数，其作用就是定义扩容阈值百分比。默认值0.75。

threshold就是具体的扩容阈值了，threshold = loadFactor * capacity。

loadFactor的值为什么是0.75呢？capacity的值是2的N次方，所以当N大1时，后续3/4 * capacity，得到的会一直是整数。

默认的threshold = 16 * 0.75 = 12，当hashmap中的size值大于threshold时，会触发扩容。

下面使用代码验证hashmap的扩容过程。

        hashmap map3 = new hashmap(3);

        // 通过反射获取其当前的capacity,默认会是16
        Method capacityMethod = mapClazz.getDeclaredMethod("capacity");
        // 设置访问权限
        capacityMethod.setAccessible(true);
        
        // size
        Field sizeField = mapClazz.getDeclaredField("size");
        sizeField.setAccessible(true);

        // loadFactor
        Field loadFactorField = mapClazz.getDeclaredField("loadFactor");
        loadFactorField.setAccessible(true);

        // threshold
        Field thresholdField = mapClazz.getDeclaredField("threshold");
        thresholdField.setAccessible(true);

        // 使用map3 做扩容的验证过程
        map3.put("1","a");
        map3.put("2","a");
        map3.put("3","a");

        // 获取capacity、size、threshold、loadFactor
        System.out.println("map capacity = " + capacityMethod.invoke(map3)); //4
        System.out.println("map size = " + sizeField.get(map3)); // 3
        System.out.println("map loadFactor = " + loadFactorField.get(map3)); // 0.75
        System.out.println("map threldold ="+ thresholdField.get(map3)); // 4 * 0.75 = 3

        // 再增加一个元素,大于threshold，触发扩容
        System.out.println("capacity resize");
        map3.put("4","a");
        System.out.println("map capacity = " + capacityMethod.invoke(map3)); //8
        System.out.println("map size = " + sizeField.get(map3)); // 4
        System.out.println("map loadFactor = " + loadFactorField.get(map3)); // 0.75
        System.out.println("map threldold ="+ thresholdField.get(map3)); // 8 * 0.75 = 6

table

    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;

table其实就是hashmap的存储底层，也就是一个数组，table.length总是2的N次方，不过<key，value>被封装到了Node对象里面，详细的可以看下面关于Node的内容。

获取table的长度

        // 获取table的长度
        Field tableField = mapClazz.getDeclaredField("table");
        tableField.setAccessible(true);
    
        System.out.println("map table length = " + ((HashMap.Entry[])tableField.get(map3)).length);

测试后可以发现，table.length与capacity的值总是一样，也就是 table是所有数据的存储容器。

tableSizeFor

这个方法用来计算扩容时hashmap的容量值，可以看到，hashmap的扩容并不会以用户指定的值为准，而是去寻找一个大于指定值的最小2的N次方。而计算的实现就是用这个方法来做的，先看代码：

    /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;   // 第一步：先把指定的值减1
        // 第二步，向右移位 并与当前值按位或；其目的对于一个数字的二进制，从第一个不为0的位开始，把后面的所有位都设置成1。
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        // 第三步，计算极限值，最后+1 返回
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

第一步为什么减1呢？先卖个关子，看核心的第二步

        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;

先说下右移位，也就是将二进制数向右移对应的位数。

按位或，就是将两个参与运算的二进制数，任意为1的位设置为1，否则设置为0.

先根据第一行举个例子，假设n=2，其对应的二级制数为 10，那么会有如下操作：

0010 >>> 1 =  0001 (右移1位)   ---- 第一行，右移1位

0010 | 0001 = 0011 （按位或），

0011 >>> 2 = 0000 (右移2位)    ---- 第二行，右移2位

0011 | 0000 = 0011 (按位或)

下面右移4位、8位、16位，最终得到的结果都是 0011 ，也就是十进制的3

最后第三步，当小于极限值的时候，需要+ 1，3+ 1 = 4

考虑到第一步，n = cap -1，也就是cap=3

也就是，十进制数3 的最近满足需要的容量是 4

这个不过瘾，n来个大点儿的数，比如18，二进制数是：0001 0010

0001 0010 >>> 1 = 0000 1001       ---- 第一行，右移1位
0001 0010 | 0000 1001 = 0001 1011  

0001 1011 >>> 2 = 0000 0110   ---- 第二行，右移两位
0001 1011 | 0000 0110 = 0001 1111   
到这里已经把第一位不为0，后面所有的0都设置为了1，再移位4、8、16，都是一样的结果

所以这里的值是 0001 1111 = 16+8+4+2+1 = 31

设置的值：cap = n + 1 = 19

其对应的实际容量是 31 + 1= 32

到这里，第二步和第三步都已经解释清楚了，那么第一步的 n = cap -1 是干啥的呢？

当cap本身就是2的N次方时，上面的算法是有点问题的，比如传入的capacity是4，那么得到的结果本应该是4，结果得到了8

假设没有 n = cap - 1 这一行
n = cap = 4，换算成二进制就是 0100，下面进行换算：
0100 >>> 1 = 0010
0010 | 0100 = 0110

0110 >> 2 = 0001
0001 | 0110 = 0111  --- 都变成了1，结束

执行第三步，实际的容量是 4+2+1  +1 = 8，其实是多设置了一倍。

所以刚开始就把n的值设置为4 - 1 =3，最终得到的容量会是4，完美解决。这就是n = cap - 1 的由来。

所以这里tableSizeFor只是做单一的事情：寻找距离最近的2的N次方。

而实际上，如果设置了cap=4，得到的实际capacity值也是4的话，马上就会触发一次扩容，反而性能不好。不过这里jdk的开发人员这么做，只是为了一个方法只做一件事情，无可厚非。所以在初始化设置就需要参考下一节的内容。

初始化时指定容量

如果在初始化hashmap时传入预估的容量值，hashmap会把值设置为大于指定值最近的一个2的N次方，比如1 —>1, 3—>4, 6—>8, 55—>64。下面进行代码测试：

        hashmap map = new hashmap(1); // 指定初始化值

        // 获取map的类-类型
        Class mapClazz = map.getClass();

        Method capacityMethod = mapClazz.getDeclaredMethod("capacity");
        // 设置访问权限
        capacityMethod.setAccessible(true);

        System.out.println("map capacity =" + capacityMethod.invoke(map1));  // 1

        hashmap map3 = new hashmap(3);
        System.out.println("map capacity = " + capacityMethod.invoke(map3)); // 4

        hashmap map55 = new hashmap(55);
        System.out.println("map capacity = " + capacityMethod.invoke(map55)); // 64

执行后结果印证了tableSizeFor的作用。另外注意，这里只用了一个反射获取对应的method，通过invoke时传入不同的对象来获取对应的值。

关于初始化值的设置：

如果知道了对应的数据个数为7，那么是不是直接传入7就可以了呢？

直接设置7，tableSizeFor得到的值是8，而threshold的值是6，7 >6，所以数据设置之后马上就会触发一次扩容，hashmap的capacity从8变成16，会有一定的性能损耗。

所以设置的初始值应该是： 数据长度 / loadFactor + 1, 也就是 7 / 0.75 + 1 = 10,那么tableSizeFor得到的就是16，不需要进行扩容。

hashmap的hash

先看下JDK1.8里面的实现：

    /**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

可以看到，这里的hash取值，将key.hashCode右移16位 然后与其本身进行按位 异或（(h = key.hashCode()) ^ (h >>> 16)），目的是对hashCode进行混淆，避免出现一些key对应的hashcode高位不同、低位相同，但是在取模（需要找hashmap中数组的下标）的时候低位相同就可能出现碰撞的问题。

这里JDK1.8 跟JDK1.7的差别还是蛮大的，看下jdk7的代码：

    /**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because hashmap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
     */
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

这里的参数h是指key的hashcode(), 调用时是这样：int hash = hash(key.hashCode());

而一系列针对h的右移位、按位异或(^)，不过是跟jdk8中的 (h = key.hashCode()) ^ (h >>> 16) 一样的目的，扰乱hashcode的正常值，尽可能的避免hash碰撞。

注意jdk中的 indexFor方法，这个方法是获取hash值对应的数组下标的，不过这里为什么用了一个按位与(&)操作呢？

jdk7中indexFor为什么使用按位与

按位与在这里的作用，其实与取模的结果是一样的，indexFor方法本来就是为了根据hash值获取对应的数组下标。那么为什么不用取模呢？性能，一切为了性能！

在1.7的HashTable中，其实取下标是用了取模的，模是hashTable的长度：

int index = (hash & 0x7FFFFFFF) % tab.length; （这里&只是为了保证为正数，毕竟首位为0 代表正数，首位为1代表负数）。

不过HashTable在初始化的时候默认值是11，每次扩容是 2N +1 ，也就是始终都是奇数个，使用取模来处理更简单，而且按位与也无法保证结果与取模相同。

而hashmap则始终是2的N次方长度，这就为&操作提供了便利,记住下面这个公式：

X % 2^n = X & (2^n – 1)

2^n表示2的n次方，也就是说，一个数对2^n取模 == 一个数和(2^n – 1)做按位与运算 。

假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 -1 = 7 ，即0111。

假设x=18，也就是 0001 0010，一起看下结果：
对 2的n次方 取模： 18 % 8 = 2
对 2的n次方-1 按位与： 0001 0010 & 0111 = 0000 0010 = 2

不过这个要求是， tab.length必须是2的N次方，而hashmap的capacity设计的就是2的N次方长度，此时按位与刚好满足需要，又可以提高性能。

至于HashTable为什么这么设计，个人猜想是本来内部就采用了synchronized机制，性能偏低，实现层面就简单点好了。另外，hashTable也确实不常用…...

JDK8中消失的indexFor

在jdk8的hashmap源码中，indexFor方法消失了。不过同样的代码其实包含在了具体的使用场景，比如get方法中引用的getNode实现：

first = tab[(n - 1) & hash]

其实就是将indexFor这个一行代码的方法合并到具体实现中了。