利用PHP實現Hash表功能

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());
//SplFixedArray Object
//(
//    [0] => value14
//    [1] => value4
//    [2] => value5
//    [3] => value6
//    [4] => value7
//    [5] => value8
//    [6] => value10
//    [7] => value11
//    [8] => value12
//    [9] => value13
//)
//不同的key可能產生相同的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可能產生相同的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'));
//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"
?>