Hash演算法我們多少會了解一點了，以下來介紹利用php實現Hash表的一個例子，希望這些例子可以給各位帶來幫助,需要的朋友可以參考下
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(){
//SplFixedArray创建的数组比一般的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($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進行測試。
<?php
//测试1
$arr = new HashTable();
for($i=0; $i<15; $i++){
$arr->set('key'.$i, 'value'.$i);
}
print_r($arr->getList());
//测试2
$arr->editSize(15);
for($i=0; $i<15; $i++){
$arr->set('key'.$i, 'value'.$i);
}
print_r($arr->getList());
?>登入後複製
改變了值之後可以儲存更多的元素。但是仍然存在不同的key可能產生相同的hash值，那麼賦值的時候後操作會覆寫前運算的問題。這種衝突的問題我們來用拉鍊法來解決。
拉鍊法解決衝突。拉鍊法解決衝突的做法是將所有的相同Hash值的key放在一個鍊錶中，例如key3和key14在hash之後都是0，那麼在數組的鍵為0的地方存儲這兩個值，形式是鍊錶。如果無法理解我的文字，請看下面的範例，看一下列印資訊就明白了。拉鍊法是什麼，就是鍊錶。
建立一個HashNode類，用來儲存key和value的值，並且儲存相同hash的另一個元素。在同一條鏈上，找出越後的元素越費時。時間複雜度為O(n).
<?php
class HashNode{
public $key;
public $value;
public $nextNode;
public function __construct($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);
for($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] = $newNode;
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
$newArr = new NewHashTable();
for($i=0; $i<30; $i++){
$newArr->set('key'.$i, 'value'.$i);
}
print_r($newArr->getList());
var_dump($newArr->get('key3'));
?>登入後複製
#以上就是本文的全部內容，希望對大家的學習有所幫助。
相關推薦：
php中codeigniter安全性注意事項圖文詳解
php及codeigniter使用session-cookie的方法詳解
php 根據自增id建立唯一編號類別的方法
#
以上是php 實作Hash表功能的詳細內容。更多資訊請關注PHP中文網其他相關文章！
