집 >백엔드 개발 >PHP 튜토리얼 >PHP는 해시 테이블 기능을 구현합니다.

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

墨辰丷원래의: 2018-05-30 11:22:011825검색

해시 알고리즘에 대해 조금 이해했습니다. 다음은 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);
  }
}
?>

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());
?>

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

충돌을 해결하는 Zip 방법. 지퍼 방식은 동일한 해시 값을 가진 모든 키를 연결된 목록에 넣어 충돌을 해결합니다. 예를 들어, 해싱 후 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;
  }
}
?>

Testing 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는 해시 테이블 기능을 구현합니다.

관련 기사