关于哈希表的知识点梳理和创建！

2023-12-11 15:37:28

一、哈希表
1、基本思想
以数据表中的每个记录的关键字k作为自变量，通过一种函数H(k)计算出函数值。把这个与数组相联系：一块连续的储存空间（数组空间）的单元地址（即数组下标），将记录存储到这个单元中。那么这个函数我们称之为哈希函数（散列函数），所求出的函数值为哈希地址，所建立的表就为哈希表（散列表）。

2、冲突
不同的关键字，却对应一个存储地址，即k1!=k2，但H(k1) = H(k2)的这种现象称之为冲突。
3、同义词
具有不同的关键词而具有相同的哈希地址的对象称为同义词。
4、冲突大多数情况是不可避免的，主要是因为关键词的集合较大和哈希地址较少引起的。
5、对于哈希技术所研究的两个问题：（1）、如何设计哈希函数以使冲突尽可能的减少。（2）、发生了冲突之后如何解决。

二、哈希函数的构造方法
处理冲突就是为该关键字的记录找到另一个“空”的哈希地址，则通过一个新的哈希函数得到一个新的哈希地址，如果仍然发生冲突，则再求下一个，直到不再发生冲突为止。

关于哈希表的知识点梳理和创建！

三、冲突的解决方法

关于哈希表的知识点梳理和创建！

四、哈希表的查找和性能分析
与冲突发生可能性有关的因素
1、与装填因子有关
所谓的装填因子为哈希表中已经存入的元素的个数n与哈希表长m的比值，即a = n / m，当a减小时，发生冲突的可能性也在减小，反之，发生冲突的可能也在增大（a最大为1）。
2、与所构造的哈希函数有关
若哈希函数选用恰当，就可以使哈希地址尽可能的均匀分布在哈希地址空间上，从而减少发生冲突的可能性，否则，若哈希函数选择不当，就可能使哈希地址集中在某些区域，从而加大冲突发生的可能。
3、与解决冲突的哈希冲突函数有关
哈希冲突函数选择的好坏也将减少或增加发生冲突的可能性。

五、哈希表的创建
1、设计哈希表的类型

#define MaxSize 100
#define NULLKEY -1   //定义空的关键字的值
typedef int KeyType;  //关键字的类型
typedef char *InforType;  //其他类型
typedef struct node
{
    KeyType key;  //关键字域
    InforType data; // 其他数据域
    int count;  //探查次数
}HashType[MaxSize];

2、将关键字插入哈希表

//将关键字插入哈希表
void InsertHT(HashType ha,int n,KeyType k,int p)
{
    int adr,i;
    adr = k % p;
    if(ha[adr].key == NULLKEY)
    {
        ha[adr].key = k;   //x[i]可以直接插入
        ha[adr].count = 1;
    }
    else   //发生冲突时，使用线性探察法解决
    {
        i = 1;   //记录发生冲突的次数
        do{
            adr = (adr + 1) % p;
            i++;
        }while(ha[adr].key != NULLKEY);
        ha[adr].key = k;
        ha[adr].count = i;
    }
    n++;
}

3、创建哈希表

//创建哈希表
void CreatHT(HashType ha, KeyType x[],int n,int m,int p)
{
    int i,n1 = 0;

    for(i = 0;i < m;i++)
    {
        ha[i].key = NULLKEY;   //哈希表初始化
        ha[i].count = 0;
    }

    for(i = 0;i < n;i++)
    {
        InsertHT(ha,n1,x[i],p);
    }
}

4、查找关键字

//查找关键字
int  SearchHT(HashType ha,int p,KeyType k)
{
    int i = 0,adr;
    adr = k % p;
    while(ha[adr].key != NULLKEY && ha[adr].key != k)
    {
        i++;
        adr = (adr + 1) % p;   //线性探查法查找
    }
    
    if(ha[adr].key == k)  //查找成功
    {
        return adr;
    }
    else    //查找失败
    {
        return -1;
    }
}

5、查找成功，求平均查找长度

//查找成功时，求平均查找长度
void CompASL(HashType ha,int m)
{
    int i;
    int s = 0,n = 0;
    for(i = 0;i < m;i++)
    {
        if(ha[i].key != NULLKEY)
        {
            s = s + ha[i].count;
            n++;
        }
    }

    printf("查找成功的ASL=%.3f\n",s * 1.0 / n);
}

6、输出哈希表

//输出哈希表
void DisHT(HashType ha,int n,int m)
{
    float avg = 0;
    int i;

    printf("哈希地址:   ");
    for(i = 0;i < m;i++)
    {
        printf("%3d",i);
    }
    printf("\n");

    printf("哈希表关键字:");
    for(i = 0;i < m;i++)
    {
        if(ha[i].key == NULLKEY)
        {
            printf("   ");
        }
        else
        {
            printf("%3d",ha[i].key);
        }
    }
    printf("\n");

    printf("搜索次数:   ");
    for(i = 0;i < m;i++)
    {
        if(ha[i].key == NULLKEY)
        {
            printf("   ");
        }
        else
        {
            printf("%3d",ha[i].count);
        }
    }
    printf("\n");

    for(i = 0;i < m;i++)
    {
        if(ha[i].key != NULLKEY)
        {
            avg = avg + ha[i].count;
        }
    }
    avg = avg / n;
    printf("平均搜索长度为ASL(%d)=%.3f\n",n,avg);
}

完整程序代码：

/*****************************************************
copyright (C), 2014-2015, Lighting Studio. Co.,     Ltd. 
File name：
Author：Jerey_Jobs    Version:0.1    Date: 
Description：
Funcion List: 
*****************************************************/

#include <stdio.h>
#define MaxSize 100
#define NULLKEY -1   //定义空的关键字的值
typedef int KeyType;  //关键字的类型
typedef char *InforType;  //其他类型
typedef struct node
{
    KeyType key;  //关键字域
    InforType data; // 其他数据域
    int count;  //探查次数
}HashType[MaxSize];

//将关键字插入哈希表
void InsertHT(HashType ha,int n,KeyType k,int p)
{
    int adr,i;
    adr = k % p;
    if(ha[adr].key == NULLKEY)
    {
        ha[adr].key = k;   //x[i]可以直接插入
        ha[adr].count = 1;
    }
    else   //发生冲突时，使用线性探察法解决
    {
        i = 1;   //记录发生冲突的次数
        do{
            adr = (adr + 1) % p;
            i++;
        }while(ha[adr].key != NULLKEY);
        ha[adr].key = k;
        ha[adr].count = i;
    }
    n++;
}

//创建哈希表
void CreatHT(HashType ha, KeyType x[],int n,int m,int p)
{
    int i,n1 = 0;

    for(i = 0;i < m;i++)
    {
        ha[i].key = NULLKEY;   //哈希表初始化
        ha[i].count = 0;
    }

    for(i = 0;i < n;i++)
    {
        InsertHT(ha,n1,x[i],p);
    }
}

//查找关键字
int  SearchHT(HashType ha,int p,KeyType k)
{
    int i = 0,adr;
    adr = k % p;
    while(ha[adr].key != NULLKEY && ha[adr].key != k)
    {
        i++;
        adr = (adr + 1) % p;   //线性探查法查找
    }
    
    if(ha[adr].key == k)  //查找成功
    {
        return adr;
    }
    else    //查找失败
    {
        return -1;
    }
}

//查找成功时，求平均查找长度
void CompASL(HashType ha,int m)
{
    int i;
    int s = 0,n = 0;
    for(i = 0;i < m;i++)
    {
        if(ha[i].key != NULLKEY)
        {
            s = s + ha[i].count;
            n++;
        }
    }

    printf("查找成功的ASL=%.3f\n",s * 1.0 / n);
}

//输出哈希表
void DisHT(HashType ha,int n,int m)
{
    float avg = 0;
    int i;

    printf("哈希地址:   ");
    for(i = 0;i < m;i++)
    {
        printf("%3d",i);
    }
    printf("\n");

    printf("哈希表关键字:");
    for(i = 0;i < m;i++)
    {
        if(ha[i].key == NULLKEY)
        {
            printf("   ");
        }
        else
        {
            printf("%3d",ha[i].key);
        }
    }
    printf("\n");

    printf("搜索次数:   ");
    for(i = 0;i < m;i++)
    {
        if(ha[i].key == NULLKEY)
        {
            printf("   ");
        }
        else
        {
            printf("%3d",ha[i].count);
        }
    }
    printf("\n");

    for(i = 0;i < m;i++)
    {
        if(ha[i].key != NULLKEY)
        {
            avg = avg + ha[i].count;
        }
    }
    avg = avg / n;
    printf("平均搜索长度为ASL(%d)=%.3f\n",n,avg);
}

int main()
{
    int x[] = {16,74,60,43,54,90,46,31,29,88,77};
    int n,m,p,k,i;
    n = 11;
    m = 13;
    k = 29;
    p = 13;
    HashType ha;
    CreatHT(ha,x,n,m,p);
    printf("\n");
    DisHT(ha,n,m);
    i = SearchHT(ha,p,k);
    if(i == -1)
    {
        printf("为找到%d\n",k);
    }
    else
    {
        printf("ha[%d],key=%d\n",i,k);
    }
    printf("\n");

    k = 66;
    InsertHT(ha,n,k,p);
    DisHT(ha,n,m);

    printf("\n");

    return 0;
}
上一篇：python-for循环-range函数


下一篇：解析函数的幂级数理论【无穷级数收敛性】