用SplFixedArray替代Array实现HashTable

• 2017-05-12
• 1901 View

php中，array数组本来就是一个key/value对应的hash结构类型，其中key可以是一个整数或者字符串。而在PHP3.0+版本中，内置的 PHP 标准函数库（SPL）中定义了几种 数据结构 类，比如SplStack、SplQueue等。其中有一个SplFixedArray类，定义了一个定长的数组结构，特性是比一般的array更快。

SplFixedArray和PHP常用的array数组之间最主要的区别就是：SplFixedArray的数组长度固定，而且只允许integer类型作为索引。foreach方法同样适用于SplFixedArray定义的数组，唯一不同的就是SplFixedArray是固定长度的，类似C，事先定义好数组的长度，比如：
$arr1 = new SplFixedArray('10');
$arr1['1'] = 'www';
$arr1['2'] = 'xxx';
foreach( $arr1 as $key=>$value ){
echo $arr1->current();//返回当前的数组值 $value
echo $arr1->key();//返回当前的数组$key，数组固定长度为10所以key是从 0 到 9
}

但是在开发中，能遇到固定长度数组的业务情况很少，一般都是if/else再foreach。下面用SplFixedArray实现一个HashTabel，因为hashtable起码会固定长度。
class HashTable{
private $size=10;
private $buckets;
function __construct(){
$this->buckets = new SplFixedArray($this->size);
}
//hash取模
function hashFunc($key){
$strlen = strlen($key);
$value = 0;
for($i=0;$i<$strlen;$i++){
$value +=ord($key[$i]); //计算 $key 的字符串和
}
return $value%$this->size;
}
function insert($key,$val){
$index = $this->hashFunc($key);
$this->buckets[$index] = $val;
}
function get($key){
$index = $this->hashFunc($key);
return $this->buckets[$index];
}
}
$ht = new HashTable();
$ht->insert('key1','value1');
echo $ht->get('key1');