Hashmap的二次hash不太理解。

Question

Hashmap的第一次hash和第二次hash分别是干什么的，能否介绍一下

Answer 1

一、哈希表的概念

1、查找算法

  当我们在一个 链表 或者 顺序表 中 查找 一个数据元素 是否存在 的时候，唯一的方法就是遍历整个表，这种方法称为 线性枚举。

  如果这时候，顺序表是有序的情况下，我们可以采用折半的方式去查找，这种方法称为 二分枚举。
  线性枚举 的时间复杂度为 $O(n)$。二分枚举 的时间复杂度为 $O(log_2n)$。是否存在更快速的查找方式呢？这就是本要介绍的一种新的数据结构 —— 哈希表。

2、哈希表

  由于它不是顺序结构，所以很多数据结构书上称之为 散列表，下文会统一采用 哈希表 的形式来说明，作为读者，只需要知道这两者是同一种数据结构即可。
  我们把需要查找的数据，通过一个 函数映射，找到 存储数据的位置 的过程称为 哈希。这里涉及到几个概念：
  a）需要 查找的数据 本身被称为 关键字；
  b）通过 函数映射 将 关键字 变成一个 哈希值 的过程中，这里的 函数 被称为 哈希函数；
  c）生成 哈希值 的过程过程可能产生冲突，需要进行 冲突解决；
  d）解决完冲突以后，实际 存储数据的位置 被称为 哈希地址，通俗的说，它就是一个数组下标；
  e）存储所有这些数据的数据结构就是 哈希表，程序实现上一般采用数组实现，所以又叫 哈希数组。整个过程如下图所示：

2、哈希数组

  为了方便下标索引，哈希表 的底层实现结构是一个数组，数组类型可以是任意类型，每个位置被称为一个槽。如下图所示，它代表的是一个长度为 8 的 哈希表，又叫 哈希数组。

3、关键字

  关键字 是哈希数组中的元素，可以是任意类型的，它可以是整型、浮点型、字符型、字符串，甚至是结构体或者类。如下的 A、C、M 都可以是关键字；

int A = 5;
char C[100] = "Hello World!";
struct Obj { };
Obj M;

  哈希表的实现过程中，我们需要通过一些手段，将一个非整型的 关键字 转换成 数组下标，也就是 哈希值，从而通过 $O(1)$ 的时间快速索引到它所对应的位置。
  而将一个非整型的 关键字 转换成 整型 的手段就是 哈希函数。

4、哈希函数

  哈希函数可以简单的理解为就是小学课本上那个函数，即 $$y = f(x)$$，这里的 $f(x)$ 就是哈希函数，$x$ 是关键字，$y$ 是哈希值。好的哈希函数应该具备以下两个特质：
  a）单射；
  b）雪崩效应：输入值 $x$ 的 $1$ 比特的变化，能够造成输出值 $y$ 至少一半比特的变化；
  单射很容易理解，图 $(a)$ 中已知哈希值 $y$ 时，键 $x$ 可能有两种情况，不是一个单射；而图 $(b)$ 中已知哈希值 $y$ 时，键 $x$ 一定是唯一确定的，所以它是单射。由于 $x$ 和 $y$ 一一对应，这样就从本原上减少了冲突。

  雪崩效应是为了让哈希值更加符合随机分布的原则，哈希表中的键分布的越随机，利用率越高，效率也越高。
  常用的哈希函数有：直接定址法、除留余数法、数字分析法、平方取中法、折叠法、随机数法 等等。有关哈希函数的内容，下文会进行详细讲解。

5、哈希冲突

  哈希函数在生成 哈希值 的过程中，如果产生 不同的关键字得到相同的哈希值 的情况，就被称为 哈希冲突。
  即对于哈希函数 $$y = f(x)$$，当关键字 $x_1 \neq x_2$，但是却有 $f(x_1) = f(x_2)$，这时候，我们需要进行冲突解决。
  冲突解决方法有很多，主要有：开放定址法、再散列函数法、链地址法、公共溢出区法 等等。有关解决冲突的内容，下文会进行详细讲解。

6、哈希地址

  哈希地址 就是一个 数组下标 ，即哈希数组的下标。通过下标获得数据，被称为 索引。通过数据获得下标，被称为 哈希。平时工作的时候，和同事交流时用到的一个词 反查 就是说的 哈希。

《画解数据结构》（1 - 8）- 哈希表_英雄哪里出来-CSDN博客 动图详解哈希表 https://blog.csdn.net/WhereIsHeroFrom/article/details/118987892