有趣的算法（三）——Hash算法
有趣的算法（三）——Hash算法
（原创内容，转载请注明来源，谢谢）
一、Hash算法
近期看到用hash实现基于hash的简单的小型数据库（传统大型数据库用的都是B+tree），感觉挺感兴趣，故先研究hash算法，近期会用hash实现一个小的数据库。
Hash表（Hash Table）又称为散列表，通过把关键字key映射到数组的一个位置，来访问记录。这个映射函数称为hash函数，存放记录的数组称为hash表。
1、hash函数
作用是把任意长度的输入，通过hash算法得到固定函数的输出，输出的内容就是hash值。这种映射是一种压缩映射，即输出的内容占用的存储空间可能会小于输入的内容。因此不同的key经过hash可能会得到同一个结果。
好的hash使每个关键字均匀分布到hash表的任一个位置，并于其他已被散列到hash表中的关键字不冲突。
根据关键字的不同，可能设计不同的hash算法。
2、直接取余法——适用整数
用关键字k除以hash表的大小m取余，得到的结果即为结果。
h(k) = k mod m。例如哈希表大小20，关键字是30，则h(20) = 10。
3、乘积取整法——适用小数
使用关键字k乘以一个常数A(0<A<1)，取出kA的小数部分，乘以hash表的大小，向下取整即可。
hash(k)= floor(m*(kA mod 1))，kA mod 1表示kA的小数部分，floor是取整操作。
4、ASCII码处理法——适用字符串
字符串无法进行取余或者取整，则可以使用把每个字符取整求和，再按照上面的方法对结果进行处理。
5、经典hash算法：DJB hashfunction（俗称Times33）
该算法效率和随机性很高，运用广泛，包括Perl、Berkeley DB、Apache、MFC、STL、PHP等的Hash，都用的此算法。
该算法的核心是将每一位都乘以33，再加上原来的值。
代码实现方法（C语言）如下：
unsignedlong time33(char const *str, int len)
{
unsigned long hash = 0;
for (int i = 0; i < len; i++) {
hash = ((hash <<5) + hash) + (unsigned long) str[i];
}
return hash;
}其中，采用<<方式，即将值乘以2的5次方（32）。
二、Hash表
1、算法
hash表的时间复杂的O(1)，即key通过hash函数，找到值所在的地方。要构建hash表必须创建一个足够大的数组用于存放数据，另外还需要一个hash函数把关键字key映射到数组的某个位置。具体实现步骤如下：
1）创建一个固定大小的数组用于存放数据。
2）设计hash函数。
3）通过hash函数把关键字映射到数组的某个位置，并在此位置上进行数据存取。
2、用PHP实现hash表
1）定义hashtable类
<?php
classHashTable{
private $buckets;
private $size = 10;
public function __construct($size = 0){
if($size > 0){
$this->size =$size;
}
$this->buckets = new SplFixedArray($this->size);
}
}hash表采用定长来保存数据，其中buckets是一个数组，其key是hash函数的结果，值用于存放原值。buckets的数组不采用array，而采用php的SPL中的SplFixedArray，该类要求初始化的时候需要一个定长，并且数组的key只能是整数。这个数组更接近原生的c语言，效率更高。
2）定义hash函数（Times33，字符串取ascii，结果和10）
private functionhashFunction($string){
$len = strlen($string);
$hash = 0;
for($i=0;$i<$len;$i++){
$hash += $hash<<5+ ord($key[$i]);
$hash %=$this->size;
}
return $hash;
}3）增删改查
//新增，相同则覆盖
publicfunction insert($key, $val){
$key= $this->hashFunction($key);
$this->buckets[$key]= $val;
return$this->buckets;
}
//查找
publicfunction search($key){
$key= $this->hashFunction($key);
return$this->buckets[$key];
}
//删除
publicfunction delete($key){
$key= $this->hashFunction($key);
if(isset($this->buckets[$key])){
unset($this->buckets[$key]);
}
}
//修改，不存在则新增
publicfunction update($key, $val){
$key= $this->hashFunction($key);
$this->buckets[$key]= $val;
return$this->buckets;
}3、Hash表冲突问题
因为key是通过一定的计算得到的结果，且通常传入的key和计算的key不是一一对应的，因此可能会存在冲突。要解决冲突，可以使用拉链法，即将所有相同的值放在一个链表中。此时，除了需存储value，还要存储key和下一个value的位置。
因此，需要引入一个新的类：
classHashNode{
public $key;
public $value;
public $next;
public function __construct($key,$value, HashNode $next = null){
$this->key = $key;
$this->value=$value;
$this->next =$next;
}
}此时，相应的操作变化如下：
//新增，链表方式，重复则添加到相应的链表
publicfunction insert($key, $val){
$key= $this->hashFunction($key);
if(isset($this->buckets[$key])){
$node= new HashNode($key, $val, $this->buckets[$key]);
}else{
$node = new HashNode($key, $val);
}
unset($this->buckets[$key);
$this->buckets[$key]= $node;
return$this->buckets;
}
//查找
publicfunction search($key){
$key= $this->hashFunction($key);
if(!isset($this->buckets[$key])){
returnnull;
}
$current= $this->buckets[$key];
while(isset($current)){
if($current->key== $key){
return$current->value;
}
$current= $current->next;
}
returnnull;
}
//修改，不存在则返回false
publicfunction update($key, $val){
$key= $this->hashFunction($key);
if(!isset($this->buckets[$key])){
returnfalse;
}
$current= $this->buckets[$key];
$isSuccess= false;
while(isset($current)){
if($current->key== $key){
$current->value= $val;
$isSuccess= true;
break;
}
$current= $current->next;
}
return$isSuccess;
}——written by linhxx 2017.08.18