php 實現Hash表功能
Hash表作為最重要的數據結構之一，也叫做散列表。使用PHP實現Hash表的功能。PHP可以模擬實現Hash表的增刪改查。通過對key的映射到數組中的一個位置來訪問。映射函數叫做Hash函數，存放記錄的數組稱為Hash表。
Hash函數把任意長度的和類型的key轉換成固定長度輸出。不同的key可能擁有相同的hash。
Hash表的時間復雜度為O(1)
<?phpclass 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).
<?phpclass 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'));?>感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
圖片精選
