散列-哈希查找 C语言实现.pdf

大愚若愚
wtfmonking的博客————IT非宅男
散列/哈希查找 C语言实现
分类: Data structure & Algorithm 2013-12-16 16:12 138人阅读评论(0) 收藏举报
散列查找哈希查找哈希表
 1、基本概念
散列(hash)同顺序、链接和索引一样,是存储数据的又一种方法。
散列存储的基本思想是:以数据(通常为集合)中的每个元素的关键字K为自变量,通过一种函数h(K)计算出函数
值,
把这个值解释为一块连续存储空间(即数组空间或文件空间)的单元地址(即下标),将该元素存储到这个单元中。
散列存储中使用的函数h(K),称为散列函数或哈希函数,它实现关键字到存储地址的映射(或称转换),h(K)的值称
为散列地址或哈希地址;
使用的数组空间是数据进行散列存储的地址空间,所以被称之为散列表或哈希表(hash list或hash table)。
在散列表上进行查找时,首先根据给定的关键字K,用与散列存储时使用的同一散列函数h(K)计算出散列地址,然后
按此地址从散列表中取出对应的元素。
      假定一个集合为
     S={18,75,60,43,54,90,46}
   其中每个整数可以是元素本身,也可以仅是元素的关键字,用以代表整个元素。为了散列存储该集合,假定
选取的散列函数为:
       h(K)=K % m
   即用元素的关键字K整除以散列表的长度m,取余数(即为0至m-1范围内的一个数)作为存储该元素的散列地
址,
这里假定K和m均为正整数,并且m要大于等于待散列存储的集合的长度n。在此例中,n=7,所以假定取m=13,则得到
的每个元素的散列地址为:
       h(18)=18 % 13=5        h(75)=75 %13=10
       h(60)=60 % 13=8        h(43)=43 %13=4
       h(54)=54 % 13=2        h(90)=90 %13=12
       h(46)=46 % 13=7
若根据散列地址把元素存储到散列表H[m]中,则存储映象为:
 
2、  散列函数
    1. 直接定址法
1
h(K) = K + C
    这种方法关键字分配不连续,存储空间严重浪费
    2. 除留余数法
   除留余数法是用关键字K除以散列表长度m所得余数作为散列地址的方法。对应的散列函数h(K)为:
    h(K) = K % m
   这种方法计算简单,适用范围广
    3. 数字分析法
    数字分析法是取关键字中某些取值较分散的数字位做为散列地址的方法。
    4. 平方取中法
    平方取中法是取关键字平方的中间几位作为散列地址的方法,具体取多少位视实际要求而定。
    5. 折叠法
    折叠法是首先将关键字部分分割成位数相同的几段(最后一段的位数若不足应补0),段的位数取决于散列
地址的位数,由实际需要而定,然后将他们的叠加和
  (舍去最高位进位)作为散列地址的方法。
3、处理冲突的方法
1、开放定址法 
 (1) 线性探查法
         d=h(K)