面试被问到HashMap 底层原理?看完这边文章绝对不慌！

快速入门

存储：put 方法 put(key,value)
查询 : get 方法 get(key)
java 代码如下

import java.util.HashMap;
import java.util.Map;
public class App {
public static void main(String[] args) {

Map<String,String> map = new HashMap<>();

map.put("刘一","刘一");

map.put("陈二","陈二");

map.put("张三","张三");

map.put("李四","李四");

map.put("王五","王五");

map.put("Money","我是猴哥Money老师");

System.out.println(map.get("Money"));

}

}

//输出结果：我是猴哥Money老师

技术的本质，底层结构

程序是等于我们的数据结构和算法
在这里插入图片描述

HashMap 其实就是做存储的，做存储的就是数据结构

在JDK7 : HashMap 是由数组，链表组成的
在JDK8: HashMap 是由数组，链表，红黑树组成的

存储是按上面的规则存储的，那查询是怎么查的了

算法：哈希算法

既然要了解HashMap 的组成，就谈谈它的结构组成

首先我们来说下数组，数组在java 中是怎么定义的了

    //数组：采用一段连续的存储单元来存储数据的
    //数组的特点: 查询时间复杂度:0(1) ,删除,插入,时间负责度0(N),总结：查询块，插入慢
    public static void main(String [] args){
   
        //数组的定义：初始化长度为10，数据类型Integer ,
        Integer integer[] = new Integer[10];
        //指定下标，复制
        integer[0]=0;
        //指定下标，复制
        integer[1]=1;
        //指定下标，复制
        integer[9]=2;
        //指定下标，复制
        integer[9]=400;
        System.out.println(integer[9]);
    }
    // 输出结果：400

数组结构如图：
在这里插入图片描述
查询：时间复杂度 0（1）,查询非常快的
删除，插入：时间复杂度0（N）非常慢的，效率没有查询那么快

为什么查询快，插入，删除慢了？

查询快

是因为我们数组了都有一个序号,如图，0,1,2,3,4,5,… ，如果要找到下标为3的数据值, 这些序号其实就是他们的下标地址，可以理解为他们的一个下标索引，这个下标是连续的，是自增的，所以我们立马可以确定3个这个位置，根据这个索引3 找到它对应的节点。

插入，删除慢

假如我现在要出入一个Monkey 的数据，插入到3和4之间，如图
存在这个位置我们是没有下标的，则我们的下标4 则要移到 Monkey 那个位置，5下标就移到4那个位置，如图：

类似，我们后面的下标都要向左移动，这样我后面的数据是不是要做很大的改动，这样时间复杂度则为0（N），这样就保证了我们数组的连续性，同理删除的话如图：

数组后面数据的下标，都要还原成之前插入前的下标，后面的节点都要改变，这样我们可以看出，这就是数组，删除，插入为什么这么慢！
除非是插入，删除，数组的最后一个元素，大家懂了吗？还不懂那就私聊！

扩充：
大家知道我们java 哪一个类，底层用的就是数组？
在我们的java.util 包下面有一个ArrayList 类，如图
在这里插入图片描述
怎么验证了？
我们查看它的add 方法

   public boolean add(E var1) {
        this.ensureCapacityInternal(this.size + 1);
        this.elementData[this.size++] = var1;
        return true;
    }

如果面试被问到ArrayList 的特性，直接回答查询快，插入，删除慢

为什么HashMap 用到数组存储了，还要用到链表了？

谈谈什么是链表？
在java 中是这么定义的：

package node;
import com.sun.org.apache.bcel.internal.generic.IMPDEP1;
public class Node {
   
<span class="token keyword">public</span> <span class="token class-name">Node</span> next<span class="token punctuation">;</span>
<span class="token keyword">private</span> <span class="token class-name">Object</span> data<span class="token punctuation">;</span>


<span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token class-name">Object</span> next<span class="token punctuation">)</span> <span class="token punctuation">{

   
    <span class="token keyword">this</span><span class="token punctuation">.</span>data <span class="token operator">=</span> next<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">//链表：链表是一种物理存储单元上非连续，非顺序的存储结构</span>
<span class="token comment">//特点: 插入，删除时间复杂度0(1) 查找遍历时间复杂度0(N) 总结：插入快,查询慢</span>
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span><span class="token punctuation">{

   
    <span class="token class-name">Node</span> head <span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token string">"monkey"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    head<span class="token punctuation">.</span>next <span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token string">"张三"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    head<span class="token punctuation">.</span>next<span class="token punctuation">.</span>next <span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token string">"刘一"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>data<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">.</span>data<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">.</span>next<span class="token punctuation">.</span>data<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

}

//输出结果:

//monkey

//张三

//刘一

链表：链表是一种物理存储单元上非连续，非顺序的存储结构,如图：
在这里插入图片描述
为什么它插入，删除快，查询慢了？
删除某个节点，只需要上一个节点 head.next =null
插入某个几点，只需要上一个节点 head.next 指向插入的节点，插入的节点指向下一个节点
查询某个节点：链表查询都要通过头节点，比如我们要查‘刘一’，我们则要先查头monkey,再查张三，再查到刘一，
虽然只有3个节点，但是我们要查到刘一要查三次，把整个链表都遍历了一次，所以查询慢！
在这里插入图片描述
扩充
在我们java 中，哪一个util 类采用的链表来实现的?

我们来查看它的add 方法

   public boolean add(E var1) {
   
        this.linkLast(var1);
        return true;
    }
    //看上面有一个linkLast,如下:
void linkLast(E var1) {
   
    <span class="token class-name">LinkedList<span class="token punctuation">.</span>Node</span> var2 <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>last<span class="token punctuation">;</span>
    <span class="token class-name">LinkedList<span class="token punctuation">.</span>Node</span> var3 <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">LinkedList<span class="token punctuation">.</span>Node</span><span class="token punctuation">(</span>var2<span class="token punctuation">,</span> var1<span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token class-name">LinkedList<span class="token punctuation">.</span>Node</span><span class="token punctuation">)</span><span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>last <span class="token operator">=</span> var3<span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>var2 <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{

   
        <span class="token keyword">this</span><span class="token punctuation">.</span>first <span class="token operator">=</span> var3<span class="token punctuation">;</span>
    <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{

   
        var2<span class="token punctuation">.</span>next <span class="token operator">=</span> var3<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token operator">++</span><span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">;</span>
    <span class="token operator">++</span><span class="token keyword">this</span><span class="token punctuation">.</span>modCount<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token comment">//看上面有一个Node,如下:</span>
<span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token keyword">class</span> <span class="token class-name">Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">&gt;</span></span> <span class="token punctuation">{

   
    <span class="token class-name">E</span> item<span class="token punctuation">;</span>
    <span class="token class-name">LinkedList<span class="token punctuation">.</span>Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">&gt;</span></span> next<span class="token punctuation">;</span>
    <span class="token class-name">LinkedList<span class="token punctuation">.</span>Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">&gt;</span></span> prev<span class="token punctuation">;</span>

    <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token class-name">LinkedList<span class="token punctuation">.</span>Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">&gt;</span></span> var1<span class="token punctuation">,</span> <span class="token class-name">E</span> var2<span class="token punctuation">,</span> <span class="token class-name">LinkedList<span class="token punctuation">.</span>Node</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">&gt;</span></span> var3<span class="token punctuation">)</span> <span class="token punctuation">{

   
        <span class="token keyword">this</span><span class="token punctuation">.</span>item <span class="token operator">=</span> var2<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> var3<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>prev <span class="token operator">=</span> var1<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
  <span class="token comment">//上面有一个next,有一个prev </span>
  <span class="token comment">//这是一个双向链表</span>

双向链表如图: 类似与分页，上一页，下一页，下面的对象也可以获取上面对象的数据（head.prev）
在这里插入图片描述
现在大家都已经了解JDK7 HashMap 数据结构了，开始了解下算法！

哈希算法

那么HashMap 是怎么去存储的了？他是如何将数据放到我们的数组和链表上的？
用的就是哈希算法，你们知道哈希算法的底层是怎么实现的？
哈希表

什么是哈希算法？
哈希算法（也叫散列），就是把任意长度值（key）通过散列算法变换成固定长度的key(地址)，通过这个地址进行访问的数据结构，
它通过把关键码值映射到表中一个位置来访问记录，以加快查找速度。
在这里插入图片描述
例如图中的John Smith 通过散列算法变换成固定长度的key:152 （永远是152），然后通过152 变成John Smith 是不可能的，哈希算法是不可逆的。
HashCode: 通过字符串算出它的ascii 码，进行mod(取模)，算出哈希表中的下标
在这里插入图片描述
代码如下：

public class AsciiCode {
   
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{

   
    <span class="token keyword">char</span> c <span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token operator">=</span><span class="token string">"lies"</span><span class="token punctuation">.</span><span class="token function">toCharArray</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> c<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{

   
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token punctuation">(</span>c<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">+</span><span class="token string">":"</span> <span class="token operator">+</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span>c<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

}

//输出结果：

//l:108

//i:105

//e:101

//s:115

将 lies 算出来的ascii 码相加
然后除以10 取模（为什么取模不直接存储 429了）
为什么取模不直接存储 429了？
//数组是采用一段连续的存储单元来存储数据的，那存lies 数据将如图：

如果你要存lies 则需要300 个这样的内存空间，所以我们取模为10，算出来的值为 9，则节省了很多空间，我们取模的目的就是节省内存空间！

如果我们取模会出现什么问题
会出现hash 冲突(碰撞)的一个问题,

什么是hash冲突

lies 的值通过ascii 码计算的总和为 429
foes 的值通过ascii 码计算的总和也为 429

两个单词取模后的值都是 9 ，则lies 会存在下标为9 的这个位置，foes 也存在下标为9 的这个位置，而数组存在同一个下标下面是会覆盖的（上面代码讲数组的时候Intergers[9]=400,会覆盖Intergers[9]=2 的值，最终Intergers[9] =400）,同样我们先存的是lies 后存的是foes,则lies
将会被覆盖，lies 和foes 是不同的key, 我们HashMap 是可以存这两个值的，为什么没有被覆盖了？这个地方就叫做哈希碰撞！

Hash冲突怎么解决了
我们用链表来解决这个问题, 链表是有一个指针的，我们可以让这个lies 指向这个foes,我们让foes 去匹配下标为9 的这个节点，如果匹配lies 不相等，则去匹配下一个节点foes,最终就会找到这个foes,这就是我们hash 算法底层的原理及解决冲突。

不调用JDK7 的HashMap,自己手动写一个HashMap


public class App {
   
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{

   
   <span class="token comment">//Map&lt;String,String&gt; map = new HashMap&lt;&gt;();</span>
    <span class="token class-name">App</span> map <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">App</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    map<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token string">"刘一"</span><span class="token punctuation">,</span><span class="token string">"刘一"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    map<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token string">"陈二"</span><span class="token punctuation">,</span><span class="token string">"陈二"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    map<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token string">"张三"</span><span class="token punctuation">,</span><span class="token string">"张三"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    map<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token string">"李四"</span><span class="token punctuation">,</span><span class="token string">"李四"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    map<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token string">"王五"</span><span class="token punctuation">,</span><span class="token string">"王五"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    map<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token string">"Money"</span><span class="token punctuation">,</span><span class="token string">"我是猴哥Money老师"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">//System.out.println(map.get("Money"));</span>
<span class="token punctuation">}</span>

public void put(String key,String value){
   
System.out.printf("key:%s:::::::::::::::;::hash值:%s:::::::::::::::::::存储位置:%s\r\n",key,key.hashCode(),Math.abs(key.hashCode() % 15));

}

}

//输出结果:

// key:刘一:::::::::::::::;::hash值:671464:::::::::::::::::::存储位置:4

// key:陈二:::::::::::::::;::hash值:1212740:::::::::::::::::::存储位置:5

// key:张三:::::::::::::::;::hash值:774889:::::::::::::::::::存储位置:4

// key:李四:::::::::::::::;::hash值:842061:::::::::::::::::::存储位置:6

// key:王五:::::::::::::::;::hash值:937065:::::::::::::::::::存储位置:0

// key:Monkey:::::::::::::::;::hash值:-1984628749:::::::::::::::::::存储位置:4

我们多次运行，运行的结果还是这样，这就是hash 算法的一个特点：它是一个幂等性的一个算法

模拟我们是怎么存值的
我们一组数据就是 key,value , 可以用string,int 来存吗？这里显然不能，我们一般存这种值一般用对象来存值，我在这里随便命名用个Object或者叫Entry 对象，其实我们还要存另外两个值？（hash和next），当发生hash 冲突的时候（存储位置4） next 可以指向下一个节点，hash 值是用来比较的,比较hashCode 值是否相等！

存取结构图如下：

上面的图形结构，我们就知道如何存数据了！

那我们该如何取数据了？
-假如我们要取‘刘一’ 的值

我们通过get(key) 方法获取数据的模，然后根据key,与hashCode 的值去比较下标为4 的key 和hashCode,查看是否相等，如果不相等我们通过next 方法比较下一个节点的数据，直到 key 与hashCode 对比的值都相等，此时，获取value的值就是当前key 所对应的value!

HashMap 底层如何实现的了？我们用写源码的方式验证

模拟java HashMap

定义一个Map 接口

/** * 自己手动定义Map * @param <K> * @param <V> */
public interface Map<K,V> {
   
<span class="token class-name">V</span> <span class="token function">put</span><span class="token punctuation">(</span><span class="token class-name">K</span> k<span class="token punctuation">,</span><span class="token class-name">V</span> v<span class="token punctuation">)</span><span class="token punctuation">;</span>

<span class="token class-name">V</span> <span class="token function">get</span><span class="token punctuation">(</span><span class="token class-name">K</span> k<span class="token punctuation">)</span><span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

 <span class="token keyword">interface</span>  <span class="token class-name">Entry</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">{

   
  <span class="token class-name">K</span> <span class="token function">getKey</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token class-name">V</span> <span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
 <span class="token punctuation">}</span>

}

定义一个实现Map 的HashMap

import sun.management.snmp.jvmmib.JvmRTInputArgsTableMeta;
/** * 自己定义HashMap * @param <K> * @param <V> */

public class HashMap<K,V> implements Map<K,V>{
   
<span class="token comment">//存储元素对象</span>
<span class="token keyword">private</span> <span class="token class-name">Entry</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">&gt;</span></span> table<span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

<span class="token comment">//扩容初始化</span>
<span class="token keyword">int</span> size <span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>

<span class="token comment">//初始化存储元素对象大小</span>
<span class="token keyword">public</span> <span class="token class-name">HashMap</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{

   
    <span class="token keyword">this</span><span class="token punctuation">.</span>table <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Entry</span><span class="token punctuation">[</span><span class="token number">16</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">/** * 1.通过key hash 算法算出hash值,然后取模 * 2.取模后就有对应的index 数组下标,然后存储对象&lt;Entry&gt; * 3.判断当前对象是否为空，如果空，直接存储， * 4.如果不为空，我们就要用到next 链表 * 5.返回当前这个节点 * @param k * @param v * @return */</span>
<span class="token annotation punctuation">@Override</span>
<span class="token keyword">public</span> <span class="token class-name">V</span> <span class="token function">put</span><span class="token punctuation">(</span><span class="token class-name">K</span> k<span class="token punctuation">,</span> <span class="token class-name">V</span> v<span class="token punctuation">)</span> <span class="token punctuation">{

   
   <span class="token keyword">int</span> index <span class="token operator">=</span> <span class="token function">hash</span><span class="token punctuation">(</span>k<span class="token punctuation">)</span><span class="token punctuation">;</span>
   <span class="token class-name">Entry</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">&gt;</span></span> entry <span class="token operator">=</span> table<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">;</span>
   <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token keyword">null</span> <span class="token operator">==</span>entry<span class="token punctuation">)</span><span class="token punctuation">{

   
       <span class="token comment">//刘一，陈二，李四，王五 就开始存在这个entry,每个entry 对象则存储到了对应table 中</span>
       table<span class="token punctuation">[</span>index<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Entry</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span>k<span class="token punctuation">,</span> v<span class="token punctuation">,</span> index<span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
       size<span class="token operator">++</span><span class="token punctuation">;</span>
   <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{

   
       <span class="token comment">//冲突了，张三，Monkey</span>
       table<span class="token punctuation">[</span>index<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Entry</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span>k<span class="token punctuation">,</span> v<span class="token punctuation">,</span> index<span class="token punctuation">,</span> entry<span class="token punctuation">)</span><span class="token punctuation">;</span>
   <span class="token punctuation">}</span>
    
    <span class="token keyword">return</span> table<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">private</span> <span class="token keyword">int</span> <span class="token function">hash</span><span class="token punctuation">(</span><span class="token class-name">K</span> k<span class="token punctuation">)</span> <span class="token punctuation">{

   
    <span class="token comment">//HashMap 底层用到的是移位的操作，性能高很多 &gt;&gt;,我们这里就直接取模</span>
    <span class="token keyword">int</span> index <span class="token operator">=</span>k<span class="token punctuation">.</span><span class="token function">hashCode</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token number">16</span><span class="token punctuation">;</span>
    <span class="token comment">//Math.abs(index);</span>
    <span class="token keyword">return</span> index<span class="token operator">&gt;</span><span class="token number">0</span><span class="token operator">?</span>index<span class="token operator">:</span><span class="token operator">-</span>index<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">/** * 1.通过 key 进行hash 运算，取模，找到数组对应的下标 index * 2.判断当前对象是否为空,如果不为空 * 3.判断是否相等，如果不相等 * 4.判断next 是否为空，如果不为空， * 5.再判断相等，知道相等为止，或者为空为止 * 6.然后返回 * * * * @param k * @return */</span>
<span class="token annotation punctuation">@Override</span>
<span class="token keyword">public</span> <span class="token class-name">V</span> <span class="token function">get</span><span class="token punctuation">(</span><span class="token class-name">K</span> k<span class="token punctuation">)</span> <span class="token punctuation">{

   
    <span class="token comment">//如果没有存储数据那size 为0，也不用查了，直接返回null</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>size <span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{

   
        <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">int</span> index <span class="token operator">=</span> <span class="token function">hash</span><span class="token punctuation">(</span>k<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token class-name">Entry</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span> <span class="token class-name">V</span><span class="token punctuation">&gt;</span></span> entry <span class="token operator">=</span> <span class="token function">findValue</span><span class="token punctuation">(</span>table<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">,</span> k<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">//通过index 找打这个对象</span>
    <span class="token keyword">return</span> entry<span class="token operator">==</span><span class="token keyword">null</span><span class="token operator">?</span><span class="token keyword">null</span><span class="token operator">:</span>entry<span class="token punctuation">.</span><span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">/** * * @param entry * @param k 查询刘一 * @return */</span>
<span class="token keyword">private</span> <span class="token class-name">Entry</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">&gt;</span></span> <span class="token function">findValue</span><span class="token punctuation">(</span><span class="token class-name">Entry</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">&gt;</span></span> entry<span class="token punctuation">,</span><span class="token class-name">K</span> k<span class="token punctuation">)</span> <span class="token punctuation">{

   
    <span class="token comment">//存的可能是数值类型，也可能是字符串类型</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>k<span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>entry<span class="token punctuation">.</span><span class="token function">getKey</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">||</span> k <span class="token operator">==</span> entry<span class="token punctuation">.</span><span class="token function">getKey</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{

   
        <span class="token keyword">return</span> entry<span class="token punctuation">;</span>
        <span class="token comment">//如果不相等，估计这个节点是个链表，判断它next 数据是否匹配</span>
    <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{

   
        <span class="token keyword">if</span><span class="token punctuation">(</span>entry<span class="token punctuation">.</span>next <span class="token operator">!=</span><span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">{

   
            <span class="token comment">//用到递归，在链表里面一直查询这个k,值是否相等</span>
            <span class="token keyword">return</span> <span class="token function">findValue</span><span class="token punctuation">(</span>entry<span class="token punctuation">.</span>next<span class="token punctuation">,</span>k<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token annotation punctuation">@Override</span>
<span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{

   
    <span class="token keyword">return</span> size<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>



<span class="token keyword">class</span> <span class="token class-name">Entry</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">&gt;</span></span> <span class="token keyword">implements</span> <span class="token class-name">Map<span class="token punctuation">.</span>Entry</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">{

   
     <span class="token comment">//存四个值</span>
    <span class="token class-name">K</span> k<span class="token punctuation">;</span>
    <span class="token class-name">V</span> v<span class="token punctuation">;</span>
    <span class="token keyword">int</span> hash<span class="token punctuation">;</span>
    <span class="token class-name">Entry</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span><span class="token class-name">V</span><span class="token punctuation">&gt;</span></span> next<span class="token punctuation">;</span>

    <span class="token keyword">public</span> <span class="token class-name">Entry</span><span class="token punctuation">(</span><span class="token class-name">K</span> k<span class="token punctuation">,</span> <span class="token class-name">V</span> v<span class="token punctuation">,</span> <span class="token keyword">int</span> hash<span class="token punctuation">,</span> <span class="token class-name">Entry</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">K</span><span class="token punctuation">,</span> <span class="token class-name">V</span><span class="token punctuation">&gt;</span></span> next<span class="token punctuation">)</span> <span class="token punctuation">{

   
        <span class="token keyword">this</span><span class="token punctuation">.</span>k <span class="token operator">=</span> k<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>v <span class="token operator">=</span> v<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>hash <span class="token operator">=</span> hash<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> next<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token class-name">K</span> <span class="token function">getKey</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{

   
        <span class="token keyword">return</span> k<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token class-name">V</span> <span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{

   
        <span class="token keyword">return</span> v<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

}

定义一个测试类

public class Test {
   
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{

   
    <span class="token class-name">Map</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">String</span><span class="token punctuation">,</span><span class="token class-name">String</span><span class="token punctuation">&gt;</span></span> map <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">HashMap</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    map<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token string">"Monkey"</span><span class="token punctuation">,</span><span class="token string">"我是moneky老师"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    map<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token string">"东山再起"</span><span class="token punctuation">,</span><span class="token string">"东山再起是位好同学"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>map<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span><span class="token string">"Monkey"</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>map<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span><span class="token string">"东山再起"</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

//输出结果:

//我是moneky老师

//东山再起是位好同学

}

查看到测试结果，我们就能看到HashMap ，是怎么存储的，和获取值的！

但是JDK8 用的是红黑树，为什么了？
举个代码的例子

import com.sun.xml.internal.ws.api.model.wsdl.WSDLOutput;
public class Test {
   
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{

   
    <span class="token class-name">Map</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">String</span><span class="token punctuation">,</span><span class="token class-name">String</span><span class="token punctuation">&gt;</span></span> map <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">HashMap</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">1000</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{

   
        map<span class="token punctuation">.</span><span class="token function">put</span><span class="token punctuation">(</span><span class="token string">"Monkey"</span><span class="token operator">+</span>i<span class="token punctuation">,</span><span class="token string">"我是moneky老师"</span><span class="token operator">+</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>map<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

}

可以看到这个map 的size 只有16，却存了很多的数据：
在这里插入图片描述
容量不够，我们就只能把这个数据放到链表上，链表无线延长，这种hash冲突是十分严重的，而链表的特性是查询慢，而链表又无线延长，我们查询链表末端的数据，这样性能就很低了，所以JDK8 就用红黑树了！

总结：解决链表过长查询效率过低的问题

什么情况下用红黑树?

前提条件
阈值 8

HashMap 类下面有个这个：

  static final int TREEIFY_THRESHOLD = 8;

为什么要阈值是8 了？

因为红黑叔插入慢，他要判断小中大（也就是左边的小于右边的），而链表插入快，删除快，但是为什么是 8 不是 6了？
在这里插入图片描述

我要去百度一下，有哪位大佬知道可以跟我讲下？