哈希表的学习
哈希表
通过哈希函数将键值映射到特定的数组索引，从而实现高效的查找、插入和删除操作。其核心思想是将数据直接存储到具有固定大小的数组中，通过哈希函数计算出每个数据的存储位置。
主要特性
哈希函数：哈希函数用于将输入的键（通常是字符串或数字）转换为数组中的索引。理想的哈希函数应尽量避免不同的键映射到同一索引（称为冲突）。
冲突处理：
开放地址法：在发生冲突时，通过线性探查、二次探查或双重哈希等方式，寻找数组中下一个空闲位置。
链地址法：在每个哈希表的索引处，维护一个链表或其他容器来存储所有具有相同哈希值的元素。
时间复杂度：
负载因子：负载因子是哈希表中存储的元素数量与哈希表大小的比值。当负载因子过大时，哈希表的性能会下降，通常通过扩展哈希表（重新哈希）来解决。
哈希表的应用
数据库索引
缓存（如 LRU Cache）
唯一性检测（如查找重复项）
字典/映射实现
优缺点
优点：
查找、插入和删除的平均时间复杂度为常数时间 O(1)O(1)O(1)。
适合快速查找和存储大量数据。
缺点：
当哈希函数设计不当或负载因子过大时，性能会急剧下降。
存在内存浪费，特别是在使用开放地址法时，需要额外的存储空间。
哈希冲突
发生在两个不同的键通过哈希函数映射到相同的数组索引时。为了解决哈希冲突，常见的解决办法主要有以下两种：开放地址法和链地址法，每种方法又有不同的变种和策略。
1. 链地址法（Separate Chaining）
链地址法是最常见的哈希冲突解决方案。它通过在哈希表的每个索引处维护一个链表（或其他容器），当多个键被映射到同一索引时，直接将它们放入这个链表中。
优点：
简单直观，容易实现。
不受表大小限制，可以处理超过哈希表容量的数据。
缺点：
如果冲突过多，链表长度变长，查找效率会退化到 O(n)O(n)O(n)。
改进方法：
使用自平衡二叉搜索树或跳表代替链表，从而在冲突严重时保持较好的性能。
2. 开放地址法（Open Addressing）
开放地址法通过在哈希表中寻找下一个可用的空闲位置来存储冲突的元素。它不使用外部链表，而是在数组内部解决冲突。
2.1 线性探查（Linear Probing）
当发生冲突时，按照线性顺序（即每次向前移动一格）依次检查下一个位置，直到找到一个空闲的槽位。
公式：h(k, i) = (h(k) + i) % m，其中 i 表示冲突次数，m 为哈希表大小。
优点：
实现简单。
连续数据的访问具有较高的缓存命中率。
缺点：
容易产生主堆积现象（primary clustering）：即多个连续的空位被占用后，新的元素很容易探查到这些连续区域，进一步加剧冲突。
算法时间复杂度
执行这个算法所花时间的度量
将数据量增长和时间增长用函数表示出来，这个函数就叫做时间复杂度。
一般用大O表示法：O（n）时间复杂度是关于数据n的一个函数
随着n的增加，时间复杂度增长较慢的算法时间复杂度低
时间复杂度的计算规则
1，用常数1 取代运行时间中的所有加法常数
2，在修改后的运行函数中，只保留最高阶项。
3，如果最高阶存在且系数不是1，则去除这个项相乘的常数。
#include "hash.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
HSNode_t *hashtable[HASH_SIZE] = {NULL};
int hash_function(char key)
{
if (key >= 'a' && key <= 'z')
{
return key-'a';
}
else if (key >= 'A' && key <= 'Z')
{
return key-'A';
}
else
{
return HASH_SIZE-1;
}
}
int insert_hashtable(HSDataTYpe data)
{
int addr = hash_function(data.name[0]);
HSNode_t *pnode = malloc(sizeof(HSNode_t));
if (NULL == pnode)
{
perror("fail malloc");
return -1;
}
pnode->data = data;
pnode->pnext = NULL;
pnode->pnext = hashtable[addr];
hashtable[addr] = pnode;
return 0;
}
void hash_for_each()
{
for (int i = 0; i < HASH_SIZE; i++)
{
HSNode_t *p = hashtable[i];
while (p != NULL)
{
printf("%s %s ", p->data.name, p->data.tel);
p = p->pnext;
}
printf("\n");
}
}
HSNode_t *find_hashtable(char *name)
{
int addr = hash_function(name[0]);
HSNode_t *p = hashtable[addr];
while (p != NULL)
{
if (!strcmp(name, p->data.name))
{
// printf("%s %s\n", ptmp->data.name, ptmp->data.tel);
return p;
}
p = p->pnext;
}
return NULL;
}
void destroy_hashtable()
{
for (int i = 0; i< HASH_SIZE; i++)
{
while (hashtable[i] != NULL)
{
HSNode_t *p = hashtable[i];
hashtable[i] = p->pnext;
free(p);
}
}
}