有趣的算法(三)——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

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-08-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Vamei实验室

纸上谈兵: 哈希表 (hash table)

HASH 哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系,而且集合A的某个元素只能对应集合B中的一个元素...

229100
来自专栏生信宝典

Python学习教程(二)

输入输出 交互式输入输出 在很多时候,你会想要让你的程序与用户(可能是你自己)交互。你会从用户那里得到输入,然后打印一些结果。我们可以分别使用raw_input...

29080
来自专栏Laoqi's Linux运维专列

正则三剑客-awk

awk与前两个不同之处是支持分段处理; #mkdir awk; cp /etc/passwd awk/passwd         //前期准备,创建一个awk...

29250
来自专栏微服务生态

由学习《软件设计重构》所想到的代码review(二)

我们接第一篇来继续说明在代码review中,有哪些属于“层次结构”中的坏味道。 第一篇链接如下:http://www.jianshu.com/p/07dbf6...

9620
来自专栏Star先生的专栏

Tensorflow 术语表

本文主要简要介绍了广播操作、Graph(图)、Session(会话)、Tensor 等13个 Tensorflow 术语表。希望对大家了解学习 Tensorfl...

1.1K10
来自专栏ATYUN订阅号

使用Python建立你数据科学的“肌肉记忆”

你是否曾在在搜索语法时,因为打断了数据分析流而感到沮丧?为什么你在屡次查找后仍然不记得它?这是因为你还没有足够的练习来为它建立“肌肉记忆”。

9520
来自专栏用户2442861的专栏

数据库系统——B+树索引

http://blog.csdn.net/cjfeii/article/details/10858721

52210
来自专栏程序员的酒和故事

跟Google学写代码--Chromium工程中用到的C++11特性

Ttile 跟Google学写代码--Chromium工程中用到的C++11特性 Chromium是一个伟大的、庞大的开源工程,很多值得我们学习的地方。 《跟...

46640
来自专栏李海辰的专栏

Unity引擎资源管理代码分析 ( 2 )

上一篇《Unity 引擎资源管理代码分析 ( 1 ) 》讲解了 Unity 引擎资源管理代码的类型设计架构和 Resources.Load 接口的实现,本文将...

1K40
来自专栏PingCAP的专栏

SuRF: 一个优化的 Fast Succinct Tries

在前一篇文章中,我简单介绍了 Succinct Data Structure,这里我们继续介绍 SuRF。

36150

扫码关注云+社区

领取腾讯云代金券