PHP implementiert die Hash-Tabellenfunktion

Wir haben ein wenig Verständnis für den Hash-Algorithmus. Hier ist ein Beispiel für die Verwendung von PHP zur Implementierung einer Hash-Tabelle. Ich hoffe, diese Beispiele können Ihnen helfen Hash-Tabellenfunktion implementieren

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 meinen Text 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 die Suche nach späteren Elementen länger. Die Zeitkomplexität ist 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 der gesamte Inhalt dieses Artikels. Ich hoffe, er wird für das Studium aller hilfreich sein.

Verwandte Empfehlungen:

php

Detaillierte grafische Erläuterung der Sicherheitsvorkehrungen für Codeigniter

php

und Codeigniter verwenden Session-Cookie im Detail

php

gemäß der sich selbst erhöhenden ID Methode zum Erstellen einer eindeutigen Zahlenklasse

Das obige ist der detaillierte Inhalt vonPHP implementiert die Hash-Tabellenfunktion. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!