理解hashMap

优点：

1、因为链表对内存空间的连续性和顺序性没有要求，所以它可以充分利用内存空间，并且这一特点还造就了链表可以不必预先知道数据的大小，更加灵活。

2、链表插入和删除数据速度快，只需要修改相邻节点的指针域就行。

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments. //就是说我们可以通过构造函数来创建指定容量的hashMap
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30; //2的30次幂
最大容量， 

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认负载因子0.75

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;
JDK 1.8后， 由链表结构转换为红黑树结构的阙值，链表长度大于8时转为红黑树，查找速度更快

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
static final int UNTREEIFY_THRESHOLD = 6;
扩容过程中， 如果红黑树长度小于6， 将由红黑树转为链表

/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 */
static final int MIN_TREEIFY_CAPACITY = 64;
红黑树的最小容量为64， 超过64将对hashmap进行扩容

构造方法：

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

默认负载因子0.75， 数组容量16

/**
 * 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; //数组容量最大为2的30次幂
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) //传入的数组容量和负载因子都不能小于0
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

注意这里计算阙值的方法，

threshold = tableSizeFor(initialCapacity)

/**
 * Returns a power of two size for the given target capacity.
 */
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;
    int ss = (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
该方法会返回一个为2的n次幂， 大于等于给定容量cap且小于最大容量的数， 如：

 这里有一点搞不明白， 在阙值的定义中，我们看到阙值等于容量*负载因子

/**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial
 */
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;

那为什么在构造函数里要这样计算阙值呢？
------继续看源码找到了答案： 构建hashMap对象时并不会去初始化或者扩容table, 所以这里的threshold只是一个初始阙值， 当我们首次调用put方法添加键值对的时候，会调用resize（）方法来初始化， 同时计算阙值=容量*负载因子

（摘自 【java】HashMap 一遍就懂！！！！_疯-CSDN博客_hashmap 仅作个人笔记使用，感谢博主）

• HashMap的put实现

当我们创建了一个HashMap之后， 不管增加，删除，修改，查找键值对。首先最重要的一点就是确定数组索引位置

 前面说过， HashMap是数组+链表的存储方式， 所以我们当然希望这个hashMap里的元素分布尽量均匀， 每个数组索引下的元素只有一个， 这样就不用遍历列表。所以在我们put数据时， 确定它对应的数组索引至关重要。

看源码(方法一 + 方法二)：

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。

方法一： 若key为null，则直接返回0，否则通过h = key.hashCode()计算出key的hashcode，然后返回h ^ (h >>> 16)的值。h >>> 16为无符号向右移动16位，移位之后，h的高16位全部变成了0，计算过程如下：

这样做的好处是，低位的信息中混入了高位的信息，这样高位的信息被变相的保留了下来，而且，HashMap已经使用了红黑树对table中的节点碰撞做了处理，因此我们只是以最简单的方式做一些移位，然后进行异或运算。采用这种计算方式，是在速度、性能、分布上做的一个平衡，掺杂的元素多了，那么生成的哈希值的随机性会增大。我们可以看这么一个例子：

 运行结果：

haseCode & (capacity - 1)是用来计算节点对应的数组下标，我们后面会介绍。可以看到如果直接使用key的hashcode作为节点的哈希值，计算出来的三个几点处于同一位置，这就产生了哈希冲突，而如果我们使用h ^ (h >>> 16)作为哈希值，计算出来的三个节点的位置都不相同，也就是说这种方式计算出的哈希值随机性更大，能使节点的分布更加均匀。

这也正好解释了为什么HashMap的数组长度要取2的整次幂。因为数组长度-1正好相当于一个“低位掩码”。这个掩码和节点的哈希值进行与操作的结果就是哈希值的高位全部归零，只保留低位值，用来做数组下标访问。同时，capacity - 1的二进制表示中的最后一位是1，这样便保证了haseCode & (capacity - 1)的最后一位可能为0，也可能为1，即计算出的下标可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，若capacity - 1的二进制表示中的最后一位是0，则计算出的下标都是偶数，所有奇数下标都没有被使用，不仅不均匀，而且还浪费了一半空间。

————————————————
版权声明：本文为CSDN博主「DivineH」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_38293564/article/details/80688474

对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。

这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

 明白了如何确定数组下标之后，我们来看看put的执行过程：

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

• HashMap的get实现： 首先对key做hash运算， 得到数组索引， 然后调用getNode方法获得对应节点

 这里需要注意的是，get(Object)方法返回结果为null并不是说HashMap中没有对应key的映射，因为HashMap中key和value都允许为null，这也有可能是key对应的value为null。

• HashMap的remove方法

先对key做hash运算得到数组下标， 然后再调removenode方法删除节点

 remove(Object)方法调用removeNode方法，设置的value为null，matchValue为false，这表明，不需要key和value全部匹配才删除节点，只要key匹配就可以删除了。

• HashMap的containsKey()和ContainsValue()方法

因为hashMap中允许一个键值对的key为null, 多个键值对的value为null, 所以我们不能用getObject(key)是否为null来判断key是否存在, 而应该使用containsKey

 若该key存在， 无论它对应的value是否为null, 但node节点不为null

 从上面代码可以看到， containsValue方法会遍历整个哈希表， 所以---慎用