HashMap工作原理

HashMap底层存储结构？

以node的形式存储在散列表中，node中  的属性有  hash,key,value,.next

HashMap底层结构其实就是数组+链表+红黑树

哈希表中如果有冲突，冲突的地方会形成链表，如果冲突数超过8，就会升级成为红黑树

Hashmap的put过程？

1、map.put("无敌","兔子");

2、获取“无敌”这个字符串的hash值

3、经过hash值扰动函数，让这个hash值更加散列

4、构造出Node函数     （其实就是存放key，value、哈希值的一个结点）

5、路由算法，找出node应存放在数组的位置

java8为什么引入红黑树？

就是为了解决链化链得太长的问题

红黑树是一个自平衡的二叉查找树

hashmap的扩容原理？

扩容是为了提高查找的性能，用空间换时间

哈希表中数据存放过多以后，基本上变成了一种线性查询，比如一开始是16,1号位上慢慢变多，可能有5个，那么我找到1号位后还需要在1号位里面的五个中去找。

当我桶位变多，查找也就更快

源码分析：

DEFAULT_INITIAL_CAPACITY    缺省table大小

MAXIMUM_CAPACITY   最大table 容量

DEFAULT_LOAD_FACTOR  缺省负载因子

TREEIFY_THRESHOLD  树化阈值

UNTREEIFY_THRESHOLD 树降级成为链表的阈值

MIN_TREEIFY_CAPACITY 树化的另一个参数，当hash表中的元素个数超过64时 才允许树化

size  当前哈希表元素个数

modcount 结构修改次数

threshold扩容阈值 当你的哈希表中元素超过阈值，扩容

loadFactor负载因子       

threshould = capacity（数组容量）* loadFactor 

首先盘有两个参数的构造函数，前两个if其实就是做了一些校验，保证capacity必须大于零 最大值是MAX_CAP

threshold扩容阈值 在构造函数中  这个数字必须是2的次方数 tableSizeFor()

hash方法：

key如果等于null  那么hash值直接就是0

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

在put时会将key再哈希一 下   在table长度还不是很高的时候 让高16位也能参与进来

HashMap的putVal方法：插入一个新的键值对，如果该键存在，则用新值覆盖旧值，方法返回值为旧值，如果该键不存在，方法返回值为null。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//hash代表key的hash值//k是key//tab引用当前hashmap的散列表//p:代表当前散列表中的元素//n:表示散列表数组的长度//i：表示路由寻址结果Node<K,V>[] tab; Node<K,V> p; int n, i;//延迟初始化逻辑，第一次调用putVal时会初始化hashmap对象中最耗费内存的散列表if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//最简单的一中情况，寻找到的桶位是null 这时候直接将当前键值扔进去即可if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {//e  node临时元素  部位null的时候 找到了一个与当前要插入的key—value一直的key的元素//k  标识临时的一个keyNode<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) {//如果next指向null  说明迭代到了最后一个元素，也没找到 与需要插入的元素一直的node//说明需要加入到当前链表的末尾if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//条件成立的话  说明当前链表达到树化标准了  需要树化treeifyBin(tab, hash);break;}//哈希值与key值都一致 说明你找到了  需要替换if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

resize（）扩容方法

final Node<K,V>[] resize() {//扩容以前的哈希表Node<K,V>[] oldTab = table;//表示扩容之前table数组的长度int oldCap = (oldTab == null) ? 0 : oldTab.length;//扩容之前的扩容阈值，触发本次扩容的阈值int oldThr = threshold;// newCap扩容之后的table数组大小//newThr 扩容之后下次再次触发扩容的条件int newCap, newThr = 0;//条件如果成立  说明hashmap中散列表已经初始化过了  就是一次正常扩容的情况if (oldCap > 0) {//扩容之前的table数组大小已经达到最大阈值，则不扩容，且设置扩容条件为int的最大值（表示绝了扩容的后路）if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//newCap 左移一位 实现数值翻倍  并且赋值给newCap  newCap小于数组最大值限制，且扩容之前的阈值大于等于16  这种情况下//则下次扩容的阈值 等于当前阈值翻倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//oldCap等于0的情况  说明散列表还没有初始化过else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaults//此处是 oldThr 和oldCap都等于0newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {//通过newCap跟loadFactor计算出一个newThrfloat ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//前面的一大堆代码只做了两件事  就是计算出下面两个值// newCap扩容之后的table数组大小//newThr 扩容之后下次再次触发扩容的条件//接下来做扩容   就是创建一个大一倍的数组 然后把小数组的内容倒入到大数组中threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})//创建出一个更长更大的数组Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {//说明hashmap中 本次扩容之前可能会有数据  table 不为nullfor (int j = 0; j < oldCap; ++j) {//当前node节点Node<K,V> e;//把头结点复制给了e  如果e不等于null  说明这个桶位中有数据 接下来应该判断他是链表还是树还是单个数据if ((e = oldTab[j]) != null) {//将头结点置空  方便jvm回收oldTab[j] = null;//说明是单个元素  没有发生过碰撞if (e.next == null)//直接计算出当前元素应存放在新数组中的位置，然后扔进去即可newTab[e.hash & (newCap - 1)] = e;//说明是红黑树else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//说明是链表else { // preserve order//他会这样处理   位于15的元素  一半放在了新表的15   一半放在了新表的31 因为第五位可能是0也可能是1//低位链表  存放扩容之后的下标位置，与当前数组的下标位置一致Node<K,V> loHead = null, loTail = null;//高位链表  存放扩容之后的下标位置 等于当前数组下标位置加上扩容前的数组长度Node<K,V> hiHead = null, hiTail = null;//定义了两个链表//指向下一个元素的指针Node<K,V> next;do {next = e.next;//hash->.....1 1111//hash->.... 0 1111  意思是不可能存在相同的//然后此时oldCap 一定是 10000//所以这里  只可能有两种方式  一种是1跟1做与运算   一种是 1跟0做与运算//如果结果是0 那么放在loHead中if ((e.hash & oldCap) == 0) {//如果头结点为null  说明还没有过元素  成为头结点if (loTail == null)loHead = e;else//如果头结点已经存在  则成为尾结点loTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;}}}}}return newTab;
}

关于get方法

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode()方法

final Node<K,V> getNode(int hash, Object key) {//tab: 引用当前hashMap的散列表//first 桶位中的头元素//e 临时node元素//n: table数组长度Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//说明里面有数据if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//说明要找的就是头元素   直接返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;//找下一个元素 看是不是if ((e = first.next) != null) {//如果他是树形if (first instanceof TreeNode)//调用getTreeNode方法查找return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {//如果他是链式结构   那就一个一个找 如果键完全相等 就返回if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}//匹配不到就返回nullreturn null;
}

remove()方法

final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {//tab引用当前hashmap中的散列表//n  散列表数组长度//index  寻址结果Node<K,V>[] tab; Node<K,V> p; int n, index;//先判断tab里面是否有值  如果没有值 直接返回nullif ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {//p现在指向了 某一个桶位   并且该桶位是有数据的  需要进行查找操作 并删除//node 表示查找结果   e表示当前node的下一个元素Node<K,V> node = null, e; K k; V v;//p的哈希值与要删除的值得哈希值是一致的 这就是我们要找的结果if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;//头结点并不是要找的元素else if ((e = p.next) != null) {//判断它是否树化if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {//不是树就是链表 根据链表结构来一个个找do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode)  //如果是树((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p)tab[index] = node.next;else //是链表p.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;
}

replace方法

public boolean replace(K key, V oldValue, V newValue)

先用key找到节点位置  然后用新值替换旧值

HashMap全B站最细致源码分析课程，看完月薪最少涨5k！_哔哩哔哩_bilibili