HashMap源码解析 一

HashMap继承自AbstractMap类
实现的接口有三种
1、 Map
2、 Cloneable
3、 Serializable
哈希表(HashMap)也叫散列表，是将存储元素（key-value键值对）通过hash算法（即散列函数）映射到表中对应的位置(一个有限的地址区间上)，以此来对元素进行直接访问，加快查找速度的数据结构。
jdk1.8之前采用的是类似下图数组+链表来实现hashMap

image.png

jdk1.8之后采用的就是数组+链表+红黑树的形式实现

image.png

在jdk1.8中，HashMap是采用数组+链表+红黑树的形式实现，其中链表实现如下：

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;
    }
}

可以看到，node中包含一个next变量，这个就是链表的关键点，hash结果相同的元素就是通过这个next进行关联的。
hash()方法：

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

通过key的哈希值来决定放置的位置，这个方法要与以下的一行在put方法里的代码一起看

 tab[(n - 1) & hash]

这行代码中的tab是table，n是map的容量大小，hash是hash()方法返回的值
好，现在我们进行分析一下

image.png

假如hashCode()的值如第一行所示，我们对这个值无符号右移16位之后与它本身异或，获得的结果hash的值如图最后一行所示，发觉高16位的值并没有发生任何改变，改变的是低16位的值，为什么要这样做呢，我们看下下面这张图：

image.png

假设table.length=2^4=16，当我们将hash的结果再与(n-1)进行与操作，发现数组的index仅与hash值的低n位有关，hash值的高位都被与操作置为0了，从而我们得出结论，hash()方法计算将哈希值向右无符号移动16位的目的是为了让高低位都能参与到数组index的位置选择，更大程度上减少了碰撞率。

HashMap的相关属性

image.png
转自链接：https://www.cnblogs.com/ayanami-rei/p/5998097.html

HashMap有四个构造方法（基于jdk1.8）

    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);
    }

    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);
    }

首先讲下 public HashMap(int initialCapacity, float loadFactor) 这个构造方法
先是三个对于初始化容量和负载因子大小的判断，然后对负载因子进行赋值，最后到临界值的赋值，这边调用了方法tableSizeFor(initialCpacity),这个方法的代码如下：

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;
}
这个方法用于找到大于等于initialCapacity的最小的2的幂,为什么容量的大小要是2的幂呢？因为2的幂的值-1的数的二进制表示为11111...,那么在之后的与哈希值的与操作过程中，可以实现均匀分布。
参考链接：https://blog.csdn.net/qq_36523667/article/details/79657400

为什么要对cap做减1操作。int n = cap - 1;
这是为了防止，cap已经是2的幂。如果cap已经是2的幂， 又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。如果n这时为0了（经过了cap-1之后），则经过后面的几次无符号右移依然是0，最后返回的capacity是1（最后有个n+1的操作）。

https://blog.csdn.net/huzhigenlaohu/article/details/51802457
https://blog.csdn.net/wangbiao007/article/details/52372909
https://www.cnblogs.com/ayanami-rei/p/5998097.html