AI 助理
备案控制台
开发者社区 云计算 文章 正文

浅析散列函数的构造方法与解决散列冲突的方法

2022-06-14 215
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 散列函数的构造方法数字分析法平方取中法平方取中法测试测例1测例2折叠法折叠法测试测例1测例2随机数法随机数法测试测例1除留余数法解决散列冲突的方法开放定址法公共溢出区法以开放定地法为基础的全部代码全部代码测试效果以公共溢出区法为基础的全部代码全部代码测试效果尾言


散列函数的构造方法

数字分析法


数字分析法常用于手机号码、身份证号码、订单编号等位数较多的关键字，对于身份证号码，前六位为地址码，中间八位为出生日期码，后三位为顺序码，最后一位为校验码；世间不缺乏生活地方、出生年月日相同的人，那么可能会增大关键字冲突的几率，我们选取后四位作为关键字的地址，若还是会出现冲突，可以采用将后四位的前两位与后两位相加、颠倒后四位关键字的顺序等方法降低关键字冲突。

数字分析法实现代码如下：

/**
 数字分析法:以手机号码，身份证为例，取后四位*/
int NumAnalysis(long key)
{
  return key % 10000;
}

数字分析法加强版如下：

/**
 若数字分析法产生冲突，则将后四位的前两位与后两位相加做为关键字地址*/
int SumNumbers(int key)
{
  //此处传入的key为产生冲突的关键字的后四位
  int FirstTwo = key / 100;
  int LastTwo = key % 100;
  return FirstTwo + LastTwo;
}


平方取中法

平方取中法：顾名思义，对关键字进行平方处理，然后取中间n位数，抽取的位数根据实际而定。

平方取中法实现代码如下：

此方法所取得中间位由key的长度决定，如果key长度为4，则取平方的中间三位；如果key的长度为3，则取平方的中间的二位；以此类推。

int SquareMedian(int key)
{
  int square = key * key;
  int length = 0;
  //获取关键字的长度
  length = KeyLength(key);
  //Times(n);方法为求10的倍数，比如Times(2);则返回100
  square = square / Times(length - 2);
  square = square % Times(length - 1);
  return square;
}


平方取中法测试

测例1

以key=1234为例，其平方为1522756,key的长度为四，则取中间三位做为关键字存储地址，即227。

 int testNum = 1234;
  printf("测试数字为:%d\n",testNum);
  printf("测试数字的平方为:%d\n", testNum * testNum);
  printf("中间位为:%d", SquareMedian(testNum));

image.png


测例2

以key=4321为例，其平方为18671041,key的长度为四，则取中间三位做为关键字存储地址，即671与710都可以。

int testNum = 4321;
  printf("测试数字为:%d\n",testNum);
  printf("测试数字的平方为:%d\n", testNum * testNum);
  printf("中间位为:%d", SquareMedian(testNum));

image.png


折叠法

折叠法是将关键字从左到右按n位数为一组，切割成m组，若最后一组不足n位，也为一组，最后将切割的m组数据相加之和做为关键字的地址。

折叠法实现代码如下：

/**
 折叠法，按照散列表表长(n)将关键字分为m组*/
long FoldMethod(long key)
{
  //设散列表表长为3位，则将9876543210分为4组
  long num = key;
  int tableLength = 3;
  long sum = 0;
  //此处以key为9876543210为例
  //sum = 987 + 456 + 321 + 0 = 1962
  //result = 962
  //获取关键字长度，即10位
  int length = KeyLength(num);
  //10.0 / 3 = 3.3 > 3,即还有最后一位未分组，但又不足三位，也纳入组数
  /*if ((float)length / tableLength > tableLength)
  {
    group = tableLength + 1;
  }*/
  while (length > 0)
  {
    //sum = key % 1000;
    //9876543210 / (10*(10-3))即取前三位
    //即对最后一位0，进行取值时
    if (length - tableLength < 0)
    {
      sum += key % 10;
      length = length - tableLength;
      printf("sum=%d\n", sum);
    }
    else
    {
      sum += num / Times(length - tableLength);
      //printf("次数测试=%ld\n", Times(7));
      num = num % Times(length - tableLength);
      length = length - tableLength;
      printf("sum=%d\n", sum);
    }
  }
  //只取结果的后三位，故判定分组之和是否为三位数
  if (sum / 1000 > 0)
  {
    //大于0，则判定结果不为三位数，则对其进行取模操作，取其后三位
    sum %= 1000;
  }
  return sum;
}


折叠法测试

测例1

以key=987654321为例，将其按3位一组分成三部分:987+654+321=1962;但我们的目的是取三位做为关键字的地址，故对1962进行模运算，得到后三位：962。

 long testNum = 987654321;
  printf("测试数字为=%ld\n", testNum);
  printf("关键字长度为:%d\n", KeyLength(testNum));
  long result = FoldMethod(testNum);
  printf("折叠法后三位散列地址为:%ld", result);

image.png


测例2

以key=123456为例，将其按3位一组分成三部分:123+456=579;对所获得的结果进行位数判定，结果为符合要求，长度为3，则关键字地址为：579

   long testNum = 123456;
  printf("测试数字为=%ld\n", testNum);
  printf("关键字长度为:%d\n", KeyLength(testNum));
  long result = FoldMethod(testNum);
  printf("折叠法后三位散列地址为:%ld", result);

image.png


随机数法

顾名思义，取随机数做为关键字的散列地址，公式为：

f(key)=random(key)

随机数法实现代码如下：

/**
 随机数法:f(key) = Random(key)*/
int RandomAddr(int key)
{
  srand(key);
  int addr = rand();
  return addr;
}


随机数法测试

测例1

以数组 { 12,67,56,16,25,37,22,29,15,47,48,34 }为例子

 int HashArray[12] = { 12,67,56,16,25,37,22,29,15,47,48,34 };
  for (int i = 0; i < 12; i++)
  {
      int result = RandomAddr(HashArray[i]);
      printf("result = %d\n", result);
  }

image.png


除留余数法

此方法最为常用，其关键为寻找合适的除数P。对于散列表长为m的散列函数公式为：

f(key)=key mod p (p <= m)

除留余数法实现代码如下：

/**
 散列函数：除留余数法*/
int ModHash(int key)
{
  return key % size;
}


解决散列冲突的方法


开放定址法

开放定址法定义为：如果不存在冲突，则直接使用除留余数法获取散列地址并保存到相应的散列表下标中；反之，则寻找空的地址，直到记录存入为止。

开放定址法插入关键字代码如下：

/**
 往哈希表内插入关键字*/
void InsertHash(HashTable *H,int key)
{
  int addr = ModHash(key);
  //如果不为NULLKEY，则说明存在冲突项，采用开放定址法的线性探索，不断自增地址取余，直到得到空余的下标，然后进行插入
  while (H->elem[addr] != NULLKEY)
  {
    addr = (addr + 1) % size;
  }
  H->elem[addr] = key;
}


公共溢出区法

将冲突的关键字保存到溢出散列中表，查找关键字时，首先查找基本表，若基本表不存在，则前往溢出表进行查找。

公共溢出区法插入关键字代码如下：

/**
 往哈希表内插入关键字*/
void InsertHash(HashTable* baseTable, HashTable* overFlow,int key)
{
  int addr = ModHash(key);
  //如果不为NULLKEY，则说明存在冲突项，采用公共溢出区法，将冲突项保存到溢出表中
  if (baseTable->elem[addr] != NULLKEY)
  {
    overFlow->elem[overIndex++] = key;
  }
  else
  {
    baseTable->elem[addr] = key;
  }
}


以开放定地法为基础的全部代码


全部代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
//宏定义
#define Status int
#define SUCCESS 1
#define FAIL 0
#define TABLESIZE 12
#define NULLKEY -32768
int size = 0;//散列表表长
//结构体
typedef struct
{
  int count; //数据个数
  int *elem;  //数据存储的数组
}HashTable;
/**
 初始化哈希表*/
Status InitHash(HashTable *H)
{
  size = TABLESIZE;
  H->count = size;
  H->elem = (int *)malloc(size * sizeof(int));
  //如果内存申请失败，则初始化失败
  if (!H->elem)
  {
    return FAIL;
  }
  //将哈希表所有地址初始化为NULLKEY
  for (int i = 0; i < size; i++)
  {
    H->elem[i] = NULLKEY;
  }
  return SUCCESS;
 }
/**
 散列函数：除留余数法*/
int ModHash(int key)
{
  return key % size;
}
/**
 散列函数:平方取中法
 截取长度为关键字长度减1*/
int SquareMedian(int key)
{
  int square = key * key;
  int length = 0;
  //获取关键字的长度
  length = KeyLength(key);
  square = square / Times(length - 2);
  square = square % Times(length - 1);
  return square;
}
/**
 数字分析法:以手机号码，身份证为例，取后四位*/
int NumAnalysis(long key)
{
  return key % 10000;
}
/**
 若数字分析法产生冲突，则将后四位的前两位与后两位相加做为关键字地址*/
int SumNumbers(int key)
{
  //此处传入的key为产生冲突的关键字的后四位
  int FirstTwo = key / 100;
  int LastTwo = key % 100;
  return FirstTwo + LastTwo;
}
/**
 10的倍数*/
long Times(int num)
{
  long numSum = 1;
  while (num-- > 0)
  {
    numSum *= 10;
  }
  return numSum;
}
/**
 折叠法，按照散列表表长(n)将关键字分为m组*/
long FoldMethod(long key)
{
  //设散列表表长为3位，则将9876543210分为4组
  long num = key;
  int tableLength = 3;
  long sum = 0;
  //此处以key为9876543210为例
  //sum = 987 + 456 + 321 + 0 = 1962
  //result = 962
  //获取关键字长度，即10位
  int length = KeyLength(num);
  //10.0 / 3 = 3.3 > 3,即还有最后一位未分组，但又不足三位，也纳入组数
  /*if ((float)length / tableLength > tableLength)
  {
    group = tableLength + 1;
  }*/
  while (length > 0)
  {
    //sum = key % 1000;
    //9876543210 / (10*(10-3))即取前三位
    //即对最后一位0，进行取值时
    if (length - tableLength < 0)
    {
      sum += key % 10;
      length = length - tableLength;
      printf("sum=%d\n", sum);
    }
    else
    {
      sum += num / Times(length - tableLength);
      //printf("次数测试=%ld\n", Times(7));
      num = num % Times(length - tableLength);
      length = length - tableLength;
      printf("sum=%d\n", sum);
    }
  }
  //只取结果的后三位，故判定分组之和是否为三位数
  if (sum / 1000 > 0)
  {
    //大于0，则判定结果不为三位数，则对其进行取模操作，取其后三位
    sum %= 1000;
  }
  return sum;
}
/**
 随机数法:f(key) = Random(key)*/
int RandomAddr(int key)
{
  srand(key);
  int addr = rand();
  return addr;
}
int KeyLength(long key)
{
  int i = 0;
  while (key > 0)
  {
    key = key / 10;
    i++;
  }
  return i;
}
/**
 往哈希表内插入关键字*/
void InsertHash(HashTable *H,int key)
{
  int addr = ModHash(key);
  //如果不为NULLKEY，则说明存在冲突项，采用开放定址法的线性探索，不断自增地址取余，直到得到空余的下标，然后进行插入
  while (H->elem[addr] != NULLKEY)
  {
    addr = (addr + 1) % size;
  }
  H->elem[addr] = key;
}
/**
 在哈希表内进行关键字查找*/
int SearchHash(HashTable* H, int key)
{
  int addr = ModHash(key);
  //地址冲突
  while (H->elem[addr] != key)
  {
    addr = (addr + 1) % size;
    //等于NULLKEY则说明关键字不存在
    //如果addr循环了一圈还没有找到，并且最终与开始的addr相等，则说明没有在冲突的情况下找到该关键字
    if (H->elem[addr] == NULLKEY || addr == ModHash(key))
    {
      return FAIL;
    }
  }
  return addr;
}
/**
 主函数*/
void main(void)
{
  int HashArray[12] = { 12,67,56,16,25,37,22,29,15,47,48,34 };
  int index;
  int result;
  HashTable H;
  InitHash(&H);
  for (int i = 0; i < size; i++)
  {
    InsertHash(&H,HashArray[i]);
  }
  printf("哈希表为：");
  for (int i = 0; i < size; i++)
  {
    printf("%d\t", H.elem[i]);
  }
  printf("\n");
  printf("请输入你要查找的关键字:");
  scanf_s("%d", &index);
  result = SearchHash(&H, index);
  if (result == 0)
  {
    printf("没有在哈希表内查到相关关键字\n");
    return;
  }
  printf("你所查找的关键字在哈希表内的下标为:%d", result);
}


测试效果

以数组 { 12,67,56,16,25,37,22,29,15,47,48,34 };

查找关键字25，返回下标1

image.png

查找关键字16，返回下标4

image.png

查找关键字33，在哈希表内没有查到该关键字

image.png


以公共溢出区法为基础的全部代码


全部代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
//宏定义
#define Status int
#define SUCCESS 1
#define FAIL 0
#define TABLESIZE 12
#define NULLKEY -32768
int size = 0;//散列表表长
int overIndex = 0;//公共溢出区表下标
//结构体
typedef struct
{
  int count; //数据个数
  int* elem;  //数据存储的数组
}HashTable;
/**
 初始化哈希表*/
Status InitHash(HashTable* H)
{
  size = TABLESIZE;
  H->count = size;
  H->elem = (int*)malloc(size * sizeof(int));
  //如果内存申请失败，则初始化失败
  if (!H->elem)
  {
    return FAIL;
  }
  //将哈希表所有地址初始化为NULLKEY
  for (int i = 0; i < size; i++)
  {
    H->elem[i] = NULLKEY;
  }
  return SUCCESS;
}
/**
 散列函数：除留余数法*/
int ModHash(int key)
{
  return key % size;
}
int KeyLength(long key)
{
  int i = 0;
  while (key > 0)
  {
    key = key / 10;
    i++;
  }
  return i;
}
/**
 往哈希表内插入关键字*/
void InsertHash(HashTable* baseTable, HashTable* overFlow,int key)
{
  int addr = ModHash(key);
  //如果不为NULLKEY，则说明存在冲突项，采用公共溢出区法，将冲突项保存到溢出表中
  if (baseTable->elem[addr] != NULLKEY)
  {
    overFlow->elem[overIndex++] = key;
  }
  else
  {
    baseTable->elem[addr] = key;
  }
}
/**
 在哈希表内进行关键字查找*/
int SearchHash(HashTable* baseTable, HashTable* overFlow, int key)
{
  int addr = ModHash(key);
  //地址冲突
  if (baseTable->elem[addr] != key)
  {
    //在溢出表进行寻找
    for (int i = 0; i < size; i++)
    {
      if (overFlow->elem[i] == key)
      {
        return i;
      }
    }
    //没有匹配项
    return -1;
  }
  return addr;
}
/**
 主函数*/
void main(void)
{
  int HashArray[12] = {12,67,56,16,25,37,22,29,15,47,48,34 };
  int index;
  int result;
  HashTable baseTable,overFlow;
  InitHash(&baseTable);
  InitHash(&overFlow);
  /*printf("初始化数据为:");
  for (int i = 0; i < size; i++)
  {
    printf("%d ", baseTable.elem[i]);
  }
  printf("\n");*/
  for (int i = 0; i < size; i++)
  {
    InsertHash(&baseTable,&overFlow,HashArray[i]);
  }
  printf("基本哈希表数据为：");
  for (int i = 0; i < size; i++)
  {
    printf("%d\t", baseTable.elem[i]);
  }
  printf("\n");
  printf("溢出哈希表数据为：");
  for (int i = 0; i < size; i++)
  {
    printf("%d\t", overFlow.elem[i]);
  }
  printf("\n");
  printf("请输入你要查找的关键字:");
  scanf_s("%d", &index);
  result = SearchHash(&baseTable,&overFlow,index);
  if (result == -1)
  {
    printf("没有在哈希表内查到相关关键字\n");
    return;
  }
  printf("你所查找的关键字在哈希表内的下标为:%d", result);
}

测试效果

以数组 { 12,67,56,16,25,37,22,29,15,47,48,34 };

查找关键字25，在基本表中，返回基本表下标1

image.png

查找关键字34，在溢出表中，返回溢出表下标2

image.png

查找关键字17，在哈希表内没有查到该关键字

image.png


尾言

一个设计的几乎完美的哈希表，在应用于不同场合，都会出现散列冲突，只有根据不同场合，不同环境设计不同散列函数和处理散列冲突的方法可以有效避免散列冲突。

文章标签：
存储
FranzLiszt1847
目录
相关文章
人不走空
|
6月前
|
存储 算法 Serverless
解决哈希冲突的方式
解决哈希冲突的方式
人不走空
61 0
人物我非-32022
|
17天前
|
存储 安全 算法
散列哈希
【10月更文挑战第16天】
人物我非-32022
12 1
古明地盆
|
1月前
|
存储 索引 Python
什么是可哈希对象，它的哈希值是怎么计算的？
什么是可哈希对象，它的哈希值是怎么计算的？
古明地盆
63 6
..清风
|
11月前
|
存储 Serverless
不允许你还没有了解哈希表、哈希桶、哈希冲突的解决，如何避免冲突
不允许你还没有了解哈希表、哈希桶、哈希冲突的解决，如何避免冲突
..清风
85 0
晨出
SWUSTOJ 1013: 哈希表（开放定址法处理冲突）
SWUSTOJ 1013: 哈希表（开放定址法处理冲突）
晨出
107 0
chengfengpolang
|
数据安全/隐私保护
散列函数是干什么的？底层原理是什么？
散列函数是干什么的？底层原理是什么？
chengfengpolang
365 0
愿天堂没有BUG（公众号同名）
|
存储 算法 Ubuntu
趣谈哈希表优化：从规避 Hash 冲突到利⽤ Hash 冲突
导读： 本文从哈希表传统设计与解决思路入手，深入浅出地引出新的设计思路：从尽量规避哈希冲突，转向了利⽤合适的哈希冲突概率来优化计算和存储效率。新的哈希表设计表明 SIMD 指令的并⾏化处理能⼒的有效应⽤能⼤幅度提升哈希表对哈希冲突的容忍能⼒，进⽽提升查询的速度，并且能帮助哈希表进⾏极致的存储空间压缩。
愿天堂没有BUG（公众号同名）
235 0
派小星_
|
存储 算法 Java
哈希函数
性质一：in的输入域无穷，比方说可以传入任意长度的字符串。但是在有些工程中也会给输入域规定范围。
派小星_
181 0
哈希函数
神奇的程序员
|
存储 算法 Serverless
哈希函数的理解
哈希函数的理解
神奇的程序员
129 0
哈希函数的理解
游客3bfkcht77micg
|
存储
浅析哈希源码
浅析哈希源码
游客3bfkcht77micg
97 0
浅析哈希源码