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

简介: 散列函数的构造方法数字分析法平方取中法平方取中法测试测例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


尾言


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

相关文章
解决办法:无法修正错误,因为您要求某些软件包保持现状,就是它们破坏了软件包间的依赖关系
解决办法:无法修正错误,因为您要求某些软件包保持现状,就是它们破坏了软件包间的依赖关系
1490 0
解决办法:无法修正错误,因为您要求某些软件包保持现状,就是它们破坏了软件包间的依赖关系
|
4月前
|
机器学习/深度学习 数据采集 人工智能
几周速通大模型实习,你需要做什么?
这是一篇关于转行进入大模型AI应用开发领域的经验分享。作者凭借自身两年开发经验成功转型,并详细列出学习路线:从Python语言、框架(如LangChain、Flask、FastAPI)到NLP、LLM微调,涉及强化学习、数据清洗、RAG调优等技术。他还提到论文复现、量化模型的重要性,以及高学历和顶会论文对进入顶级公司(如九坤、幻方)的帮助。文中提及面试经历和技术挑战,强调技术深度与努力的必要性。最后,作者鼓励读者坚持学习,并计划全平台发布教程。
|
11月前
|
敏捷开发 监控 测试技术
深入理解自动化测试:从理论到实践
自动化测试在软件开发中扮演着至关重要的角色,它不仅提高了测试效率,还确保了软件质量的一致性和可靠性。本文将引导你了解自动化测试的核心概念,探讨其在不同开发阶段的应用,并通过一个简单的代码示例,展示如何实现一个基本的自动化测试脚本。无论你是初学者还是有经验的开发者,这篇文章都将为你提供宝贵的见解和实用的技能。
233 1
|
7月前
|
测试技术
RBTree(红黑树)的介绍和实现
RBTree(红黑树)的介绍和实现
|
10月前
|
算法 搜索推荐
解读双编码器和交叉编码器:信息检索中的向量表示与语义匹配
在信息检索领域(即从海量数据中查找相关信息),双编码器和交叉编码器是两种至关重要的工具。它们各自拥有独特的工作机制、优势和局限性。本文将深入探讨这两种核心技术。
348 3
解读双编码器和交叉编码器:信息检索中的向量表示与语义匹配
|
存储 关系型数据库 分布式数据库
揭秘PolarDB:中国云原生数据库的超级英雄,如何颠覆传统数据存储?
在数字化时代,数据成为企业的核心资产,而云原生数据库则是推动企业转型的关键。PolarDB凭借其先进的存储计算分离架构,在性能、可靠性和易用性方面脱颖而出,成为国内领先的选择。它支持多种数据库引擎,提供多副本存储机制,并采用按量付费模式,有效降低管理和成本压力,助力企业实现高效、可靠的数字化转型。
207 1
|
Java 测试技术 Spring
|
SQL 存储 关系型数据库
Hive 和 HDFS、MySQL 之间的关系
Hive是Hadoop上的数据仓库工具,用HiveQL进行大数据查询;HDFS是分布式文件系统,用于存储大规模数据,常与Hive结合,提供数据存储和高可靠性。MySQL是RDBMS,适用于结构化数据管理,在大数据环境里可存储Hive的元数据,提升查询效率和元数据管理。三者协同处理数据管理和分析任务。
627 0
|
达摩院 供应链 Cloud Native
低代码这么火,它的人才认证你考了吗?
2021年超级🔥 的证书!限时免费认证中……
8699 0
低代码这么火,它的人才认证你考了吗?
|
存储 Kubernetes Cloud Native
Vineyard | 开源分布式内存数据管理引擎
阿里巴巴技术专家迪杰&高级开发工程师临竹在阿里云开发者社区特别栏目《周二开源日》直播中,介绍了Vineyard的设计动因和整体架构,并通过示例展示如何使用Vineyard来共享数据,分享Vineyard结合云原生能力,赋能更大数据应用场景的尝试和愿景。本文为直播内容文字整理,看直播回放,请点击文首链接~
Vineyard | 开源分布式内存数据管理引擎