哈希表是散列表吗（线性探测再散列法是什么）

本文目录

• 线性探测再散列法是什么
• 散列查找和哈希查找一样吗
• 数据结构与算法-基础（十八）哈希表
• 下面关于哈希(Hash)查找（散列查找）的说法中不正确的是【】
• hashmap 中 hash 函数怎么是是实现的还有哪些 hash 的实现方式

线性探测再散列法是什么

线性探测再散列是哈希表解决冲突的一种计算方法，哈希表又称散列表，哈希表存储的基本思想是：以数据表中的每个记录的关键字 k为自变量，通过一种函数H(k)计算出函数值。

把这个值解释为一块连续存储空间（即数组空间）的单元地址（即下标），将该记录存储到这个单元中。在此称该函数H为哈希函数或散列函数。按这种方法建立的表称为哈希表或散列表。

Hi=(H(key)+di) % m，i=1,2,……k(k《=m-1)，H(key)哈希函数，m哈希表长，di增量序列。

当di值可能为1,2,3,...m-1，称线性探测再散列。开放地址法有一个公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k《=m-1）。

其中，m为哈希表的表长。di是产生冲突的时候的增量序列。

如果di取1，则每次冲突之后，向后移动1个位置。如果di取值可能为1，-1、4、-4、9、-9、16,、16、...k*k、-k*k(k《=m/2），称二次探测再散列，如果di取值可能为伪随机数列。称伪随机探测再散列。

处理冲突的方法：

1、开放寻址法：Hi=(H(key) + di) MOD m, i=1,2,…, k(k《=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：

（1）di=1,2,3,…, m-1，称线性探测再散列；

（2）di=1^2, -1^2, 2^2,-2^2, 3^2, …, ±(k)^2,(k《=m/2)称二次探测再散列。

（3）di=伪随机数序列，称伪随机探测再散列。

2、再散列法：Hi=RHi(key), i=1,2,…,k. RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。

3、链地址法（拉链法）：将所有关键字为同义词的记录存储在同一线性链表中。

散列查找和哈希查找一样吗

哈希查找(散列查找)，与前面介绍的静态查找和动态查找方法完全不同，前面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，而散列查找是通过构造哈希函数来得到待查关键字的地址，按理论分析真正不需要用到比较的一种查找方法。
2.哈希表定义：根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作 为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”
3.举例来说明：
假设有一批关键字序列18,75,60,43,54,90,46，给定哈希函数H（k）=k%13，存贮区的内存地址从0到15，则可以得到每个关键字的散列地址为：
H（18）=18%13=5,H（75）=75%13=10,H（60）=60%13=8,H（43）=43%13=4,H（54）=54%13=2,H（90）=90%13=12, H（46）=46%13=7，
于是，根据散列地址，可以将左边7个关键字序列存贮到一个一维数组HT（哈希表或散列表）中，具体

数据结构与算法-基础（十八）哈希表

上期使用 红黑树 实现映射结构，这样的结构满足 Key 必须具备可比性，元素有顺序地分布 这两个特点。在实际的应用场景中，存在结构中的 元素是不需要有序的，并且 Key 也不具备可比较性 ，哈希表完全满足这样的应用场景。

比如设计一个公司的通讯录，存放所有员工的通讯信息，就可以拿手机号作为 index，员工的名称、职位等作为 value。用哈希表的方式可以将添加、删除和搜索的时间复杂度控制在 O(1)。

这时创建一个数组，手机号作为 index，然后存放 value。这样能将复杂度控制在 O(1)，但是这种 空间换时间 的方式也造成了一些其他问题，比如空间复杂度大（需要更多的空间），空间使用率极其低，非常浪费内存空间。

哈希表 就是空间换时间的处理方式，但是做了优化，在空间和时间两个纬度中达到适当的平衡。

哈希表也叫做散列表，整体结构就是一个数组 ，哈希表会将 key 用哈希函数处理之后返回 hash（哈希值），hash 就是哈希表中的 index这样的处理方式就可以满足搜索时间是 O(1)，这样的处理方式就可以满足搜索时间是 O(1)。因为哈希表中的 key 可能不具备可比较性，所以要做哈希处理。

在执行哈希函数之后返回的 hash，可能会出现相同的情况 ，这样的情况就是 哈希冲突 。解决哈希冲突常见的方法有这三种：

JDK1.8 解决哈希冲突的方式就是使用链地址法，其中的链表就是通过链表+红黑树的组合来实现 。比如当哈希表中的容量大于等于 64，并且单向链表的节点数大于 8 时，转换为红黑树，不满足这个条件时就使用单向链表。

哈希函数 是生成哈希值的实现方法，哈希函数的实现步骤大致分为两步：

hash_code 是生成哈希值的函数，也可以直接用 JAVA 中的标准函数 hashCode() 。

这里可以用 & 位运算替换 % 运算，来提高效率。因为 & 位运算是二进制运算，所以在设计数组的时候，需要将数组的长度设计为 2 的幂次方。

一个良好的哈希函数，可以让生成的哈希值分布更加均匀，减少哈希冲突的次数，最终可以提升哈希表的性能。

Key 的常见类型可能有证书、浮点数、字符串或者自定义对象，不同的类型生成哈希值的方式也会不一样，但是目标是一致的，就是 尽量让每个 Key 的哈希值唯一，尽量让 Key 中的所有信息参与运算 。

比如在 Java 中， Long 的哈希值实现如下代码：

这里的 》》》 和 ^ 就是将高 32 bit 和低 32 bit 混合计算出 32 bit 的哈希值。

在计算字符串的哈希值时，可以将字符串拆解成若干个字符，比如 jack，将它拆解成 j、a、c、k（字符的本质就是一个整数，所以 jack 的哈希值可以表示为 j * n3 + a * n2 + c * n1 + k * n0，表达式也可以写成 * n + k，代码实现如下：

看上面代码时，可以发现，表达式中的 n 使用的是 31 这个数字，那么为什么用 31 呢？

因为 31 不仅符合 22 - 1 , 而且它还是个奇素数（既是技术，又是素数，还是质数），素数和其他数相乘的结果比其他方式更容易产生唯一性，减少哈希冲突。

JDK 中，乘数 n 也是用 31，31 也是经过观测分布结果后的选择，关于 31 的变体可以有以下几种：

31 * i = (25 - 1) * i = i * 25 - i = (i 《《 5) - i

下面关于哈希(Hash)查找（散列查找）的说法中不正确的是【】

【答案】：ABD
散列表又被称为哈希(Hash)表，散列函数又被称为哈希函数．冲突是不可完全避免的，只能在设计哈希函数时尽量减少冲突．不能说哪，种哈希函数的选取方法最好，各种选取方法有自己的适用范围．

hashmap 中 hash 函数怎么是是实现的还有哪些 hash 的实现方式

HashMap是对数据结构中哈希表(Hash
Table)的实现，Hash表又叫散列表。Hash表是根据关键码Key来访问其对应的值Value的数据结构，它通过一个映射函数把关键码映射到表中一个位置来访问该位置的值，从而加快查找的速度。这个映射函数叫做Hash函数，存放记录的数组叫做Hash表。
在Java中，HashMap的内部实现结合了链表和数组的优势，链接节点的数据结构是Entry《k,v》，每个Entry对象的内部又含有指向下一个Entry类型对象的引用，如以下代码所示：
static
class
Entry《K,V》
implements
Map.Entry《K,V》
{
final
K
key;
V
value;
Entry《K,V》
next;
//Entry类型内部有一个自己类型的引用，指向下一个Entry
final
int
hash;
...
}
在HashMap的构造函数中可以看到，Entry表被申明为了数组，如以下代码所示：
public
HashMap()
{
this.loadFactor
=
DEFAULT_LOAD_FACTOR;
threshold
=
(int)(DEFAULT_INITIAL_CAPACITY
*
DEFAULT_LOAD_FACTOR);
table
=
new
Entry;
init();
}
在以上构造函数中，默认的DEFAULT_INITIAL_CAPACITY值为16，DEFAULT_LOAD_FACTOR的值为0.75。
当put一个元素到HashMap中去时，其内部实现如下：
public
V
put(K
key,
V
value)
{
if
(key
==
null)
return
putForNullKey(value);
int
hash
=
hash(key.hashCode());
int
i
=
indexFor(hash,
table.length);
...
}