《利用PHP实现Hash表功能_.docx》由会员分享，可在线阅读，更多相关《利用PHP实现Hash表功能_.docx（18页珍藏版）》请在三一文库上搜索。
1、利用PHP实现Hash表功能_ Hash表作为最重要的数据结构之一，也叫做散列表。用法PHP实现Hash表的功能。PHP可以模拟实现Hash表的增删改查。通过对key的映射到数组中的一个位置来访问。映射函数叫做Hash函数，存放记录的数组称为Hash表。 Hash函数把任意长度的和类型的key转换成固定长度输出。不同的key可能拥有相同的hash。 Hash表的时间简单度为O(1) 代码如下: ?php class HashTable private $arr = array(); private $size = 10; public function _construct() /SplFix
2、edArray创建的数组比一般的Array()效率更高，由于更接近C的数组。创建时需要指定尺寸 $this-arr = new SplFixedArray($this-size); /* * Description: 简洁hash算法。输入key，输出hash后的整数 * param $key * return int */ private function simpleHash($key) $len = strlen($key); /key中每个字符所对应的ASCII的值 $asciiTotal = 0; for($i=0; $i$len; $i+) $asciiTotal += ord($
3、key$i); return $asciiTotal % $this-size; /* * Description: 赋值 * param $key * param $value * return bool */ public function set($key, $value) $hash = $this-simpleHash($key); $this-arr$hash = $value; return true; /* * Description: 取值 * param $key * return mixed */ public function get($key) $hash = $th
4、is-simpleHash($key); return $this-arr$hash; public function getList() return $this-arr; public function editSize($size) $this-size = $size; $this-arr-setSize($size); ? 下面对我们的HashTable进行测试。 代码如下: ?php /测试1 $arr = new HashTable(); for($i=0; $i15; $i+) $arr-set(key.$i, value.$i); print_r($arr-getList()
5、; /SplFixedArray Object /( / 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; $i15; $i+) $arr-set(key.$i, value.$i); print_r($arr-getList();
6、/SplFixedArray Object /( / 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值，那么赋值的时候后操作会掩盖前操作的问题。这种冲突的问题我们来用拉链法解决。 拉链法解决冲
7、突。拉链法解决冲突的做法是将全部的相同Hash值的key放在一个链表中，比如key3和key14在hash之后都是0，那么在数组的键为0的地方存储这两个值，形式是链表。假如不能理解我的文字，请看下面的示例，看一下打印信息就明白了。拉链法是什么，就是链表。 创建一个HashNode类，用来存储key和value的值，并且存储相同hash的另一个元素。在同一条链上，查找越后的元素越费时。时间简单度为O(n). 代码如下: ?php class HashNode public $key; public $value; public $nextNode; public function _constr
8、uct($key, $value, $nextNode=Null) $this-key = $key; $this-value = $value; $this-nextNode = $nextNode; class NewHashTable private $arr; private $size = 10; public function _construct() $this-arr = new SplFixedArray($this-size); private function simpleHash($key) $asciiTotal = 0; $len = strlen($key); f
9、or($i=0; $i$len; $i+) $asciiTotal += ord($key$i); return $asciiTotal % $this-size; public function set($key, $value) $hash = $this-simpleHash($key); if(isset($this-arr$hash) $newNode = new HashNode($key, $value, $this-arr$hash); else $newNode = new HashNode($key, $value, null); $this-arr$hash = $new
10、Node; return true; public function get($key) $hash = $this-simpleHash($key); $current = $this-arr$hash; while(!empty($current) if($current-key = $key) return $current-value; $current = $current-nextNode; return NULL; public function getList() return $this-arr; ? 对我们新的HashTable进行测试 代码如下: ?php /测试1 $n
11、ewArr = new NewHashTable(); for($i=0; $i30; $i+) $newArr-set(key.$i, value.$i); print_r($newArr-getList(); var_dump($newArr-get(key3); /SplFixedArray Object /( / 0 = HashNode Object /( / key = key23 / value = value23 / nextNode = HashNode Object /( / key = key14 / value = value14 / nextNode = HashNo
12、de Object /( / key = key3 / value = value3 / nextNode = / ) / / ) / / ) / / 1 = HashNode Object /( / key = key24 / value = value24 / nextNode = HashNode Object /( / key = key15 / value = value15 / nextNode = HashNode Object /( / key = key4 / value = value4 / nextNode = / ) / / ) / / ) / / 2 = HashNo
13、de Object /( / key = key25 / value = value25 / nextNode = HashNode Object /( / key = key16 / value = value16 / nextNode = HashNode Object /( / key = key5 / value = value5 / nextNode = / ) / / ) / / ) / / 3 = HashNode Object /( / key = key26 / value = value26 / nextNode = HashNode Object /( / key = k
14、ey17 / value = value17 / nextNode = HashNode Object /( / key = key6 / value = value6 / nextNode = / ) / / ) / / ) / / 4 = HashNode Object /( / key = key27 / value = value27 / nextNode = HashNode Object /( / key = key18 / value = value18 / nextNode = HashNode Object /( / key = key7 / value = value7 /
15、 nextNode = / ) / / ) / / ) / / 5 = HashNode Object /( / key = key28 / value = value28 / nextNode = HashNode Object /( / key = key19 / value = value19 / nextNode = HashNode Object /( / key = key8 / value = value8 / nextNode = / ) / / ) / / ) / / 6 = HashNode Object /( / key = key29 / value = value29
16、 / nextNode = HashNode Object /( / key = key10 / value = value10 / nextNode = HashNode Object /( / key = key9 / value = value9 / nextNode = / ) / / ) / / ) / / 7 = HashNode Object /( / key = key20 / value = value20 / nextNode = HashNode Object /( / key = key11 / value = value11 / nextNode = HashNode
17、 Object /( / key = key0 / value = value0 / nextNode = / ) / / ) / / ) / / 8 = HashNode Object /( / key = key21 / value = value21 / nextNode = HashNode Object /( / key = key12 / value = value12 / nextNode = HashNode Object /( / key = key1 / value = value1 / nextNode = / ) / / ) / / ) / / 9 = HashNode Object /( / key = key22 / value = value22 / nextNode = HashNode Object /( / key = key13 / value = value13 / nextNode = HashNode Object /( / key = key2 / value = value2 / nextNode = / ) / / ) / / ) / /) /string(6) value3 ? 更多信息请查看IT技术专栏 .