.png)
相關(guān)關(guān)鍵詞
關(guān)于我們
最新文章
php 實現(xiàn)Hash表功能實例詳解
php 實現(xiàn)Hash表功能
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);
}
}
?>