debug熟悉HashMap的源码
- 1、新建HashMap，添加第一个数据时
- - （1）执行`new HashMap<>();`
  - （2）执行`map.put(key,value);`方法
- 2、添加后续数据
- - (1) 添加完数据之后，`map.size`小于阈值
  - - <1> 未发生hash冲突时,直接添加成功
    - <2> 发生hash冲突时
  - (2) 添加完数据之后，`map.size`大于阈值
  - - <2> 当容器存储数据量达到阈值时
- 3、关于树化和树化节点的扩容

debug熟悉HashMap的源码

1、新建HashMap，添加第一个数据时

（1）执行 `new HashMap<>();`

调用构造器，设置负载因子为默认负载因子（0.75）： static final float DEFAULT_LOAD_FACTOR = 0.75f;

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

（2）执行 `map.put(key,value);` 方法

put() 方法调用 putVal()

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

计算hash：

如果 key 为 null ，则设置 key 的 hash = 0
如果不为 null ，则调用 String.hashCode() 方法计算hash值（ Object.hashCode() —> 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;
}

然后将计算得到的hash和无符号右移16位之后的hash进行异或（ ^ ）运算，再和本身异或，得到最后的hash值

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

执行

putVal()

首先会判断是不是新建的 HashMap ，如果是，此时会调用 resize() 初始化

//putVal()
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

resize() 使用到的部分：
- transient Node<K,V>[] table; 这里面的table就是 HashMap 存储数据的容器
- 默认容量： static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
- 负载因子： static final float DEFAULT_LOAD_FACTOR = 0.75f;
- newThr ：初始化获得的阈值为12

//resize()
else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

threshold = newThr;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//因为newTab为null，返回newTab
return newTab;

初始化存储容器之后，会计算数据的存储位置：

(n - 1) & hash

,并判断该位置上是否已经有元素

我们是第一次添加，此时是没有元素的，所以直接将元素放在该位置上

//putVal()
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
/*
	Node是HashMap上存储数据的节点
    // Create a regular (non-tree) node
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }
*/

然后给统计修改次数（hash计算次数）的计数器自增1： ++modCount;

putVal() 结束， put() 结束，存储完成

2、添加后续数据

(1) 添加完数据之后， `map.size` 小于阈值

<1> 未发生hash冲突时,直接添加成功

//putVal()
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

<2> 发生hash冲突时

会判断是否已经有相同的 key ,如果相同会把之前的 Node 节点覆盖

//p = tab[i = (n - 1) & hash]
Node<K,V> e; K k;
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

然后会判断是否为树节点，如果是，则将值存在红黑树中

else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

如果都不是，则将新的 Node 挂到该位置上的节点之后

else {
    for (int binCount = 0; ; ++binCount) {
        //判断当前位置的节点是否有子节点
        if ((e = p.next) == null) {
            //如果没有子节点，则在将新节点挂在p->next上
            p.next = newNode(hash, key, value, null);
            //判断是否大于树化的阈值，如果大于则进行树化操作
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        //判断子节点的key是否和新的节点的key相同，如果相同则直接结束循环，覆盖掉之前的值
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        //如果当前有子节点，则通过循环将新节点挂在子节点的next上
        p = e;
    }
}

(2) 添加完数据之后， `map.size` 大于阈值

<2> 当容器存储数据量达到阈值时

if (++size > threshold)
    resize();

调用 resize() 扩容
- 如果当前容量达到默认的最大容量，则将阈值调到Integer类型的最大值，不改变最大容量
```
if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
}
           
```
- 如果没有达到最大容量，则将容量按位右移一位（扩大2倍），并将阈值按位右移一位（扩大2倍）
```
else if ( (newCap = oldCap << 1) < MAXIMUM_CAPACITY 
          && oldCap >= DEFAULT_INITIAL_CAPACITY)
     newThr = oldThr << 1; // double threshold
           
```
- 扩容完成后，先将数据拷贝，然后再将拷贝的数据迁移到新数组的相应位置（迁移过程中一个很巧妙的算法： (e.hash & oldCap) == 0 ，当为0时，数据节点不需要移动位置，不为0 时，则将节点向后移动一个旧容量的长度的位置，具体算法理解起来有些复杂，建议百度看大佬的分析）
- 迁移过程中判断是否有子节点，是否为树的根节点
  - 如果有子节点，且转化为红黑树，则通过 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 来完成数据的迁移
  - 如果有子节点，且子节点没有转化为红黑树，则执行以下操作：
    - 定义的两中含义不同的 Node ： lo 和 hi ， lo 节点是放到原位置， hi 节点是放到偏移之后的位置
```
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
           
```
    - 数据拷贝（拿一种情况来分析，因为存储位置是否偏移对数据拷贝无影响）
```
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
        	loHead = e;
        else
        	loTail.next = e;
    	loTail = e;
    }
    else {
        if (hiTail == null)
        	hiHead = e;
        else
        	hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
           
```
    - 数据迁移
```
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}
           
```
以上步骤会执行旧容量大小的次数来将所有数据迁移到数组中，迁移完成之后将新的数组返回

3、关于树化和树化节点的扩容

红黑树部分内容暂时还未深入学习，涉及到红黑树这个数据结构，等深入学习到红黑树原理时再深挖这一块

treeifyBin(tab, hash);	//树化
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);	//扩容

HashMap原理学会了吗？（HashMap存储及扩容）debug熟悉HashMap的源码

目录

debug熟悉HashMap的源码

1、新建HashMap，添加第一个数据时

（1）执行 `new HashMap<>();`

（2）执行 `map.put(key,value);` 方法

2、添加后续数据

(1) 添加完数据之后， `map.size` 小于阈值

<1> 未发生hash冲突时,直接添加成功

<2> 发生hash冲突时

(2) 添加完数据之后， `map.size` 大于阈值

<2> 当容器存储数据量达到阈值时

3、关于树化和树化节点的扩容

继续阅读

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

软件测试工程师跳槽：收到面试电话后，我会做的事。

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method

HashMap原理学会了吗？（HashMap存储及扩容）debug熟悉HashMap的源码

目录

debug熟悉HashMap的源码

1、新建HashMap，添加第一个数据时

（1）执行 new HashMap<>();

（2）执行 map.put(key,value); 方法

2、添加后续数据

(1) 添加完数据之后， map.size 小于阈值

<1> 未发生hash冲突时,直接添加成功

<2> 发生hash冲突时

(2) 添加完数据之后， map.size 大于阈值

<2> 当容器存储数据量达到阈值时

3、关于树化和树化节点的扩容

继续阅读

（1）执行 `new HashMap<>();`

（2）执行 `map.put(key,value);` 方法

(1) 添加完数据之后， `map.size` 小于阈值

(2) 添加完数据之后， `map.size` 大于阈值