【数据结构与算法】【查找】哈希表的代码实现

柔情只为你懂 2022-08-13 13:36 180阅读 0赞

哈希表也叫散列表，散列存储结构主要是面向查找的。

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。

散列地址/存储位置 = f（关键字）

哈希表/散列表的构造主要依赖两个问题的解决：

1、散列函数的构造方法；

2、散列冲突的处理方法。

构造散列函数的两个原则：

1、计算简单；

2、散列地址/存储位置/f()函数值均匀分布。

散列函数的构造方法：

<table style="border-collapse:collapse; margin-top:10px; margin-bottom:10px; background-color:inherit; width:940px"> 
 <tbody style="background-color:inherit"> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:184.45454078469405px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">构造方法</span></span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:340.8181831974631px"> <span style="background-color:inherit"><span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">散列函数</span></span></span></td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:353.5454506007112px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">应用场景</span></span></span> 
    </div> </td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:184.45454078469405px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">直接定址法</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:340.8181831974631px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">f（key）= a * key +b （a、b为常数）</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:353.5454506007112px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">适合<span style="line-height:1.5">于</span><span style="color:rgb(255,0,0); line-height:1.5">知道</span><span style="line-height:1.5">关键字分布，且</span><span style="background-color:inherit; line-height:1.5"><span style="color:#ff0000; background-color:inherit">查找表较小且连续</span>的情况。</span></span></span> 
    </div> </td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:63.636374170130125px; background-color:inherit; width:184.45454078469405px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">数字分析法</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:63.636374170130125px; background-color:inherit; width:340.8181831974631px"> <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px"><span style="color:#ff0000; background-color:inherit">抽取</span>部分数字进行诸如：反转、左环位移、右环位移、前两数与后两数相加</span></span></td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:63.636374170130125px; background-color:inherit; width:353.5454506007112px"> <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">适合于<span style="color:#ff0000; background-color:inherit">知道</span>关键字分布，且关键字位数<span style="color:#ff0000; background-color:inherit">较多</span>，关键字的<span style="color:#ff0000; background-color:inherit">若干位分布比较均匀</span>的情况。</span></span></td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:184.45454078469405px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">平方取中法</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:340.8181831974631px"> <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">数字平方后取中间的几位</span></span></td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:353.5454506007112px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">适合于<span style="color:#ff0000; background-color:inherit">不知道</span>关键字分布，且关键字位数<span style="color:#ff0000; background-color:inherit">不多</span>的情况。</span></span> 
    </div> </td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:184.45454078469405px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">折叠法</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:340.8181831974631px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">将数字串平均分几个部分后求和</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:353.5454506007112px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">适合于<span style="color:#ff0000; background-color:inherit">不知道</span>关键字分布，且<span style="line-height:1.5">关键字</span><span style="line-height:1.5">位数<span style="color:#ff0000; background-color:inherit">较多</span>的情况。</span></span></span> 
    </div> </td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:184.45454078469405px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px"><span style="color:#ff0000; background-color:inherit">除留余数法</span>（最常用）</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:340.8181831974631px"> <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">f（key）= key mod p（p &lt;= m）</span></span></td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:353.5454506007112px"> <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">NA</span></span></td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:30.000015905080943px; background-color:inherit; width:184.45454078469405px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">随机数法</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:30.000015905080943px; background-color:inherit; width:340.8181831974631px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">f（key）= random（key）</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:30.000015905080943px; background-color:inherit; width:353.5454506007112px"> <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">适合于关键字<span style="color:#ff0000; background-color:inherit">长度不等</span>的情况。</span></span></td> 
  </tr> 
 </tbody> 
</table>

散列冲突的处理方法：

<table style="border-collapse:collapse; margin-top:10px; margin-bottom:10px; background-color:inherit; width:939px"> 
 <tbody style="background-color:inherit"> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:246px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">处理方法</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:596px"> <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">散列函数</span></span></td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:246px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">开放定址法（线性探测）</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:596px"> <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">fi（key）= （f（key）+ di） MOD m<br style="background-color:inherit"> di = 1, 2, 3, ...., m-1</span></span></td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:31px; background-color:inherit; width:246px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">开放定址法（二次探测）</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:31px; background-color:inherit; width:596px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">fi（key）= （f（key）+ di） MOD m</span></span> 
    </div> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">di = 1^2, -1^2, 2^2, -<span style="line-height:1.5">2^2, ..., q^2, -q^2, q&lt;=m/2</span></span></span> 
    </div> </td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:246px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">开放定址法（随机探测）</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:596px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">fi（key）= （f（key）+ di） MOD m</span></span> 
    </div> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">di是一个伪随机数列，即：用同样的随机种子，每次得到的数列是相同的。</span></span> 
    </div> </td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:246px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">再散列函数法</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:596px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">fi（key）= RHi（key）</span></span> 
    </div> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">i = 1, 2, ..., k &nbsp; &nbsp; RHi是不同散列函数，可以使用不同的<span style="line-height:1.5">散列函数构造方法构造。</span></span></span> 
    </div> </td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:246px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">链地址法</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:596px"> <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">散列表中只存储指针，指针指向同义词子表。</span></span></td> 
  </tr> 
  <tr style="background-color:inherit"> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:246px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">公共区溢出法</span></span> 
    </div> </td> 
   <td style="word-break:break-all; border:1px solid rgb(153,153,153); padding:5px 10px; min-height:25px; min-width:25px; height:25px; background-color:inherit; width:596px"> 
    <div style="min-width:2px; background-color:inherit"> 
     <span style="background-color:inherit"><span style="font-family:SimSun; font-size:18px">散列表中只存储一个记录，其他同义词存储在公共溢出区。</span></span> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

散列表查找性能的分析角度：

1、散列函数是否均匀；

2、处理冲突的方法；

3、散列表的装填因子：装填因子 = 填入表中的记录个数 / 散列表的长度。装填因子越大，冲突的可能性越大。通常做法是将散列表的长度设置得比查找集合大，以空间换时间，提高查找效率。

// Filename: hash.h
    
    #ifndef HASH_H_INCLUDED
    #define HASH_H_INCLUDED
    
    #define HASH_TABLE_SIZE 10  // Hash表大小，根据实际情况修改
    typedef int HElemType; // Hash表中存储的元素类型，根据实际情况修改
    #define HASH_ELEM_INVALID_VALUE 0x7FFFFFFF // 无效的元素值，假设为最大正整数
    typedef struct HashTable
    {
        HElemType *pElem;   // Hash表，数组形式，动态分配, 每个元素初始值为HASH_ELEM_INVALID_VALUE
        int totalnum;       // Hash表中能够存储的元素，Hash表申请后固定不变
        int existnum;       // Hash表中已经存储的元素，初始为0，每插入一个加一
    }HashTable;
    
    #define HASH_ERROR_INIT         1
    #define HASH_ERROR_MALLOC       2
    #define HASH_ERROR_KEY          3
    #define HASH_ERROR_FULL         4
    #define HASH_ERROR_NOT_FOUND    5
    
    int hash_main();
    
    #endif // HASH_H_INCLUDED

// Filename: hash.c
    
    #include <stdio.h>
    #include <stdlib.h>
    #include "public.h"
    #include "hash.h"
    
    // 哈希表初始化，哈希表长度为size
    int InitHashTable(HashTable *pH, int size)
    {
        int i = 0;
    
        if ((!pH) || (size <= 0))
        {
            return HASH_ERROR_INIT;
        }
    
        pH->pElem =  malloc(sizeof(HElemType) * size);
        if (!pH->pElem)
        {
            return HASH_ERROR_MALLOC;
        }
    
        for (i = 0; i < size; i++)
        {
            pH->pElem[i] = HASH_ELEM_INVALID_VALUE;
        }
        pH->totalnum = size;
        pH->existnum = 0;
    
        return OK;
    }
    
    // 散列函数：计算散列地址
    int Hash(int key)
    {
        return key % HASH_TABLE_SIZE;
    }
    
    // 查找关键字，返回散列地址
    int SearchHash(HashTable *pH, int key, int *pAddr)
    {
        if ((!pH) || (!pAddr)) return ERROR;
    
        // key值不能和Hash表元素的初始默认值相同，否则就会被后面的元素覆盖
        if (HASH_ELEM_INVALID_VALUE == key) return HASH_ERROR_KEY;
    
        // 进行查找操作
        *pAddr = Hash(key);
        while (pH->pElem[*pAddr] != key)
        {
            *pAddr = (*pAddr + 1) % HASH_TABLE_SIZE;
            if ((HASH_ELEM_INVALID_VALUE == pH->pElem[*pAddr]) || (*pAddr == Hash(key)))
            {
                return HASH_ERROR_NOT_FOUND;
            }
        }
    
        return OK;
    }
    
    // 插入元素，冲突处理方法：开放定址法线性探测
    int InsertHash(HashTable *pH, int key)
    {
        int addr;
    
        if (!pH) return ERROR;
    
        // key值不能和Hash表元素的初始默认值相同，否则就会被后面的元素覆盖
        if (HASH_ELEM_INVALID_VALUE == key) return HASH_ERROR_KEY;
    
        // 表满则无法插入，返回错误
        if (pH->existnum >= pH->totalnum) return HASH_ERROR_FULL;
    
        // 已经插入的元素，不能重复插入
        if (OK == SearchHash(pH, key, &addr))
        {
            printf("该元素已经在哈希表中，无需重复插入\n");
            return OK;
        }
    
        // 进行插入操作
        addr = Hash(key);
        while (HASH_ELEM_INVALID_VALUE != pH->pElem[addr])
        {
            addr = (addr + 1) % HASH_TABLE_SIZE;
        }
    
        pH->pElem[addr] = key;
        pH->existnum++;
        return OK;
    }
    
    // 删除关键字，有则删除，没有不做操作
    int DeleteHash(HashTable *pH, int key)
    {
        int addr;
    
        if (!pH) return ERROR;
    
        // key值不能和Hash表元素的初始默认值相同，否则就会被后面的元素覆盖
        if (HASH_ELEM_INVALID_VALUE == key) return HASH_ERROR_KEY;
    
        if (OK == SearchHash(pH, key, &addr))
        {
            if (pH->existnum <= 0) pH->existnum = 1; // 此处应提示异常，说明程序实现有问题;
            pH->pElem[addr] = HASH_ELEM_INVALID_VALUE;
            pH->existnum--;
        }
    
        //printf("DeleteHash(): 未找到待删除元素%d.", key);
        return OK;
    }
    
    // 打印哈希表
    void PrintHash(HashTable *pH)
    {
        int i;
        if (!pH) return;
    
        printf("哈希表: 空间大小: %d, 元素数量: %d.\n", pH->totalnum, pH->existnum);
        printf("-----------------------------------\n");
        printf("下标    元素值\n");
        printf("-----------------------------------\n");
    
        for (i = 0; i < pH->totalnum; i++)
        {
            printf("%-8d%-6d\n", i, pH->pElem[i]);
        }
        printf("-----------------------------------\n");
        return;
    }
    
    int hash_main()
    {
        int input;
        int addr;
        int key;
        int retCode;
        HashTable H;
    
    	while (1)
    	{
    		printf("----------------------------------\n");
    		printf("哈希表基本操作\n");
    		printf("----------------------------------\n");
    		printf("0.创建/初始化哈希表\n");
    		printf("1.插入元素\n");
    		printf("2.删除元素\n");
    		printf("3.查找元素\n");
    		printf("4.打印哈希表\n");
    		printf("9.退出系统\n");
    		printf("----------------------------------\n");
    		printf("请选择:");
    		scanf("%d", &input);
    		getchar();
    
    		switch (input)
    		{
                case 0:
                    retCode = InitHashTable(&H, HASH_TABLE_SIZE);
                    if (OK == retCode)
                    {
                        printf("创建/初始化哈希表成功!\n");
                    }
                    else
                    {
                        printf("创建/初始化哈希表失败!!!\n");
                    }
                    break;
    
    
                case 1:
                    printf("请输入待插入元素: --> ");
                    scanf("%d", &key);
                    retCode = InsertHash(&H, key);
                    if (OK == retCode)
                    {
                        printf("插入元素成功!\n");
                    }
                    else
                    {
                        printf("插入元素失败!!!\n");
                    }
                    break;
    
                case 2:
                    printf("请输入待删除元素: --> ");
                    scanf("%d", &key);
                    retCode = DeleteHash(&H, key);
                    if (OK == retCode)
                    {
                        printf("删除元素成功!\n");
                    }
                    else
                    {
                        printf("删除元素失败!!!\n");
                    }
                    break;
    
                case 3:
                    printf("请输入待查找元素: --> ");
                    scanf("%d", &key);
                    retCode = SearchHash(&H, key, &addr);
                    if (OK == retCode)
                    {
                        printf("查找元素成功, 所在位置为: %d.\n", addr);
                    }
                    else
                    {
                        printf("查找元素失败!!!\n");
                    }
                    break;
    
                case 4:
                    PrintHash(&H);
                    break;
    
                case 9:
                    printf("系统已退出！\n");
                    exit(0);
    
                default:
                    printf("无效，请重新选择操作！\n");
                    exit(0);
    		}
    	}
    
        return 0;
    }