如何在php項(xiàng)目中實(shí)現(xiàn)一個(gè)Hash表功能

這篇文章將為大家詳細(xì)講解有關(guān)如何在php項(xiàng)目中實(shí)現(xiàn)一個(gè)Hash表功能，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。

php 實(shí)現(xiàn)Hash表功能

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

Hash函數(shù)把任意長(zhǎng)度的和類(lèi)型的key轉(zhuǎn)換成固定長(zhǎng)度輸出。不同的key可能擁有相同的hash。
Hash表的時(shí)間復(fù)雜度為O(1)

<?php
class HashTable{
  private $arr = array();
  private $size = 10;
  public function __construct(){
    //SplFixedArray創(chuàng)建的數(shù)組比一般的Array()效率更高，因?yàn)楦咏麮的數(shù)組。創(chuàng)建時(shí)需要指定尺寸
    $this->arr = new SplFixedArray($this->size);
  }
  /**
   * Description: 簡(jiǎn)單hash算法。輸入key，輸出hash后的整數(shù)
   * @param $key
   * @return int
   */
  private function simpleHash($key){
    $len = strlen($key);
    //key中每個(gè)字符所對(duì)應(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);
  }
}
?>

 下面對(duì)我們的HashTable進(jìn)行測(cè)試。

<?php
//測(cè)試1
$arr = new HashTable();
for($i=0; $i<15; $i++){
  $arr->set('key'.$i, 'value'.$i);
}
print_r($arr->getList());

//測(cè)試2
$arr->editSize(15);
for($i=0; $i<15; $i++){
  $arr->set('key'.$i, 'value'.$i);
}
print_r($arr->getList());
?>

 改變了值之后可以存放更多的元素。但是仍然存在不同的key可能產(chǎn)生相同的hash值，那么賦值的時(shí)候后操作會(huì)覆蓋前操作的問(wèn)題。這種沖突的問(wèn)題我們來(lái)用拉鏈法解決。

拉鏈法解決沖突。拉鏈法解決沖突的做法是將所有的相同Hash值的key放在一個(gè)鏈表中，比如key3和key14在hash之后都是0，那么在數(shù)組的鍵為0的地方存儲(chǔ)這兩個(gè)值，形式是鏈表。如果不能理解我的文字，請(qǐng)看下面的示例，看一下打印信息就明白了。拉鏈法是什么，就是鏈表。

創(chuàng)建一個(gè)HashNode類(lèi)，用來(lái)存儲(chǔ)key和value的值，并且存儲(chǔ)相同hash的另一個(gè)元素。在同一條鏈上，查找越后的元素越費(fèi)時(shí)。時(shí)間復(fù)雜度為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;
  }
}
?>

對(duì)我們新的HashTable進(jìn)行測(cè)試

<?php
//測(cè)試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'));
?>

關(guān)于如何在php項(xiàng)目中實(shí)現(xiàn)一個(gè)Hash表功能就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。