哈希表的相关知识点

1.哈希表是什么

哈希表的诞生：在哈希表出现之前，查找数据都是通过比较来查找到，效率太慢了，有没有一种方法是不经过任何比较，一次就查找到所查的数据？

• 线性表、树

  线性表、树 这些结构中，记录 在结构 中的相对位置是随机的，和记录的关键字之间不存在确定关系，因此，在结构中查找时需要进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上。在顺序查找时，比较的结果为“=”与“≠”2种可能；在折半查找、二叉排序树查找和B-树查找时，比较的结果为“<”“=”“>”3种可能。查找的效率依赖于查找过程中所进行的比较次数。

• 哈希表

  理想的情况是希望不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的关系，使每个关键字和结构中一个唯一的存储位置相对应。因而在查找时，只要根据这个对应关系找到给定值的像。若结构中存在关键字和相等的记录，则必定在的存储位置上，反之在这个位置上没有记录。由此，不需要比较便可直接取得所查记录。在此，我们称这个对应关系为哈希(Hash)函数 ，按这个思想建立的表为哈希表 。

  （插播：注意“理想情况”这几个字~~ 这会在后文给出解释）

这是《数据结构（C语言版）》[1]中引出哈希表的一段描述，通俗易懂。所以，我们知道了什么是哈希函数 和哈希表 。

2.HashMap的使用

使用哈希表前需导入相关的包

import java.util.HashMap;

创建一个HashMap对象，存储的是双列表数据，键值对key-value

HashMap hm = new HashMap<>();

hm 为HashMap的变量名

 为HashMap存储的双队列
key-value 可以为任意的Object对象的类型
如 Integer(整数),String(字符串),Charcter(字符)

Hash表中的存储数据

hm.put(key,value)

hm为HashMap的名字

hm.size() 返回Hash表中元素的数量

举例：

package hashmap;

import java.util.HashMap;

public class hashmap {
    public static void main(String[] args) {
        //创建一个HashMap对象:存储的是双列表数据,键值对 key-value
        HashMap hm = new HashMap<>();
        //在jdk17后，后面的<>不必和前面的一样了，省去了编写的过程
        //存储数据
        hm.put(12,"zcj");
        hm.put(7,"asdf");
        hm.put(1,"aoin");
        hm.put(7,"oain");

        System.out.println("集合中的元素"+hm/*.toString()*/);
        //通过.toString 将hm中的值输出
        System.out.println("集合中元素的数量"+hm.size());

    }
}

注意事项：

当两个值的key相同时会出现什么情况？

上述代码的运行结果，明明我们给它赋值了四个元素，但hash表中只有三个

由结果我们可以得出：当两个key相同时，后面的value会将前面的value给覆盖掉，并将前面的value作为返回值返回

示例如下：

package hashmap;

import java.util.HashMap;

public class hashmap {
    public static void main(String[] args) {
        //创建一个HashMap对象:存储的是双列表数据,键值对 key-value
        HashMap hm = new HashMap<>();
        //在jdk17后，后面的<>不必和前面的一样了，省去了编写的过程
        //存储数据
        System.out.println(hm.put(12, "zcj"));
        System.out.println(hm.put(7, "asdf"));
        System.out.println(hm.put(1, "aoin"));
        System.out.println(hm.put(7, "oain"));
        System.out.println("集合中的元素"+hm/*.toString()*/);
        //通过.toString 将hm中的值输出
        System.out.println("集合中元素的数量"+hm.size());

    }
}

运行结果： 

 asdf是前面的value，oain是后面的value

由结果可以看出，后面存储的value（oain）将前面存储的value（asdf）覆盖掉，并将asdf返回

如果后面的value没有将前面的value覆盖掉，则放入hash表中，返回为null

也可以得出如下结论：key的值唯一

3.哈希表的底层原理

以key = int为例

1.确定好存储的数据

2.调用hashCode方法计算出哈希码

3.调用另一个算法根据hash码计算出数据放在主数组中的哪个位置

主数组：hash表中的底层数组，用来存储数据

存储数据的类为Entry类，因此数组的类型也是Entry[]，

Entry类：key,value,根据key计算出来的hash码，下一个元素的地址

 注意：哈希碰撞

哈希碰撞就是两个值的存储地址相同的时候，如下

1.两个key相同

hm.put(1,"a")
hm.put(1,"b")

两个key-value的key相同，因此根据key计算出来的存放位置也相同

哈希碰撞结果：b将a替换掉，其他的三个数据不变

2.两个key不同，但是算出来的存放位置相同

hm.put(1,"a")
hm.put(22,"b")

这两个key-value的在主数组中存放的位置都是4（元素的下标）

此时，需要判断，（22，“b")放在（1，“a")前还是后

口诀：七上八下

jdk7对应的源码往上插，jdk8对应的往下插

举例：以往上查为例

假设（1，”a")封装后的地址为0x99，则主数组4存储的数据就是0x99

在（22，“b")封装的地址为0x77,且存储位置为4

此时，发生了哈希碰撞，主数组存储的数据0x99变为0x77,封装好的（22，”b")中的指向下一个元素的地址变为0x99

如图：

 由图也可以看出

哈希表 = 数组 + 链表（数据结构的逻辑结构）

4.哈希表的一些重要属性

主数组的默认长度

static final int DEFAULT_INITIAL_CAPACITY = 16;默认长度为16

主数组最大长度

static final int MAXIMUM_CAPACITY = 1 << 30;

2的30次方

负载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;
定义了一个值：0.75f 负载因子
也可以叫做加载因子

主数组的定义

transient Entry[] table;//底层的主数组

数组扩容的边界值

int threshosd;

定义了一个变量，没赋值默认为0
这个变量是用来表示数组扩容的边界值

装填因子

float float loadFactor;

用来接受 负载因子/加载因子

添加的元素的数量

transient int size;

5.HashMap的构造器

源码：

空构造器：

public HashMap(){
    this(DEFAULT_INITIAL_CAPACITY,DEFAULT_LOAD_FACTOR)
}

DEFAULT_INITIAL_CAPACITY : 16
DEFAULT_LOAD_FACTOR : 0.75f

带参数构造器（删除抛出异常后的源码） 

确定容量： 

int capacity = 1;
while(capacity < initialCapacity)
    capacity <<= 1;

capacity:容量
capacity的最终结果为2的n次幂

确定负载因子： 

this.loadFactor = loadFactor;
threshold = (int) Math.min(capacity * loadFactor , MAXIMUM_CAPACITY + 1);

// threshold = 16 * 0.75 = 12
// 12-->数组扩容的边界值

创建数组

table = new Entry[capacity];//创建主数组，长度为16，类型为Entry

下面两行不重要
useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();

6.HashMap的put方法

put源码：

 hash值的算法

通过二次散列的方式尽量避免两个不同的key存放的位置相同 ，解决hash冲突

扰动函数中具体的值，如20，12，都是通过统计学得出来的

 计算位置

 h & (length-1)  == h % length 取余

用 & 运算效率更高

添加元素的方法

 创建Entry对象，并将其放入table

   这一个位置没有值的时候，e就是null，有的话e就是指向先前位置的指针

源码分析

//存储数据的方法
public V put(K key,V value){ // k: Integer V: String
     //对空判断，允许key 为 null
     if(key == null)
        return putForNullKey(value);
    //获取哈希码
    int hash = hash(key);
    //得到元素在数组中的位置
    int i = indexFor(hash,table.length)l
    //如果放入的数组的位置上没有元素的话，那么直接添加就行了，不用走这个for循环
    //e != null 满足的话，说明这个位置上有东西了
    for(Entry e = table[i];e != null ;e=e.next){
        Object k;
        //如果发生hash碰撞的时候，会先比较hash值
        //比较key是否是一个对象，如果是一个对象的话，equals就不比较了
        //如果不是同一个对象，会比较equals方法
        //如果hash值不一样，equals方法比较的结果也一样，那么才会走这个if
        if(e.hash == hash && ((k == e.key) == key || key.equals(k))){
            V oldvalue = e.value;//获取先前的value
            e.value = value;//新的value替换老的value
//只替换value，不替换key（key相同）
            e.recordAccess(this);
            return oldValue;//将先前的value返回
        }
    }
    addEntry(hash , key,value,i);
    return null;
}

7.HashMap底层数组的扩容

源码：

在添加元素前会进行一次判断，符合扩容条件就会自动扩容为原来的两倍 

8.经典面试题

1.为什么装填因子，负载因子，加载因子 是 0.75？

装填因子设置为 1 ： 空间利用率提高了，但很容易发生碰撞，容易产生链表--->查询效率低（空间高，时间低）

装填因子设置为 0.5 ：空间利用率低， 碰撞低，扩容，产生链表低，查询高（空间低，时间高）

因子取 1和0.5之间的数：0.75

源码：

 2.主数组的长度为什么必须为2的n次幂？

原因：1. h &(length-1) 等效于 h%length *** 作的前提：length必须是2的整数倍

2.防止hash冲突，位置冲突