Hash表作為最重要的數(shù)據(jù)結(jié)構(gòu)之一，也叫做散列表。使用PHP實現(xiàn)Hash表的功能。PHP可以模擬實現(xiàn)Hash表的增刪改查。通過對key的映射到數(shù)組中的一個位置來訪問。映射函數(shù)叫做Hash函數(shù)，存放記錄的數(shù)組稱為Hash表。
Hash函數(shù)把任意長度的和類型的key轉(zhuǎn)換成固定長度輸出。不同的key可能擁有相同的hash。
Hash表的時間復(fù)雜度為O(1)
代碼如下:
<?php
class HashTable{
private $arr = array();
private $size = 10;
public function __construct(){
//SplFixedArray創(chuàng)建的數(shù)組比一般的Array()效率更高，因為更接近C的數(shù)組。創(chuàng)建時需要指定尺寸
$this->arr = new SplFixedArray($this->size);
}
/**
* Description: 簡單hash算法。輸入key，輸出hash后的整數(shù)
* @param $key
* @return int
*/
private function simpleHash($key){
$len = strlen($key);
//key中每個字符所對應(yīng)的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());
//SplFixedArray Object
//(
// [0] => value14
// [1] => value4
// [2] => value5
// [3] => value6
// [4] => value7
// [5] => value8
// [6] => value10
// [7] => value11
// [8] => value12
// [9] => value13
//)
//不同的key可能產(chǎn)生相同的hash值，那么賦值的時候后操作會覆蓋前操作。
//測試2
$arr->editSize(15);
for($i=0; $i<15; $i++){
$arr->set('key'.$i, 'value'.$i);
}
print_r($arr->getList());
//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可能產(chǎn)生相同的hash值，那么賦值的時候后操作會覆蓋前操作的問題。這種沖突的問題我們來用拉鏈法解決。
拉鏈法解決沖突。拉鏈法解決沖突的做法是將所有的相同Hash值的key放在一個鏈表中，比如key3和key14在hash之后都是0，那么在數(shù)組的鍵為0的地方存儲這兩個值，形式是鏈表。如果不能理解我的文字，請看下面的示例，看一下打印信息就明白了。拉鏈法是什么，就是鏈表。
創(chuàng)建一個HashNode類，用來存儲key和value的值，并且存儲相同hash的另一個元素。在同一條鏈上，查找越后的元素越費時。時間復(fù)雜度為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'));
//SplFixedArray Object
//(
// [0] => HashNode Object
//(
// [key] => key23
// [value] => value23
// [nextNode] => HashNode Object
//(
// [key] => key14
// [value] => value14
// [nextNode] => HashNode 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] => HashNode 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] => key17
// [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
// [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
// [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 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"
?>