PHP 实现HASH表

WBOY
Freigeben: 2016-06-20 12:45:06
Original
1098 Leute haben es durchsucht

Hash 表又称散列表,通过关键字Key 映射到数组中一个位置来访问记录

Hash 函数的作用是把任意长度的输入,通过HASH算法变换成固定长度的输出,该输出就是HASH值

HASH表的时间复杂度为O(1)

下文使用直接取余法实现

创建一个hashtable

class HashTable{		private $buckets;			//用于存储数据的数组	private $size = 12;			//记录buckets 数组的大小	public function __construct(){				$this->buckets = new SplFixedArray($this->size);		//SplFixedArray效率更高,也可以用一般的数组来代替	}		private function hashfunc($key){		$strlen = strlen($key); 	//返回字符串的长度		$hashval = 0;				for($i = 0; $i<$strlen ; $i++){			$hashval +=ord($key[$i]); //返回ASCII的值		}		return $hashval%$this->size;    //    返回取余数后的值	}	public function insert($key,$value){		$index = $this->hashfunc($key);	if(isset($this->buckets[$index])){        $newNode = new HashNode($key,$value,$this->buckets[$index]);			}else{	$newNode = new HashNode($key,$value,null);			}	$this->buckets[$index] = $newNode;		}		public function find($key){					$index = $this->hashfunc($key);						$current = $this->buckets[$index];			echo "</br>";			var_dump($current);			while(isset($current)){    //遍历当前链表				if($current->key==$key){    //比较当前结点关键字					return $current->value;				}				$current = $current->nextNode;				//return $current->value;			}			return NULL;		}	}
Nach dem Login kopieren

上述可能会有冲突问题,比如HASH表指向的

插入两个元素,第二个元素的HASH值与第一个值得HASH值相同

则第二个元素将覆盖第一个元素的值

这时我们用拉链法解决冲突:具有相同HASH值得字节点链接在同一个链表中。查找这个元素的时候就必须遍历这条链表。

创建 HASHNODE

class HashNode{			public $key;		//关键字			public $value;		//数据			public $nextNode;	//HASHNODE来存储信息			public function __construct($key,$value,$nextNode = NULL){						$this->key = $key;						$this->value = $value;						$this->nextNode = $nextNode;									}		}
Nach dem Login kopieren

实现

    $ht = new HashTable();     $ht->insert('key1','value1');     //$ht->insert('key12','value12');		echo $ht->find('key1');
Nach dem Login kopieren


Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage