Hash表：使用PHP实现Hash表功能
Hash表作为最重要的数据结构之一，也叫做散列表。使用PHP实现Hash表的功能。PHP可以模拟实现Hash表的增删改查。通过对key的映射到数组中的一个位置来访问。映射函数叫做Hash函数，存放记录的数组称为Hash表。
Hash函数把任意长度的和类型的key转换成固定长度输出。不同的key可能拥有相同的hash。
Hash表的时间复杂度为O(1)
/
hash表类
ClassHashTable
AuthLane
Maillixuan868686@163.com
Bloghttp://www.lanecn.com
/
classHashTable{
private$arr=array();
private$size=10;
publicfunction__construct(){
//SplFixedArray创建的数组比一般的Array()效率更高，因为更接近C的数组。创建时需要指定尺寸
$this->arr=newSplFixedArray($this->size);
}
/
Description:简单hash算法。输入key，输出hash后的整数
@param$key
@returnint
/
privatefunctionsimpleHash($key){
$len=strlen($key);
//key中每个字符所对应的ASCII的值
$asciiTotal=0;
for($i=0;$i<$len;$i++){
$asciiTotal+=ord($key[$i]);
}
return$asciiTotal%$this->size;
}
/
Description:赋值
@param$key
@param$value
@returnbool
/
publicfunctionset($key,$value){
$hash=$this->simpleHash($key);
$this->arr[$hash]=$value;
returntrue;
}
/
Description:取值
@param$key
@returnmixed
/
publicfunctionget($key){
$hash=$this->simpleHash($key);
return$this->arr[$hash];
}
publicfunctiongetList(){
return$this->arr;
}
publicfunctioneditSize($size){
$this->size=$size;
$this->arr->setSize($size);
}
}
?>
下面对我们的HashTable进行测试。
//测试1
$arr=newHashTable();
for($i=0;$i<15;$i++){
$arr->set(''key''.$i,''value''.$i);
}
print_r($arr->getList());
//SplFixedArrayObject
//(
//[0]=>value14
//[1]=>value4
//[2]=>value5
//[3]=>value6
//[4]=>value7
//[5]=>value8
//[6]=>value10
//[7]=>value11
//[8]=>value12
//[9]=>value13
//)
//不同的key可能产生相同的hash值，那么赋值的时候后操作会覆盖前操作。
//测试2
$arr->editSize(15);
for($i=0;$i<15;$i++){
$arr->set(''key''.$i,''value''.$i);
}
print_r($arr->getList());
//SplFixedArrayObject
//(
//[0]=>value14
//[1]=>value4
//[2]=>value0
//[3]=>value1
//[4]=>value2
//[5]=>value3
//[6]=>value10
//[7]=>value11
//[8]=>value12
//[9]=>value13
//[10]=>value14
//[11]=>value9
//[12]=>
//[13]=>
//[14]=>
//)
?>
改变了值之后可以存放更多的元素。但是仍然存在不同的key可能产生相同的hash值，那么赋值的时候后操作会覆盖前操作的问题。这种冲突的问题我们来用拉链法解决。
拉链法解决冲突。拉链法解决冲突的做法是将所有的相同Hash值的key放在一个链表中，比如key3和key14在hash之后都是0，那么在数组的键为0的地方存储这两个值，形式是链表。如果不能理解我的文字，请看下面的示例，看一下打印信息就明白了。拉链法是什么，就是链表。
创建一个HashNode类，用来存储key和value的值，并且存储相同hash的另一个元素。在同一条链上，查找越后的元素越费时。时间复杂度为O(n).
classHashNode{
public$key;
public$value;
public$nextNode;
publicfunction__construct($key,$value,$nextNode=Null){
$this->key=$key;
$this->value=$value;
$this->nextNode=$nextNode;
}
}
classNewHashTable{
private$arr;
private$size=10;
publicfunction__construct(){
$this->arr=newSplFixedArray($this->size);
}
privatefunctionsimpleHash($key){
$asciiTotal=0;
$len=strlen($key);
for($i=0;$i<$len;$i++){
$asciiTotal+=ord($key[$i]);
}
return$asciiTotal%$this->size;
}
publicfunctionset($key,$value){
$hash=$this->simpleHash($key);
if(isset($this->arr[$hash])){
$newNode=newHashNode($key,$value,$this->arr[$hash]);
}else{
$newNode=newHashNode($key,$value,null);
}
$this->arr[$hash]=$newNode;
returntrue;
}
publicfunctionget($key){
$hash=$this->simpleHash($key);
$current=$this->arr[$hash];
while(!empty($current)){
if($current->key==$key){
return$current->value;
}
$current=$current->nextNode;
}
returnNULL;
}
publicfunctiongetList(){
return$this->arr;
}
}
?>
对我们新的HashTable进行测试
//测试1
$newArr=newNewHashTable();
for($i=0;$i<30;$i++){
$newArr->set(''key''.$i,''value''.$i);
}
print_r($newArr->getList());
var_dump($newArr->get(''key3''));
//SplFixedArwww.shanxiwang.netrayObject
//(
//[0]=>HashNodeObject
//(
//[key]=>key23
//[value]=>value23
//[nextNode]=>HashNodeObject
//(
//[key]=>key14
//[value]=>value14
//[nextNode]=>HashNodeObject
//(
//[key]=>key3
//[value]=>value3
//[nextNode]=>
//)
//
//)
//
//)
//
//[1]=>HashNodeObject
//(
//[key]=>key24
//[value]=>value24
//[nextNode]=>HashNodeObject
//(
//[key]=>key15
//[value]=>value15
//[nextNode]=>HashNodeObject
//(
//[key]=>key4
//[value]=>value4
//[nextNode]=>
//)
//
//)
//
//)
//
//[2]=>HashNodeObject
//(
//[key]=>key25
//[value]=>value25
//[nextNode]=>HashNodeObject
//(
//[key]=>key16
//[value]=>value16
//[nextNode]=>HashNodeObject
//(
//[key]=>key5
//[value]=>value5
//[nextNode]=>
//)
//
//)
//
//)
//
//[3]=>HashNodeObject
//(
//[key]=>key26
//[value]=>value26
//[nextNode]=>HashNodeObject
//(
//[key]=>key17
//[value]=>value17
//[nextNode]=>HashNodeObject
//(
//[key]=>key6
//[value]=>value6
//[nextNode]=>
//)
//
//)
//
//)
//
//[4]=>HashNodeObject
//(
//[key]=>key27
//[value]=>value27
//[nextNode]=>HashNodeObject
//(
//[key]=>key18
//[value]=>value18
//[nextNode]=>HashNodeObject
//(
//[key]=>key7
//[value]=>value7
//[nextNode]=>
//)
//
//)
//
//)
//
//[5]=>HashNodeObject
//(
//[key]=>key28
//[value]=>value28
//[nextNode]=>HashNodeObject
//(
//[key]=>key19
//[value]=>value19
//[nextNode]=>HashNodeObject
//(
//[key]=>key8
//[value]=>value8
//[nextNode]=>
//)
//
//)
//
//)
//
//[6]=>HashNodeObject
//(
//[key]=>key29
//[value]=>value29
//[nextNode]=>HashNodeObject
//(
//[key]=>key10
//[value]=>value10
//[nextNode]=>HashNodeObject
//(
//[key]=>key9
//[value]=>value9
//[nextNode]=>
//)
//
//)
//
//)
//
//[7]=>HashNodeObject
//(
//[key]=>key20
//[value]=>value20
//[nextNode]=>HashNodeObject
//(
//[key]=>key11
//[value]=>value11
//[nextNode]=>HashNodeObject
//(
//[key]=>key0
//[value]=>value0
//[nextNode]=>
//)
//
//)
//
//)
//
//[8]=>HashNodeObject
//(
//[key]=>key21
//[value]=>value21
//[nextNode]=>HashNodeObject
//(
//[key]=>key12
//[value]=>value12
//[nextNode]=>HashNodeObject
//(
//[key]=>key1
//[value]=>value1
//[nextNode]=>
//)
//
//)
//
//)
//
//[9]=>HashNodeObject
//(
//[key]=>key22
//[value]=>value22
//[nextNode]=>HashNodeObject
//(
//[key]=>key13
//[value]=>value13
//[nextNode]=>HashNodeObject
//(
//[key]=>key2
//[value]=>value2
//[nextNode]=>
//)
//
//)
//
//)
//
//)
//string(6)"value3"
?>
|
|
