搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > Coder的自我修养 > 【数据结构与算法】散列介绍与几个散列函数

【数据结构与算法】散列介绍与几个散列函数

Coder的自我修养 2018-07-01

第五章:散列

  • 散列表(hash table):只支持二叉查找树所允许的一部分操作.

  • 散列(hashing):一种用于以常数平均时间执行插入,删除和查找的级数.

5.1 一般想法

  • 理想的散列表数据结构只不过是一个包含有关键字的具体固定大小的数组.一般而言,这个关键字就是带有一个相关之的字符串.

  • 我们把表的大小记作 $ TableSize $,并将其理解为散列数据结构的一部分而不仅仅是浮动于全局的某个变量.通常的习惯是让表从 $ 0 $ 到 $ TableSize - 1 $ 变化.

  • 散列函数(hash function):每个关键字映射到从 $ 0 $ 到 $ TableSize - 1 $ 这个范围中的某个数,并且被放到适当额单元中.最理想的情况是,运算简单并且任何两个不同的关键字映射到不同的单元.但是这是不可能的,因为单元的数目是有限的,而关键字是用不完的.

  • 冲突(collision):当两个关键字散列到同一个值的时候.

5.2 散列函数

  • 当关键字是整数时,我们保证表的大小是一个素数,可以直接返回 $ Key mod TableSize $

  • 当关键字是字符串时,散列函数需要仔细选择.

  1. 一种选择方法是可以将字符串中的字符的 ASCII 码值相加起来.如下

 
   
   
 
  1. //将字符逐个相加来处理整个字符串

  2. typedef unsigned int Index;

  3. Index Hash( const char *Key, int TableSize){

  4.    unsigned int HashVal = 0;

  5.    while( *Key != '\0')

  6.        HashVal += *Key++;

  7.    return HashVal % TableSize;

  8. }

上述散列函数描述起来简单并且能够很快的算出答案.但是,如果表很大,那么函数并不能很好的分配关键字. $ e.g. $ 当 $ TableSize = 10007 ( 一个素数 ) $ 并假设所有的关键字之多 8 个字符长,那么由于 $ char $ 类型的变量值最多为127,因此散列函数的取值处于 0 到 1016 之间.这显然是一种不均匀的分配.

2.另一种散列函数如下

 
   
   
 
  1. Index Hash2( const char *Key, int TableSize){

  2.    return( Key[0] + 27 * Key[1] + 729 * Key[2]) % TableSize;

  3. }

这个散列函数假设 $ Key $ 至少有两个字符外加 NULL结束符,值 27 表示英文字母的个数外加一个空格. 假设我们的表的大小依旧是 10007 并且如果字符串具有随机性,由于 $ 27^2 =729 $ $ 729 * 27 = 93312 $ 因此我们可以得到一个合理的均匀分配. 但是,考虑到英文不是随机的,具有三个字母的单词数目只有2851个,远小于三个英文字母的排列数.因此当散列表足够大的时候这个函数还是不合适的.

3.第三种散列函数

 
   
   
 
  1. Index Hash3( const char *Key, int TableSize){

  2.    unsigned int HashVal = 0;

  3.    while( *Key != '\0')

  4.        HashVal = ( HashVal<<5) + *Key++;

  5.    return HashVal % TableSize;

  6. }


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《【数据结构与算法】散列介绍与几个散列函数》的版权归原作者「一个理科生的自我修养」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注一个理科生的自我修养微信公众号

一个理科生的自我修养微信公众号:A_self_cultivation

一个理科生的自我修养

手机扫描上方二维码即可关注一个理科生的自我修养微信公众号

一个理科生的自我修养最新文章

精品公众号随机推荐

上一篇 >>

Netty笔记(一)