PHP에서 해시 테이블 함수를 구현하는 예제에 대한 자세한 설명

php는 해시 테이블 기능을 구현합니다.

해시 테이블은 해시 테이블이라고도 불리는 가장 중요한 데이터 구조 중 하나입니다. PHP를 사용하여 해시 테이블 기능을 구현합니다. PHP는 해시 테이블의 추가, 삭제, 수정 및 쿼리를 시뮬레이션할 수 있습니다. 키를 배열의 위치에 매핑하여 액세스합니다. 매핑 함수를 해시 함수(Hash function)라 하고, 레코드를 저장하는 배열을 해시 테이블(Hash table)이라고 합니다.

해시 함수는 모든 길이와 유형의 키를 고정 길이 출력으로 변환합니다. 서로 다른 키가 동일한 해시를 가질 수 있습니다.

해시 테이블의 시간 복잡도는 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());
?>

값을 변경하면 더 많은 요소를 저장할 수 있습니다. 그러나 여전히 서로 다른 키가 동일한 해시 값을 생성할 수 있으므로 값을 할당할 때 후속 작업이 이전 작업을 덮어쓰게 되는 문제가 있습니다. 이 충돌 문제를 해결하기 위해 지퍼 방식을 사용해보자.

지퍼 방식은 충돌을 해결합니다. 지퍼 방식은 동일한 해시 값을 가진 모든 키를 연결된 목록에 넣어 충돌을 해결합니다. 예를 들어, 해싱 후 key3과 key14는 모두 0입니다. 그런 다음 배열의 키가 0인 이 두 값을 에 저장합니다. 연결리스트의 형태. 제 말이 이해가 안 되신다면 아래 예시를 보시고 인쇄된 내용을 보시면 이해가 되실 겁니다. 지퍼 방식이란 무엇입니까?

키와 값의 값을 저장하고 동일한 해시의 다른 요소를 저장하는 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;
  }
}
?>

Test our new 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에서 Hash table 함수를 구현하는 예제에 대한 자세한 설명입니다. , 기타 관련 내용은 PHP 중국어 홈페이지(www.php.cn)를 참고해주세요!