前言

ysoserial反序列化漏洞利用工具的CC6和CC7链都使用的HashSet和Hashtable都是基于哈希表的数据存储结构，说到哈希表在Java中用的最多的使用哈希表存储结构的就是HashMap类了，同时HashMap类也是CC6链中HashSet类的底层实现基础，HashSet的增删改查方法都是基于一个在构造函数中最开始实例化的一个HashMap类，CC7链中的Hashtable类和HashMap类用法及结构也非常相似，简单分析一下HashMap的源码还是比较有意义的。

测试环境

jdk1.8

Node内部静态类

HashMap类就是通过这样一个内部类实现键值对数据存储的结构，Node类实现了Map类的Entry接口，每添加一个元素实际上就是实例化一个Node类，通过构造函数对Node类内的key和vlue属性进行赋值，同时还有一个hash函数存储的是元素的hash值，这个值在每次添加函数的时候生成。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

hash()方法 

hash方法被称为扰动函数，它的作用就是使得哈希结果更加均匀，扰动函数的计算方式是将hashcode和无符号右移16位的hashcode后得到的值做异或运算。

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

关于扰动函数为什么是这样计算，这里简单说一下 ，扰动函数设计出来是为了减少hash冲突，使得每个元素分布的更加均匀，java中的int整型的表示范围是-2^31——2^31-1，即-2147483648——2147483647，而HashMap的初始容量为16，每次扩容为原来的二倍，短时间内不会超过2的16次方，这样一来int型的前16位就很少参与到hash值的计算会使得分布不是很均匀，假设一种情况，hashCode是32位int型整数且后16位都是1

1010 1011 0101 0101 1111 1111 1111 1111

计算元素在hashMap中的下标值的算法是hash&(length-1)，hashMap的容量始终为2的n次，length-1的二进制形式是固定的，第一位为0后面几位都是1，假设lengt为16，

16-1二进制 = 01111  ，这样hashCode直接和01111相与就是01111不变，那所有32位int型整数且后16位都是1的hashCode在计算出hash值后都相同分布不均匀，hash冲突概率更大。

hashCode()方法

当调用扰动函数的时候需要调用key值所代表的对象的hashCode方法，如果没有在类中没有重写hashCode方法就会调用Object类的HashCode方法，这个方法在Object类的源码中只有一个方法的声明，但实际还是会返回一个int型整数，这个整数是根据类在内存中的位置记算出来的。

看一个String类的hashCode方法：

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

循环char数组取出字符串的字符，第一次循环h为第一个字符的ascii码，第二次循环h为 31*第一个字符的ascii码+第二个字符的ascii码，后面就重复第二次循环的步骤，最后把h作为hash值返回。

putValue方法

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

常用的put方法就是对putValue方法的包装，直接看putValue方法

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;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    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;
    }

第一个if判断的是hashMap是被初始化过，hashMap初始化后默认长度为16（1左移4位），为什么是16呢？这个也是一个有意思的地方。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

第二个if判段着重看一下if ((p = tab[i = (n - 1) & hash]) == null)，这一行的作用是判断下标位置是否hash冲突了，如果冲突了HashMap使用链地址法+红黑树解决冲突，这个下标是怎么得出的呢？通过hash值与HashMap的长度值做位与运算而且hash值一般都会比hashMap长度大很多，在这里其实是在取余，为什么是取余？根据位运算的原理，一个整数向右移n位就是在除以2的n次，而被移除的n位就是余数，比如：19%8=3

8是2的3次 ，19的二进制是10011右移3位  10011  011被移除011转换10进制就是3，所以我们可以直接从移除的位数计算出取余的结果，8的二进制位1000，7的二进制位0111，7&19=3，发现了，2的n次的二进制第一位总是1其余为0，我们只要减一就会变为出了第一位是零剩下所有位都是1，这样与被模的数向与就可以得到余数了，这也是为什么HashMap的默认容量为16，而且HashMap每次扩容都是2的n次。

那为什么不直接使用取模符号进行运算呢？这个在做一些算法题也会用到，那就是对于计算机来说位运算要比加减乘除这些运算要快。

这个if语句判断这个下标位置是否已经有元素了，没有的话就会向这个下标位置添加元素，如果已经存在元素则会进入else中的代码首先会判断key值是否相同，相同的话就会修改value值，不同的话，相当于发生了hash冲突，这时会使用链表来存储相同下标的元素，而且在JAVA8中当链表的长度大于8时会将链表转换为红黑树来存储元素，具体的转换不分析了跟算法有关了。

总结

简单分析了一下HashMap源码中会经常接触到的方法，分析了putVal函数之后其实对于get方法的实现也能推出大概的实现方式，对于HashMap,HashSet,Hashtable也有了进一步的了解，后续如果有其他需要再深度分析。