哈希表
哈希表
哈希表
又称为散列表，通过建立key、value之间的映射，实现元素的高效查找访问，实现O(1)时间复杂度。
相对于数组和链表而言，具有以下区别：（哈希表对以下操作都是O(1)时间复杂度）
- 添加元素：仅需将元素添加到数组的末尾，使用O(1)的时间。
- 查找元素：由于数组链表是无序的，因此需要逐个遍历，使用O(n)的时间。
- 删除元素：需要先查询到元素，再执行删除，所以数组也需要O(n)的时间。
哈希表常用操作
哈希表常见的操作包括初始化、查询操作、添加键值对和删除键值对。
简单哈希的实现
将一个数组用于实现哈希表，将数组中的每个空位称为桶(bucket)，每个桶可存储一个键值对，查询操作就是找到key对应桶，并获取桶中的value。
如何定位桶呢？通过哈希函数实现，哈希函数的作用就是输入一个key，通过哈希函数找到对应键值在数组中的存储位置。
/* 模拟简单哈希表 */
// 初始化、查询操作、添加键值对、删除键值对
class HashMap {
constructor(size) {
this.size = size;
this.table = new Array(size); // 初始化
}
hash(key) { // 哈希函数
let hashValue = 0;
for (let i = 0; i < key.length; i++) {
hashValue += key.charCodeAt(i);
}
return hashValue % this.size; // 模拟了一个10个空间的哈希表,取模相对于一个哈希函数过程，获取对应索引
}
set(key, value) {
let index = this.hash(key);
if (!this.table[index]) {
console.log(this.table[index]);
this.table[index] = []; // undefined，先赋值一个空数组，方便后续插入
}
this.table[index].push([key, value]);
}
get(key) {
let index = this.hash(key);
if (!this.table[index]) {
return undefined;
}
for (let fair of this.table[index]) {
// 数组中存储的是[key，value]
if (fair[0] == key) {
return fair[1];
}
}
return undefined;
}
remove(key) {
let index = this.hash(key);
if (!this.table[index]) {
return;
}
// ?
this.table[index] = this.table[index].filter((pair) => pair[0] !== key);
}
}
const hashTable = new HashMap(50);
hashTable.set("name", "sunshine");
hashTable.set("name", "scott");
hashTable.set("age", 26);
console.log(hashTable.get("name"));
console.log(hashTable.get("name"));
hashTable.remove('name')
console.log(hashTable.get('name'));
哈希冲突与扩容
从本质来讲，哈希函数的作用是将所有的key构成的输入空间映射到数组索引组成的输出空间中，但是输入空间往往远大于输出空间。因此，理论上一定存在“多个输入对应相同的输出”的情况。例如上述哈希函数，对于12306与12506而言，取模结果都是6，指向了同一个地址。我们将多个输入对应同一个输出的情况叫做哈希冲突。
发散想象，当哈希标容量n越大，多个key被分配到同一个桶中的概率越低，冲突越少，因此可以通过扩容来解决哈希冲突问题。
哈希扩容类似于数组扩容，需要将原哈希表中的所有键值对迁移到新的哈希表中，非常耗时间。且由于哈希表容量变化，需要重新通过哈希函数计算所有键值对的存储位置，因此编程语言一般会预留出足够大的哈希表容量来避免发生哈希扩容。
负载因子是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重性，也常用于判定是否进行哈希扩容的触发条件。例如Java中，当负载因子超过0.75时，会将哈希表扩容为原来的2倍。
哈希冲突
通常情况下哈希函数的输入空间远远大于输出空间，因此哈希冲突是不可避免的。每当发生哈希冲突时，就对哈希标进行扩容，这种效率太低，为了提升效率有以下策略：
- 改良哈希表结构，使得哈希表发送哈希冲突时可以正常工作。
- 仅在必要时进行哈希扩容。
哈希表结构改良主要包括链式地址、开发寻址
链式地址
在原始哈希表中，每个桶仅能存储一个键值对。链式地址将单个元素转换为链表，将键值对作为链表节点，所有发生冲突的键值对都存储在同一个链表中。
基于链表实现的哈希表的操作方法发生了以下变化：
- 查询元素：输入key，通过哈希函数获取桶的索引，即可访问链表头节点，然后遍历链表并对比key以查找目标键值对。
- 添加元素：首先通过哈希函数查找对应桶，从链表头节点开始访问，如何将新节点（键值对）添加到链表中。
- 删除元素：删除元素需要先查询到元素，后将其删除。
链式地址存在以下局限性：
- 占用空间增大：链表中包含节点指针，它相比于普通数组更占据空间。
- 查询效率降低：需要线性遍历链表来查找对应元素
// 定义链表节点
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.next = null;
}
}
// 定义哈希表
class HashTable {
constructor(size) {
this.size = size;
this.table = new Array(size);
}
// 哈希函数
hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % this.size;
}
// 插入键值对
insert(key, value) {
const index = this.hash(key);
if (!this.table[index]) {
this.table[index] = new Node(key, value);
} else {
let currentNode = this.table[index];
while (currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = new Node(key, value);
}
}
// 获取值
get(key) {
const index = this.hash(key);
let currentNode = this.table[index];
while (currentNode) {
if (currentNode.key === key) {
return currentNode.value;
}
currentNode = currentNode.next;
}
return null;
}
// 删除键值对
delete(key) {
const index = this.hash(key);
let currentNode = this.table[index];
if (currentNode && currentNode.key === key) {
this.table[index] = currentNode.next;
return;
}
while (currentNode.next) {
if (currentNode.next.key === key) {
currentNode.next = currentNode.next.next;
return;
}
currentNode = currentNode.next;
}
}
}
// 使用示例
let hashTable = new HashTable(10);
hashTable.insert("key1", "value1");
hashTable.insert("key2", "value2");
hashTable.insert("key3", "value3");
console.log(hashTable.get("key1")); // 输出 "value1"
console.log(hashTable.get("key2")); // 输出 "value2"
hashTable.delete("key2");
console.log(hashTable.get("key2")); // 输出 null，因为已经删除了 "key2"
开放寻址
开放寻址不引入额外的数据结构，而是通过多次探测来处理哈希冲突，主要包含线性探测、平方探测、多次哈希等。
线性探测
采用固定步长来进行线性搜索进行探测，有以下步骤：
- 通过哈希函数计算桶索引，若桶内已有元素，则从冲突不为向后线性遍历，直到找到空桶，将元素放入桶内。
- 查找元素：若发生哈希冲突，使用相同步长向后进行线性遍历，直到找到对应元素，返回value。若遇到空桶，则该元素不存在。
问题：线性探测容易发生聚集现象，数组中连续部分被占用越长，这些位置继续发生哈希冲突的可能性就越大，从而聚堆生长。并且不能再开放寻址的哈希表中直接删除元素，这样会产生空桶，导致误以为元素不存在，解决方法就是采用懒删除方式，并不直接在哈希表用移除该元素，而是使用TOMBSTONE进行标记，线性遍历到这里时会忽略，继续遍历。但是这会加速哈希表的性能退化。
平方探测
与线性探测类似，每当发生冲突时，并不是简单的跳过一个固定步长，而是跳过探测次数的平方的步数。具体优势如下：
- 平方探测通过加大探测的距离，进行缓解聚集效应。
- 有助于数据分布更均匀。
多次哈希
使用多次哈希函数进行探测。
- 插入元素：当哈希函数f1发生冲突时，尝试使用f2，以此类推，直到找到空桶插入元素。
- 查找元素：在相同的哈希函数顺序下进行查找，直到找到目标元素时返回。或遇到空位或者已经尝试所有的哈希函数后，则表明该哈希表中不存在该元素，返回None。
哈希算法
开放寻址法跟链式地址只能保证哈希表在发生冲突时能正常工作，而无法减少哈希冲突的发生。
哈希算法的目标
为了实现“既快又稳”的哈希表数据结构，哈希算法应具备以下特点：
- 确定性：对于相同的输入，哈希算法应始终输出相同的输出。
- 效率高：计算哈希值的过程应该足够快，计算开销越小，哈希表的实用性越高。
- 均匀分布：哈希算法应 当使得键值对均匀分布在哈希表中，分布越均匀，发生哈希冲突的概率越小。
应用领域：
- 密码存储：保护密码安全，用户不存储密码明文，而是存储密码的哈希值。
- 数据完整性检验：数据发送方可以计算数据的哈希值并将其一同发送，接收方可以重新计算数据的哈希值，并与接收到的哈希值进行比较。
对于密码学来说，为了防止从哈希值反推原始密码等逆向工程，哈希算法应具备更高等级的安全性：
- 单向性：无法通过哈希值反推关于输入的任何信息。
- 抗碰撞性：极难找到两个不同的输入，使得他们的哈希值相同。
- 雪崩效应：输入的微小变化应当导致输入的显著且不可预测的变化。
常见的哈希算法
MD5、SHA-1、SHA2、SHA3等标准哈希算法：
- MD5和SHA-1已被多次成功破解，因此被各大类安全应用弃用，MD5输出128比特，SHA-1输出160比特。
- SHA-2系列中SHA-256是最安全的哈希算法之一，SHA-2输出256/512比特。
- SHA-3相较SHA-2的实现开销更低、计算效率更高，但是目前使用覆盖率不如SHA-2系列，SHA-3输出224/256/384/512比特。