《PHP實戰：php 實現Hash表功能實例詳解》要點：
本文介紹了PHP實戰：php 實現Hash表功能實例詳解，希望對您有用。如果有疑問，可以聯系我們。
php 實現Hash表功能PHP編程
Hash表作為最重要的數據結構之一,也叫做散列表.使用PHP實現Hash表的功能.PHP可以模擬實現Hash表的增刪改查.通過對key的映射到數組中的一個位置來訪問.映射函數叫做Hash函數,存放記錄的數組稱為Hash表.
PHP編程
Hash函數把任意長度的和類型的key轉換成固定長度輸出.不同的key可能擁有相同的hash.
Hash表的時間復雜度為O(1)PHP編程
<?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編程
<?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值,那么賦值的時候后操作會覆蓋前操作的問題.這種沖突的問題我們來用拉鏈法解決.PHP編程
拉鏈法解決沖突.拉鏈法解決沖突的做法是將所有的相同Hash值的key放在一個鏈表中,比如key3和key14在hash之后都是0,那么在數組的鍵為0的地方存儲這兩個值,形式是鏈表.如果不能理解我的文字,請看下面的示例,看一下打印信息就明白了.拉鏈法是什么,就是鏈表.PHP編程
創建一個HashNode類,用來存儲key和value的值,并且存儲相同hash的另一個元素.在同一條鏈上,查找越后的元素越費時.時間復雜度為O(n).PHP編程
<?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編程
<?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'));
?>
感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!PHP編程
轉載請注明本頁網址：
http://www.snjht.com/jiaocheng/2561.html
