PHP는 HASH 테이블을 구현합니다.-PHP源码-php.cn

PHP는 HASH 테이블을 구현합니다.

大家讲道理

풀어 주다： 2016-11-09 14:43:05

원래의

1404명이 탐색했습니다.

해시 테이블이라고도 하는 해시 테이블은 키워드 Key를 배열의 위치에 매핑하여 레코드에 액세스합니다.

해시 함수의 기능은 모든 길이의 입력을 고정 길이 출력으로 변환하는 것입니다. HASH 알고리즘을 통해 출력은 HASH 값입니다

HASH 테이블의 시간 복잡도는 O(1)입니다

다음은 직접 나머지 방법을 사용하여 구현합니다

해시 테이블 만들기

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;
        }
     
}

로그인 후 복사

위의 경우 충돌 문제가 발생할 수 있습니다. 예를 들어 HASH 테이블이 가리키는

에 두 요소가 삽입됩니다. 첫 번째 요소의 HASH 값과 같습니다.

그런 다음 두 번째 각 요소가 첫 번째 요소

의 값을 덮어씁니다. 이때 지퍼 방법을 사용하여 충돌을 해결합니다. 동일한 HASH 값을 가진 바이트는 동일한 연결 리스트에 연결됩니다. 이 요소를 찾을 때는 연결리스트를 순회해야 합니다.

HASHNODE 생성

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;
                         
            }
         
}

로그인 후 복사

구현

    $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;);

로그인 후 복사