Explication détaillée d'exemples d'implémentation de la fonction de table de hachage en php

php implémente la fonction de table de hachage

La table de hachage est l'une des structures de données les plus importantes, également appelée table de hachage. Utilisez PHP pour implémenter la fonction de table de hachage. PHP peut simuler l'ajout, la suppression, la modification et l'interrogation d'une table de hachage. Accessible en mappant la clé à une position dans le tableau. La fonction de mappage est appelée fonction de hachage et le tableau stockant les enregistrements est appelé table de hachage.

La fonction Hash convertit les clés de n'importe quelle longueur et type en sortie de longueur fixe. Différentes clés peuvent avoir le même hachage.

La complexité temporelle de la table de hachage est 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);
  }
}
?>

Testons notre 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());
?>

Plus d'éléments peuvent être stockés après avoir modifié la valeur. Cependant, il existe toujours un problème : différentes clés peuvent produire la même valeur de hachage. Ainsi, lors de l'attribution d'une valeur, l'opération suivante écrasera l'opération précédente. Utilisons la méthode zipper pour résoudre ce problème de conflit.

La méthode zipper résout les conflits. La méthode zipper résout les conflits en plaçant toutes les clés avec la même valeur de hachage dans une liste chaînée. Par exemple, key3 et key14 sont toutes deux 0 après le hachage. Stockez ensuite ces deux valeurs où la clé du tableau est 0, dans. sous la forme d'une liste chaînée. Si vous ne comprenez pas mes propos, veuillez regarder l'exemple ci-dessous et vous comprendrez après avoir regardé les informations imprimées. Quelle est la méthode de fermeture éclair ? C'est une liste chaînée.

Créez une classe HashNode pour stocker les valeurs de clé et de valeur, et stockez un autre élément du même hachage. Sur la même chaîne, il faut plus de temps pour retrouver les éléments ultérieurs. La complexité temporelle est 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;
  }
}
?>

Testez notre nouvelle 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;));
?>

Ce qui précède est un exemple détaillé de la façon d'implémenter la table de hachage fonction dans le contenu PHP, veuillez faire attention au site Web PHP chinois (www.php.cn) pour plus de contenu connexe !