php implémente la fonction de table de hachage

Nous comprenons un peu l'algorithme de hachage. Voici un exemple d'utilisation de PHP pour implémenter une table de hachage. J'espère que ces exemples pourront vous aider. Les amis dans le besoin peuvent se référer à

php. Implémenter 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());
?>

Après avoir modifié la valeur, davantage d'éléments peuvent être stockés. 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 mon texte, veuillez regarder l'exemple ci-dessous et vous comprendrez après avoir regardé les informations imprimées. Quelle est la méthode de la fermeture éclair ? Il s’agit d’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, la recherche d’éléments ultérieurs prend plus de temps. 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 représente l'intégralité du contenu de cet article, j'espère qu'il sera utile à l'étude de chacun.

Recommandations associées :

php Explication graphique détaillée des précautions de sécurité de CodeIgniter

php et codeigniter utilisent le cookie de session en détail

php selon l'identifiant auto-incrémenté Méthode pour créer une classe de nombres unique

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!