最近在看凹凸曼和白菜写的书,500多页,其实我真正想看的是PHP扩展部分以及缓存部分。下面是凹凸曼用PHP实现的HashTable代码,其中需要说明的有两点:
1)代码中使用了SplFixedArray,这是一个更接近C语言的数组[Array],而且效率更高。使用之前需要开启SPL扩展,PHP5.3+默认开启。
2)代码中使用拉链法解决冲突,即将所有相同的Hash值的关键字节点链接在同一个链表中。
key=$key; $this->value=$value; $this->nextNode=$nextNode; } } //天涯PHP博客http://blog.phpha.com classHashTable{ private$buckets; private$size=10; publicfunction__construct(){ $this->buckets=newSplFixedArray($this->size); } privatefunctionhashfunc($key){ $strlen=strlen($key); $hashval=0; for($i=0;$i<$strlen;$i++){ $hashval+=ord($key{$i}); } return$hashval%$this->size; } publicfunctioninsert($key,$value){ $index=$this->hashfunc($key); /*新创建一个节点*/ if(isset($this->buckets[$index])){ $newNode=newHashNode($key,$value,$this->buckets[$index]); }else{ $newNode=newHashNode($key,$value,NULL); } $this->buckets[$index]=$newNode;/*保存新节点*/ } publicfunctionfind($key){ $index=$this->hashfunc($key); $current=$this->buckets[$index]; while(isset($current)){/*遍历当前链表*/ if($current->key==$key){/*比较当前节点的关键字*/ return$current->value;/*查找成功*/ } $current=$current->nextNode;/*比较下一个节点*/ } returnNULL;/*查找失败*/ } } //天涯PHP博客http://blog.phpha.com //*******下面是测试代码******* $ht=newHashTable(); $ht->insert('key1','value1'); $ht->insert('key12','value12'); echo$ht->find('key1'); echo$ht->find('key12'); ?>