一、哈希表是什么？

哈希表，也称为散列表，是一种根据关键码值（Key value）直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，从而加快查找速度。这个映射函数叫做散列函数（哈希函数），而存放记录的数组则称为散列表。

二、哈希表的构成（开放地址法）

我们先了解一下哈希表是如何构成的？
实现一个基本的哈希表数据结构涉及到几个核心步骤：
1、创建哈希表本身的数据结构，
2、定义一个哈希函数，
3、处理哈希冲突(本文以开放地址法为例)

开放地址法（Open Addressing）是哈希表解决哈希冲突的一种策略。当发生哈希冲突时，即两个或更多的键具有相同的哈希值，开放地址法通过在数组中查找下一个可用的空位来解决冲突。这种方法的核心思想是不再依赖哈希函数给出的数组下标，而是顺序查看表中的下一个单元，直到找到一个空单元或查遍全表。

开放地址法通常有以下三种具体实现方式：

---

线性探测：这是最简单的一种开放地址法。当发生冲突时，顺序查看表中下一个单元，直到找到一个空单元或查遍全表。这种方法的核心思想是“一旦发生冲突，就去寻找下一个空的散列表地址”。

二次探测：这是另一种开放地址法，它在发生冲突时，不是简单地顺序查看下一个单元，而是根据某种二次方程来确定下一个要查看的单元位置。

双重散列：这种方法使用两个哈希函数。当第一个哈希函数发生冲突时，使用第二个哈希函数来确定下一个要查看的单元位置。

这里我们用C语言更加方便举例，后面附带代码图解。

首先是创建哈希表本身的数据结构

#define TABLE_SIZE 10  

//先定义一个有key和value两种属性的结构体
//该结构体的名字是KeyValuePair
typedef struct {  
    int key;  
    int value;  
} KeyValuePair;  

  
// 哈希表结构  
//定义一个结构体，里面有KeyValuePair结构体的数组
//该结构体的名字是HashTable
typedef struct {  
    KeyValuePair pairs[TABLE_SIZE];  
    //暂时定为哈希表的容量为10
    //数组名为pairs
    
} HashTable;  

定义一个哈希函数

// 简单的哈希函数  
unsigned int hash(int key) { 
    //将key值求余以表的容量10 
    return key % TABLE_SIZE;  
}  

定义一个初始化哈希表的函数

#define EMPTY -1

// 初始化哈希表  
void initHashTable(HashTable *table) {  
    for (int i = 0; i < TABLE_SIZE; i++) {  
    //table是指针，所以要用->去解引用再访问
    //table->pairs[i].key 首先解引用 table 指针以获取 HashTable 结构体，
    //然后访问其 pairs 数组的第 i 个元素，
    //最后访问该元素的 key 成员
    //将key值赋值成EMPTY（即-1）
        table->pairs[i].key = EMPTY;  
    }  
}  

创建一个插入值到哈希表的函数，里面需要进行哈希冲突的处理

哈希冲突：将数据插入表中时，数据通过哈希函数计算出来的索引值来找到自己的位置，而数组索引处已有数据，产生冲突。
通俗点，两个数据想要插在数组的同一位置，必须要做一定处理

// 向哈希表中插入键值对  
void insert(HashTable *table, int key, int value) {  
    unsigned int index = hash(key);  
    //通过哈希函数对Key值的运算得到索引index的值



	//产生哈希冲突进行开放寻址，即重新为新来的数据找到空的位置
    while (table->pairs[index].key != EMPTY) { 
    
    	
        // 如果发现key值完全相同，说明用户想覆盖值，则替换值  
        if (table->pairs[index].key == key) {  
            table->pairs[index].value = value;  
            return;  
        }  
        // 线性探测下一个位置  
        index = (index + 1) % TABLE_SIZE;  
    } 
     
    // 找到空位置并插入  
    table->pairs[index].key = key;  
    table->pairs[index].value = value;  
}  

创建一个查询哈希表数据的函数

// 从哈希表中检索值  
int get(HashTable *table, int key) {  
    unsigned int index = hash(key);  
    while (table->pairs[index].key != EMPTY) {  
        // 找到键，返回对应的值  
        if (table->pairs[index].key == key) {  
            return table->pairs[index].value;  
        }  
        // 线性探测下一个位置  
        index = (index + 1) % TABLE_SIZE;  
    }  
    // 没找到键，返回错误值  
    return -1;  
}  

测试主函数

int main() {  
    HashTable table;  
    initHashTable(&table);  
  
    // 插入键值对  
    insert(&table, 10, 100);  
    insert(&table, 20, 200);  
    insert(&table, 30, 300);  
  
    // 检索值  
    printf("Value for key 20: %d\n", get(&table, 20));  
  
    // 更新值  
    insert(&table, 20, 2000);  
    printf("Updated value for key 20: %d\n", get(&table, 20));  
  
    return 0;  
}

例子代码图解

图【1】

图【2】

图【3】

图【4】

图【5】

图【6】

图【7】

图【8】

三、哈希表的构成（链地址法）

处理哈希冲突时，主要有开放地址法和链地址法这两种方法，上面的代码和图解已经介绍了开放地址法

而链地址法也是一种优雅的冲突解决策略。

---

实现步骤：

---

初始化：
创建一个数组，每个元素都是一个链表的头指针。
哈希函数：选择一个合适的哈希函数，将键映射到数组的某个索引。

插入：
计算键的哈希值，找到对应的数组索引。
如果该索引的链表为空，直接插入数据。
如果链表不为空，遍历链表查找：
若找到相同键，更新值。
若未找到，在链表末尾插入新数据。

查找：
计算键的哈希值，找到对应的链表。
遍历链表，比较键，直到找到或遍历完。

删除：
计算键的哈希值，找到对应的链表。
遍历链表，找到要删除的数据并移除。

链地址法通过链表巧妙地解决了哈希冲突，使得哈希表在冲突较多的情况下仍能保持高效。

四、开放地址法与链地址方法时间复杂度比较

开放地址法

开放地址法的时间复杂度分析相对复杂，因为它依赖于哈希表的装载因子（即已存储元素数量与哈希表大小的比值）以及哈希函数的均匀分布性。

插入操作

平均情况：当哈希表的大小足够大且装载因子较低时，插入操作的平均时间复杂度接近O(1)，因为空闲位置较多，冲突较少。
最坏情况：当哈希表的大小较小或装载因子接近1时，插入操作的时间复杂度可能退化为O(n)，其中n是哈希表中的元素数量。这是因为连续的冲突可能导致需要遍历整个哈希表来找到空闲位置。

查找操作

平均情况：与插入操作类似，当哈希表的大小足够大且装载因子较低时，查找操作的平均时间复杂度接近O(1)。
最坏情况：当哈希表的大小较小或装载因子接近1时，查找操作的时间复杂度可能退化为O(n)，特别是当发生堆积（即大量元素集中在哈希表的某些区域）时。

链地址法
链地址法的时间复杂度分析相对简单，因为它不依赖于哈希表的装载因子。

插入操作

平均情况：无论哈希表的大小和装载因子如何，插入操作的平均时间复杂度都是O(1)，因为插入总是在链表的末尾进行。
最坏情况：最坏情况下，当所有的元素都哈希到同一个桶（即链表）时，插入操作的时间复杂度为O(n)，其中n是链表的长度。然而，这种情况在良好的哈希函数和适当的哈希表大小下是很少见的。

查找操作
平均情况：查找操作的平均时间复杂度是O(1 + α)，其中α是链表的平均长度。这是因为查找操作通常只需要遍历链表一次。
最坏情况：最坏情况下，当所有的元素都哈希到同一个桶时，查找操作的时间复杂度为O(n)，其中n是链表的长度。

开放地址法和链地址法在平均情况下的时间复杂度都是O(1)，但在最坏情况下，开放地址法的时间复杂度可能更高，因为它可能需要进行多次探测来找到空闲位置或查找元素。而链地址法则在最坏情况下可能面临链表过长的问题，但在良好的哈希函数和适当的哈希表大小下，这种情况是不常见的。因此，选择哪种方法取决于具体的应用场景和需求。

五、哈希表的应用场景

---

哈希表因其高效的查找和插入性能，被广泛应用于各种场景。以下是哈希表的一些典型应用：

数据库索引

数据库索引是哈希表的一个重要应用。通过索引，可以快速定位到数据库中的特定数据，提高查询效率。

缓存系统

缓存系统通常使用哈希表来存储热点数据，以便快速响应请求。当数据被访问时，将其存储在哈希表中，以便后续快速查找。

唯一性检查

哈希表可以用于检查数据的唯一性。通过计算数据的哈希值，可以快速判断数据是否已经存在于哈希表中。