Heim > php教程 > PHP源码 > Hauptteil

PHP implementiert die HASH-Tabelle

大家讲道理
Freigeben: 2016-11-09 14:43:05
Original
1379 Leute haben es durchsucht

Hash-Tabelle, auch Hash-Tabelle genannt, greift auf Datensätze zu, indem sie das Schlüsselwort Key einer Position im Array zuordnet

Die Funktion der Hash-Funktion besteht darin, Eingaben beliebiger Länge in eine Ausgabe fester Länge umzuwandeln durch den HASH-Algorithmus. Die Ausgabe ist der HASH-Wert

Die Zeitkomplexität der HASH-Tabelle ist O(1)

Im Folgenden wird die direkte Restmethode zur Implementierung verwendet

Erstellen Sie eine Hashtabelle

class HashTable{
     
    private $buckets;          //用于存储数据的数组
    private $size = 12;          //记录buckets 数组的大小
    public function __construct(){
         
        $this->buckets = new SplFixedArray($this->size);
        //SplFixedArray效率更高,也可以用一般的数组来代替
    }
     
    private function hashfunc($key){
        $strlen = strlen($key);  //返回字符串的长度
        $hashval = 0;     
        for($i = 0; $i<$strlen ; $i++){
            $hashval +=ord($key[$i]); //返回ASCII的值
        }
        return $hashval%$this->size;    //    返回取余数后的值
    }
    public function insert($key,$value){
     
    $index = $this->hashfunc($key);
    if(isset($this->buckets[$index])){
        $newNode = new HashNode($key,$value,$this->buckets[$index]);
            }else{
    $newNode = new HashNode($key,$value,null);
            }
    $this->buckets[$index] = $newNode;
        }
     
    public function find($key){
         
            $index = $this->hashfunc($key);
             
            $current = $this->buckets[$index];
            echo "</br>";
            var_dump($current);
            while(isset($current)){    //遍历当前链表
                if($current->key==$key){    //比较当前结点关键字
                    return $current->value;
                }
                $current = $current->nextNode;
                //return $current->value;
            }
            return NULL;
        }
     
}
Nach dem Login kopieren

Das oben Gesagte kann zu Konfliktproblemen führen. Beispielsweise werden zwei Elemente in die

eingefügt, auf die die HASH-Tabelle zeigt Derselbe wie der HASH-Wert des ersten Elements.

Dann überschreibt das zweite Element den Wert des ersten Elements.

Zu diesem Zeitpunkt verwenden wir die Zipper-Methode, um den Konflikt zu lösen: Bytes mit demselben HASH-Wert werden in derselben verknüpften Liste verknüpft. Wenn Sie nach diesem Element suchen, müssen Sie die verknüpfte Liste durchlaufen.

HASHNODE erstellen

class HashNode{
            public $key;       //关键字
            public $value;     //数据
            public $nextNode;  //HASHNODE来存储信息
            public function __construct($key,$value,$nextNode = NULL){
                        $this->key = $key;
                        $this->value = $value;
                        $this->nextNode = $nextNode;
                         
            }
         
}
Nach dem Login kopieren

Implementieren

    $ht = new HashTable();
     $ht->insert(&#39;key1&#39;,&#39;value1&#39;);
     //$ht->insert(&#39;key12&#39;,&#39;value12&#39;);
        echo $ht->find(&#39;key1&#39;);
Nach dem Login kopieren


Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Empfehlungen
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage