散列函数的构造方法

数字分析法

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

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

/**
 数字分析法:以手机号码，身份证为例，取后四位*/
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));

测例2

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

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

折叠法

折叠法是将关键字从左到右按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);

测例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);

随机数法

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

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);
  }

除留余数法

此方法最为常用，其关键为寻找合适的除数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

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

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

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

全部代码

#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

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

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

尾言

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

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

散列函数的构造方法

数字分析法

平方取中法

平方取中法测试

测例1

测例2

折叠法

折叠法测试

测例1

测例2

随机数法

随机数法测试

测例1

除留余数法

解决散列冲突的方法

开放定址法

公共溢出区法

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

全部代码

测试效果

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

全部代码

测试效果

尾言

热门文章

最新文章

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

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

散列函数的构造方法

数字分析法

平方取中法

平方取中法测试

测例1

测例2

折叠法

折叠法测试

测例1

测例2

随机数法

随机数法测试

测例1

除留余数法

解决散列冲突的方法

开放定址法

公共溢出区法

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

全部代码

测试效果

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

全部代码

测试效果

尾言

热门文章

最新文章

相关电子书