数据结构 --- 哈希表

哈希表（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;
    }
}