数据结构 --- 哈希表

哈希表（Hash Table），也叫散列表，是一种根据关键码值（Key value）而直接进行访问的数据结构。

一、基本原理

1. 哈希函数

   • 哈希表通过一个特定的哈希函数，将关键码映射到表中的一个位置。这个位置通常称为哈希地址或索引。
   • 例如，对于一个整数关键码，可以使用简单的取余函数作为哈希函数，将关键码对哈希表的大小取余，得到对应的哈希地址。

2. 冲突解决

   • 由于不同的关键码可能会映射到相同的哈希地址，这就会产生冲突。解决冲突的方法有多种，常见的有开放寻址法和链地址法。
   • 开放寻址法：当发生冲突时，通过探测哈希表中的其他位置来寻找空闲位置。例如线性探测，就是依次检查下一个位置，直到找到空闲位置。
   • 链地址法：将哈希地址相同的元素存储在一个链表中。当查找元素时，先通过哈希函数计算出哈希地址，然后在对应的链表中进行查找。

二、特点和优势

1. 快速查找

   • 哈希表能够在平均情况下以接近常数时间的复杂度进行查找、插入和删除操作，效率非常高。
   • 只要哈希函数设计合理，能够将关键码均匀地分布在哈希表中，就可以快速定位到元素的位置。

2. 灵活性

   • 可以存储不同类型的关键码和值，只要能够为这些关键码定义合适的哈希函数。
   • 适用于各种数据结构和算法中，如数据库索引、编译器符号表、缓存等。

三、应用场景

1. 数据库索引

   • 在数据库中，哈希表可以用于快速查找特定的数据行。通过将表中的关键列作为关键码，经过哈希函数计算得到哈希地址，然后将数据存储在对应的位置。这样在查询时，可以快速定位到数据所在的位置，提高查询效率。

2. 缓存

   • 缓存系统通常使用哈希表来存储已经访问过的数据，以便下次访问时能够快速获取。当需要访问某个数据时，先计算其哈希地址，然后在哈希表中查找。如果找到，则直接返回缓存中的数据；如果没有找到，则从数据源获取数据并存储到缓存中。

3. 编译器符号表

   • 在编译器中，符号表用于存储程序中的变量、函数等标识符的信息。哈希表可以作为符号表的实现方式，通过将标识符作为关键码，快速查找其对应的类型、作用域等信息。

以存储通讯录为例 

#ifndef __HASH_H__
#define __HASH_H__#define HASH_SIZE 27      //26个字母表数量以及符号typedef struct per        //数据结构体
{char name[32];char tel[32];
}hsdatatype;typedef struct hsnode     //结构体类型
{hsdatatype data;struct hsnode *pnext;
}hsnode_t;int insert_hashtable(hsdatatype data);
void hashtable_array();
void destroy_hash();#endif

#include "hash.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>hsnode_t *hashtable[HASH_SIZE] = {NULL};int hash_func(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_func(data.name[0]);hsnode_t *p = (hsnode_t *)malloc(sizeof(hsnode_t));if(!p)return -1;p->data = data;p->pnext = NULL;/*if(!hashtable[addr])hashtable[addr] = p;else {while(hashtable[addr]->pnext && !strcmp(hashtable[addr]->data.name,data.name)){hashtable[addr] = hashtable[addr]->pnext;}p->pnext = hashtable[addr];hashtable[addr]->pnext = p;}*/p->pnext = hashtable[addr];hashtable[addr] = p;return 0;
}void link_array(hsnode_t *p)        
{while(p){printf("%s  %s\n",p->data.name,p->data.tel);p = p->pnext;}
}void hashtable_array()        //遍历哈希表
{int i = 0;while(i < HASH_SIZE){/*while(hashtable[i]){//printf("%s  %s\n",hashtable[i]->data.name,hashtable[i]->data.tel);//hashtable[i] = hashtable[i]->pnext;link_array(hashtable[i]);}*/link_array(hashtable[i]);++i;}
}hsnode_t *find_hash(char *name)        //通过名字在哈希表中查找数据，返回地址
{int addr = hash_func(name[0]);hsnode_t *p = hashtable[addr];while(p){if(!strcmp(name,p->data.name)){return p;}p = p->pnext;}return NULL;
}void destroy_link(hsnode_t *p)    //销毁链表
{while(p){hsnode_t *q = p;p = p->pnext;free(q);}
}void destroy_hash()    //销毁哈希表
{int i = 0;while(i < HASH_SIZE){destroy_link(hashtable[i]);++i;}
}