php核心技术与最佳实践之hash算法 php核心技术与最佳实践之hash算法
hash表又称散列表，通过把关键字key映射到数组中的一个位置来访问记录，以加快查找速度。这个映射函数称为hash函数，存放记录的数组称为hash表。
1. hash函数
作用是把任意长度的输入，通过hash算法变换成固定长度的输出，该输出就是hash值。这种转换是一种压缩映射，也就是hash值得空间通常远小于输入的空间，不输入可能会散列成相同的输出，而不可能从hash值来唯一的确定输入值。
一个好的hash函数应该满足以下条件：每个关键字都可以均匀的分布到hash表任意一个位置，并与其他已被散列到hash表中的关键字不发生冲突。这是hash函数最难实现的。
2. hash算法
1) 直接取余法
直接取余法比较简单，直接用关键字k除以hash表的大小m取余数，算法如下：
h(k) = k mod m
例如：hash表的大小为m=12，所给关键字为k=100，则h(k) = 4.这种算法是一个求余操作，速度比较快。
2) 乘积取整法
乘积取整法首先使用关键字k乘以一个常数a(0
h(k) = floor (m*(ka mod 1))
其中，ka mod1表示ka的小数部分，floor是取整操作。
当关键字是字符串的时候，就不能用上面的hash算法。因为字符串是由字符组成，所以可以把字符串所有的字符的ascii码加起来得到一个整数，然后再按照上面的hash算法去计算即可。
算法如下：
function hash($key,$m){
$strlen= strlen($key);
$hashval= 0;
for($i=0;$i
$hashval+=ord($key{$i});
}
return $hashval % $m;
}
3) 经典hash算法times33
unsigned int djbhash(char *str){
unsignedint hash = 5381;
while(*str){
hash+=(hash
}
return (hash &0x7fffffff)
}
算法思路就是不断乘以33，其效率和随机性都非常好，广泛运用于多个开源项目中，如apache、perl和php等。
3. hash表
hash表的时间复杂度为o(1)，hash表结构可用图表示：
要构造一个hash表必须创建一个足够大的数组用于存放数据，另外还需要一个hash函数把关键字key映射到数组的某个位置。
hash表的实现步骤：
1) 创建一个固定大小的数组用于存放数据。
2) 设计hash函数。
3) 通过hash函数把关键字映射到数组的某个位置，并在此位置上进行数据存取。
4. 使用php实现hash表
首先创建一个hashtable类，有两个属性$buckets和$size。$buckets用于存储数据的数组，$size用于记录$buckets数组大小。然后在构造函数中为$buckets数组分配内存。代码如下：
classhashtable{
private$buckets;
private$size =10;
publicfunction __construct(){
$this-> buckets =new splfixedarray($this->size);
}
}
?>
在构造函数中，为$buckets数组分配了一个大小为10的数组。在这里使用了spl扩展的splfixedarray数组，不是一般的数组(array)
这是因为splfixedarray数组更接近于c语言的数组，而且效率更高。在创建其数组时需要为其提供一个初始化的大小。
注意：要使用splfixedarray数组必须开启spl扩展。如果没有开启，可以使用一般的数组代替。
接着为hash表指定一个hash函数，为了简单起见，这里使用最简单的hash算法。也就是上面提到了把字符串的所有字符加起来再取余。代码如下：
public function hashfunc($key){
$strlen= strlen($key);
$hashval= 0;
for($i=0;$i
$hashval+=ord($key{$i});
}
return $hashval % $this->size;
}
有了hash函数，就可以实现插入和查找方法。插入数据时，先通过hash函数计算关键字所在hash表的位置，然后把数据保存到此位置即可。代码如下：
public function insert($key,$val){
$index= $this -> hashfunc($key);
$this-> buckets[$index] = $val;
}
查找数据方法与插入数据方法相似，先通过hash函数计算关键字所在hash表的位置，然后返回此位置的数据即可。代码如下：
public function find($key){
$index= $this -> hashfunc($key);
return$this ->buckets[$index];
}
至此，一个简单的hash表编写完成，下面测试这个hash表。代码清单如下：
$ht= new hashtable();
$ht->insert(‘key1’,’value1’);
$ht->insert(‘key2’,’value2’);
echo$ht ->find(‘key1’);
echo$ht ->find(‘key2’);
?>
完整代码：#hash.php
buckets =new splfixedarray($this->size); } publicfunction hashfunc($key){ $strlen= strlen($key); $hashval= 0; for($i=0;$isize; } publicfunction insert($key,$val){ $index= $this -> hashfunc($key); $this-> buckets[$index] = $val; } publicfunction find($key){ $index= $this -> hashfunc($key); return$this ->buckets[$index]; } } $ht = newhashtable(); $ht->insert('key1','value1'); $ht->insert('key2','value2'); echo $ht->find('key1'); echo $ht->find('key2'); ?>
http://www.bkjia.com/phpjc/984757.htmlwww.bkjia.comtruehttp://www.bkjia.com/phpjc/984757.htmltecharticlephp核心技术与最佳实践之hash算法 php核心技术与最佳实践之hash算法 hash表又称散列表，通过把关键字key映射到数组中的一个位置来访问记录...