PHP实现一个hash表（拉链法解决hash冲突）代码实例

小咪咪 2022-04-03 03:06 200阅读 0赞

<?php
    header('Content-type:text/html;charset=utf-8');
    
    class HashTable{
        private $buckets;
        private $size = 10;
        public function __construct()
        {
            $this->buckets = new SplFixedArray($this->size);
        }
    
        private function hash_func($key)
        {
            $strlen = strlen($key);
            $hash_val = 0;
            for ($i=0;$i<$strlen;$i++){
                $hash_val += ord($key[$i]);
            }
            return $hash_val%$this->size;
        }
    
        public function insert($key,$val)
        {
            $index = $this->hash_func($key);
            if(isset($this->buckets[$index])){
                $new_code = new HashNode($key,$val,$this->buckets[$index]);
            }else{
                $new_code = new HashNode($key,$val,null);
            }
            $this->buckets[$index] = $new_code;
        }
    
        public function find($key)
        {
            $index = $this->hash_func($key);
            $current = $this->buckets[$index];
            while (isset($current)) {
                if ($current->key == $key){
                    return $current->value;
                }
                $current = $current->next_node;
            }
            return null;
        }
    }
    
    class HashNode{
        public $key;
        public $value;
        public $next_node;
        public function __construct($key,$value,$next_node=null)
        {
            $this->key = $key;
            $this->value = $value;
            $this->next_node = $next_node;
        }
    
    
    }
    
    $hash = new HashTable();
    $hash->insert('value1','A');
    $hash->insert('value12','B');
    //echo $hash->find('value1');
    //echo $hash->find('value2');
    echo $hash->find('value1');
    echo $hash->find('value12');

记录一下实例，有兴趣的可以一起研究下。。。