好好学 Hash

目录
[隐藏]

Hash 的应用是十分广泛的,比较基础的用来做 散列检索,然后可以 实现分布式,再到现在大数据哈希学习 等等。一直处在一个一知半解的程度,吃过亏,就知道该好好学一下啦。

1、Hash 基础

虽然 Hash 应用广泛,但万变不离其宗,其核心的东西是相似的。

Hash 表HashTable)又称散列表,是根据关键字(Key)而直接进行访问的一种数据结构,简单说来是数组。通过把关键字 Key 映射到数组中的一个位置,然后在这个位置存储 Value,就能加快查找的速度。所用到的映射函数称为 Hash 函数,存放记录的数组就被称为 Hash 表

对比理解是最形象的:

无论是线性表的顺序检索、二分检索,还是树的二叉排序树、平衡树、B树检索等。这些数据结构中的检索都有一个共同点:即都是通过若干次 比较 来寻找指定的记录,比较次数与数据规模是直接相关的,这就形成了一个难以绕过去的坎。

人的欲望是无限的,有了快还要更快。既然从 比较 这个思路出发已经遇到了瓶颈,那就换个想法。于是,Hash 表就出现了,从上面对 Hash 表的描述可以看到,通常情况下,在 Hash 表中检索数据是不用进行 比较 的,只需通过映射函数处理就可以进行访问了,时间复杂度O(1)。

给一个最简单的 HasbTable 示意图:

对于Hash 表来说,核心考虑两个方面的内容:

  1. Hash 函数怎么构造?
  2. 冲突如何解决?

第一点 Hash 函数很容易理解,就是前面提到的映射函数。Hash 函数的作用是把任意长度输入,通过 Hash 算法变换成固定长度的输出,该输出就是 Hash 值。可以看出这种转换是一种压缩映射,也就是 Hash 值的空间通常会远小于输入的空间。

第二点 冲突?这个 冲突 也是很容易理解的。看个例子:假设 Hash 表大小只有10,但现在有 11 条记录,那通过 Hash 函数进行映射后,至少会有两条记录被映射到一个位置,这种情况就称为发生“冲突”了。

下面是一个冲突示意图:

从上述可以看出“不同的输入可能会散列成相同的输出,而不可能从 Hash 值来唯一地确定输入值”,在一般情况,对于冲突是很难完全解决,只能缓解,毕竟关键字集合通常远大于 Hash 表容量。

2、Hash 函数

一个好的 Hash 函数应该满足一些条件:每个关键字都可以均匀地分布到 Hash 表任意一个位置,并且与其他已被散列到 Hash 表中的关键字不发生冲突。当然完全做到是很难的,通常是尽可能去达到这两个条件。

因为 关键字k 可能是整数或者字符串,所以通常会按照关键字的类型设计不同的 Hash 算法。
对于 整数 关键字的 Hash 有以下几种(简单描述):

2.1 直接取余

直接取余原理很简单,直接用关键字 k 除以 Hash 表的大小 m 取余数。

hash(k) = k mod m;

2.2 乘积取整

该方法首先用关键字 k 乘以一个常数 A (0<A<1),并抽取去 kA 的小数部分。然后用 Hash 表的大小 m 乘以这个值,再取整数部分即可。

hash(k) = floor(m*(kA mod 1));

而当关键字是字符串时,上面的Hash 算法就行不通了,不过可以一种想法是把所有字符的 ASCII 码加起来,然后作为一个整数去处理。

在这里仅仅是稍微描述下 Hash 算法的基本原理,数据结构 书籍上通常会介绍五种:取余法、平方取中法、折叠法、数字分析法、直接地址法。主要学习原理

2.3 经典 Hash 算法Times33

在实际应用中,Hash 函数得考虑那两个条件,所以一般不会自己去设计 Hash 函数。有一些经过多年研究创造的非常有效的 Hash 算法可以让我们使用,这里以 Times33(DJB hash function) 为例:

unsigned int DJBHash(char *str){

  unsigned int hash = 5381;

  while(*str){

    hash += (hash << 5) + (*str++);

  }

  return (hash & 0x7FFFFFFF);  //保证返回32位

}

Times33 算法思路很简单,就是不断乘以 33,经过各种测试发现它的效率和随机性都非常好(肯定比我们自己编写的好很多,,)。在很多开源项目中也有运用如:Apache、Perl 和 PHP 中。所以放心大胆的用

到这里,Hash 函数的基本原理应该是理解了,要更详细的了解,可以参考:

http://www.nowamagic.net/academy/detail/3008097

3、冲突解决

数据结构书上,通常会讲:开放地址法、再哈希法、链地址法(拉链法)

3.1 拉链法

拉链法 相比较起来更容易理解,也更容易实现,所以详细讲解下这个。

拉链法 解决冲突的做法是:将所有相同 Hash 值得关键字节点链接在同一个链表中。看下图

可以看出,拉链法把相同 Hash 值的关键字节点以一个链表连接起来,那么在查找元素时就必须遍历这条链表,比较链表中每个元素的关键字与查找的关键字是否相等,如果相等就是需要查找的元素。

对于链表中的节点,通常需要保存关键字key、数据value 和 具有相同 Hash 值的下一个节点。

在拉链法下的 HashTable 就可以看作是头指针的指针数组了。

拉链法的优点是:处理冲突简单、无聚集现象(后面讲)、平均查找长度短、删除结点方便

拉链法的缺点很明显是:需要开辟额外空间。

3.2 开放地址法

开放地址法的基本做法是在发生冲突时,按照某种方法继续 探测 Hash 表中其它存储单元,直到找到一个开发的地址(即空位置)为止。显然,这种方法的话需要标记空单元和非空单元。

探测方法通常有:线性探测、二次探测、随机探测

线性探测基本原理就是:在 Hash(key) = i 时,如果在 i 地址发生冲突就继续往后找,这就容易产生"聚集"

"聚集":就是说本应该在 i 地址的,占用了 i+1 地址,导致原本使用 i 地址的 只能使用 i+2 或更后面的地址。这就可能导致很多元素在 哈希地址上 "聚集" 起来。

二次探测、随机探测能很好解决 "聚集" 问题,需要了解可以参考:

http://www.jianshu.com/p/dbe7a1ea5928

4、简单实现 HashTable

为了应用 拉链法 解决冲突,定义节点类:

class HashNode{
   public $key;
   public $value;
   public $nextNode;

   public function __construct($key,$value
       ,$nextNode = NULL){
       $this->key = $key;
       $this->value = $value;
       $this->nextNode = $nextNode;
   }
}

HashTable 类仅实现了简单 Hash 函数、插入 和 查找。

class HashTable{
   private $buckets;  // HashTable
   private $size=10;  // HashTable 长度

   public function __construct(){
       $this->buckets = new SplFixedArray($this->size);
   }
   public function hashfunc($key){
       $strlen = strlen($key);
       $hashval = 0;
       for($i = 0; $i < $strlen; $i++){
           $hashval += ord($key{$i});
       }
       return $hashval % $this->size;
   }
   public function insert($key,$value){
       $index = $this->hashfunc($key);
       //根据 $index 判断是否已有节点,来创建新节点
       if(isset($this->buckets[$index])){
           $newNode = new HashNode($key,$value,
               $this->buckets[$index]);
       }else{
           $newNode = new HashNode($key,$value,
               NULL);
       }
       //HashTable 中记录新节点
       $this->buckets[$index] = $newNode;
   }
   public function find($key){
       $index = $this->hashfunc($key);
       //获取具有相同 hash 值得节点链表头节点
       $current = $this->buckets[$index];
       //遍历链表
       while(isset($current)){
           if($current->key == $key){
               return $current->value;
           }
           $current = $current->nextNode;
       }
       return NULL;
   }
}

5、总结

虽然经过一系列学习,感觉对 Hash 的认识比之前好了很多。但最关键的还是要学会运用,在遇到某些问题时能够去想到用 HashTable 这种数据结构来解决。

一致性Hash 实现分布:Memcached 分布式布置方案

更多参考:

http://blog.csdn.net/sangyongjia/article/details/37312851

http://blog.csdn.net/sangyongjia/article/details/33397109

http://www.jianshu.com/p/dbe7a1ea5928

http://www.nowamagic.net/academy/detail/3008097

发表评论

电子邮件地址不会被公开。 必填项已用*标注

To