PHPでのハッシュテーブル関数の実装例を詳しく解説

黄舟
リリース: 2023-03-06 07:22:01
オリジナル
1640 人が閲覧しました

phpはハッシュテーブル関数を実装します

ハッシュテーブルは、ハッシュテーブルとも呼ばれる最も重要なデータ構造の1つです。 PHPを使用してハッシュテーブルの機能を実装します。 PHPはハッシュテーブルの追加、削除、変更、クエリをシミュレートできます。キーを配列内の位置にマッピングすることでアクセスします。マッピング関数をハッシュ関数と呼び、レコードを格納する配列をハッシュテーブルと呼びます。

ハッシュ関数は、任意の長さと型のキーを固定長の出力に変換します。異なるキーが同じハッシュを持つ場合があります。

ハッシュ テーブルの時間計算量は 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);
  }
}
?>
ログイン後にコピー

ハッシュ テーブルをテストしてみましょう。

<?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());
?>
ログイン後にコピー

値を変更すると、さらに多くの要素を保存できます。ただし、異なるキーが同じハッシュ値を生成する可能性があるため、値を割り当てると、後続の操作が前の操作を上書きしてしまうという問題が依然として残っています。この競合の問題を解決するために、ジッパー メソッドを使用してみましょう。

競合を解決するための Zip メソッド。ジッパーメソッドは、同じハッシュ値を持つすべてのキーをリンクされたリストに入れることで競合を解決します。たとえば、ハッシュ化後、key3 と key14 は両方とも 0 になります。次に、配列のキーが 0 であるこれら 2 つの値を に格納します。リンクされたリストの形式。私の言葉が理解できない場合は、以下の例を見てください。印刷された情報を見れば理解できると思います。ジッパー方式とは何ですか? 連結リストです。

キーとバリューの値を格納するHashNodeクラスを作成し、同じハッシュの別の要素を格納します。同じチェーン上では、後の要素を見つけるのに時間がかかります。時間計算量は 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;
  }
}
?>
ログイン後にコピー

新しい 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;));
?>
ログイン後にコピー

上記は、PHP でのハッシュ テーブル関数の実装例の詳細な説明です。詳細については、PHP を参照してください。中国語のウェブサイト (www.php.cn)!

関連ラベル:
ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート
私たちについて 免責事項 Sitemap
PHP中国語ウェブサイト:福祉オンライン PHP トレーニング,PHP 学習者の迅速な成長を支援します!