Detaillierte Erläuterung von Beispielen für die Implementierung der Hash-Tabellenfunktion in PHP

php implementiert die Hash-Tabellenfunktion

Hash-Tabelle ist eine der wichtigsten Datenstrukturen, auch Hash-Tabelle genannt. Verwenden Sie PHP, um die Funktion der Hash-Tabelle zu implementieren. PHP kann das Hinzufügen, Löschen, Ändern und Abfragen einer Hash-Tabelle simulieren. Der Zugriff erfolgt durch Zuordnen des Schlüssels zu einer Position im Array. Die Zuordnungsfunktion wird als Hash-Funktion bezeichnet, und das Array, in dem Datensätze gespeichert werden, wird als Hash-Tabelle bezeichnet.

Die Hash-Funktion wandelt Schlüssel beliebiger Länge und beliebigen Typs in eine Ausgabe fester Länge um. Verschiedene Schlüssel können denselben Hash haben.

Die zeitliche Komplexität der Hash-Tabelle beträgt 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);
  }
}
?>

Testen wir unsere HashTable.

<?php
//测试1
$arr = new HashTable();
for($i=0; $i<15; $i++){
  $arr->set(&#39;key&#39;.$i, &#39;value&#39;.$i);
}
print_r($arr->getList());

//测试2
$arr->editSize(15);
for($i=0; $i<15; $i++){
  $arr->set(&#39;key&#39;.$i, &#39;value&#39;.$i);
}
print_r($arr->getList());
?>

Nach Änderung des Werts können weitere Elemente gespeichert werden. Es besteht jedoch immer noch das Problem, dass unterschiedliche Schlüssel möglicherweise denselben Hashwert erzeugen, sodass beim Zuweisen eines Werts die nachfolgende Operation die vorherige Operation überschreibt. Lassen Sie uns dieses Konfliktproblem mit der Reißverschlussmethode lösen.

Die Reißverschlussmethode löst Konflikte. Die Zipper-Methode löst Konflikte, indem sie alle Schlüssel mit demselben Hash-Wert in eine verknüpfte Liste einfügt. Beispielsweise sind key3 und key14 nach dem Hashing beide 0. Speichern Sie dann diese beiden Werte, wobei der Schlüssel des Arrays 0 ist die Form einer verknüpften Liste. Wenn Sie meine Worte nicht verstehen, schauen Sie sich bitte das Beispiel unten an und Sie werden es verstehen, nachdem Sie die gedruckten Informationen gelesen haben. Was ist die Zipper-Methode? Es handelt sich um eine verknüpfte Liste.

Erstellen Sie eine HashNode-Klasse, um die Werte von Schlüssel und Wert zu speichern, und speichern Sie ein weiteres Element desselben Hashs. In derselben Kette dauert es länger, spätere Elemente zu finden. Die Zeitkomplexität beträgt 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;
  }
}
?>

Testen Sie unsere neue HashTable

<?php
//测试1
$newArr = new NewHashTable();
for($i=0; $i<30; $i++){
  $newArr->set(&#39;key&#39;.$i, &#39;value&#39;.$i);
}
print_r($newArr->getList());
var_dump($newArr->get(&#39;key3&#39;));
?>

Das Obige ist ein detailliertes Beispiel für die Implementierung der Hash-Tabelle Funktion in PHP-Inhalten. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www.php.cn)!