Hash表作為最重要的數(shù)據(jù)結構之一，也叫做散列表。使用PHP實現(xiàn)Hash表的功能。PHP可以模擬實現(xiàn)Hash表的增刪改查。通過對key的映射到數(shù)組中的一個位置來訪問。映射函數(shù)叫做Hash函數(shù)，存放記錄的數(shù)組稱為Hash表。

Hash函數(shù)把任意長度的和類型的key轉(zhuǎn)換成固定長度輸出。不同的key可能擁有相同的hash。

Hash表的時間復雜度為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中每個字符所對應的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的另一個元素。在同一條鏈上，查找越后的元素越費時。時間復雜度為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"

?>

更多信息請查看IT技術專欄