当前位置:Gxlcms > PHP教程 > php实现Hash表功能

php实现Hash表功能

时间:2021-07-01 10:21:17 帮助过:6人阅读

Hash算法我们多少会了解一点了,下面来介绍利用php实现Hash表的一个例子,希望这些例子可以给各位带来帮助,需要的朋友可以参考下

php 实现Hash表功能

Hash表作为最重要的数据结构之一,也叫做散列表。使用PHP实现Hash表的功能。PHP可以模拟实现Hash表的增删改查。通过对key的映射到数组中的一个位置来访问。映射函数叫做Hash函数,存放记录的数组称为Hash表。

Hash函数把任意长度的和类型的key转换成固定长度输出。不同的key可能拥有相同的hash。
Hash表的时间复杂度为O(1)

  1. <?php
  2. class HashTable{
  3. private $arr = array();
  4. private $size = 10;
  5. public function __construct(){
  6. //SplFixedArray创建的数组比一般的Array()效率更高,因为更接近C的数组。创建时需要指定尺寸
  7. $this->arr = new SplFixedArray($this->size);
  8. }
  9. /**
  10. * 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($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 = $this->simpleHash($key); return $this->arr[$hash]; } public function getList(){ return $this->arr; } public function editSize($size){ $this->size = $size; $this->arr->setSize($size); } } ?>

下面对我们的HashTable进行测试。

  1. <?php
  2. //测试1
  3. $arr = new HashTable();
  4. for($i=0; $i<15; $i++){
  5. $arr->set('key'.$i, 'value'.$i);
  6. }
  7. print_r($arr->getList());
  8. //测试2
  9. $arr->editSize(15);
  10. for($i=0; $i<15; $i++){
  11. $arr->set('key'.$i, 'value'.$i);
  12. }
  13. print_r($arr->getList());
  14. ?>

改变了值之后可以存放更多的元素。但是仍然存在不同的key可能产生相同的hash值,那么赋值的时候后操作会覆盖前操作的问题。这种冲突的问题我们来用拉链法解决。

拉链法解决冲突。拉链法解决冲突的做法是将所有的相同Hash值的key放在一个链表中,比如key3和key14在hash之后都是0,那么在数组的键为0的地方存储这两个值,形式是链表。如果不能理解我的文字,请看下面的示例,看一下打印信息就明白了。拉链法是什么,就是链表。

创建一个HashNode类,用来存储key和value的值,并且存储相同hash的另一个元素。在同一条链上,查找越后的元素越费时。时间复杂度为O(n).

  1. <?php
  2. class HashNode{
  3. public $key;
  4. public $value;
  5. public $nextNode;
  6. public function __construct($key, $value, $nextNode=Null){
  7. $this->key = $key;
  8. $this->value = $value;
  9. $this->nextNode = $nextNode;
  10. }
  11. }
  12. class NewHashTable{
  13. private $arr;
  14. private $size = 10;
  15. public function __construct(){
  16. $this->arr = new SplFixedArray($this->size);
  17. }
  18. private function simpleHash($key){
  19. $asciiTotal = 0;
  20. $len = strlen($key);
  21. for($i=0; $i<$len; $i++){
  22. $asciiTotal += ord($key[$i]);
  23. }
  24. return $asciiTotal % $this->size;
  25. }
  26. public function set($key, $value){
  27. $hash = $this->simpleHash($key);
  28. if(isset($this->arr[$hash])){
  29. $newNode = new HashNode($key, $value, $this->arr[$hash]);
  30. }else{
  31. $newNode = new HashNode($key, $value, null);
  32. }
  33. $this->arr[$hash] = $newNode;
  34. return true;
  35. }
  36. public function get($key){
  37. $hash = $this->simpleHash($key);
  38. $current = $this->arr[$hash];
  39. while(!empty($current)){
  40. if($current->key == $key){
  41. return $current->value;
  42. }
  43. $current = $current->nextNode;
  44. }
  45. return NULL;
  46. }
  47. public function getList(){
  48. return $this->arr;
  49. }
  50. }
  51. ?>

对我们新的HashTable进行测试

  1. <?php
  2. //测试1
  3. $newArr = new NewHashTable();
  4. for($i=0; $i<30; $i++){
  5. $newArr->set('key'.$i, 'value'.$i);
  6. }
  7. print_r($newArr->getList());
  8. var_dump($newArr->get('key3'));
  9. ?>

以上就是本文的全部内容,希望对大家的学习有所帮助。


相关推荐:

php中codeigniter安全性注意事项图文详解

php及codeigniter使用session-cookie的方法详解

php 根据自增id创建唯一编号类的方法

以上就是php 实现Hash表功能的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行