Hash表

俗称散列表、是比较重要的数据结构，它是把关键字通过某个实现函数(Hash函数)映射到数组(Hash 表)中的某一个特定位置，以加快查找的速度。

Hash函数

  它的作用是将任意的Key通过指定的算法换算成固定的长度的值(Hash值)、但是在某些情况下不同的Key通过Hash函数转换过后可能会产生相同的值，这种现象称之为Hash碰撞.

Hash算法

• 直接取余法

Hash表的大小为L、指定Key是K、则：换算的值 L(K) = fmod(K, L); 

• 乘积取余法

关健字             K
常数C在(0, 1)区间  C
Hash表大小         L

L(k) = floor(L *fmod(KC, 1))

如果 K是字符串 把字符串里每一个字符 ord()后累加。

• Timess33算法

这里可以参考下大V的Blog ===
鸟哥Blog

PHP实现Hash表

图示

流程图

代码

//hash表
class HashTable
{
    private $buckets;
    private $size = 10;

    public function __construct()
    {
        //创建一个长度为10的一个数组
        $this->buckets = new \SplFixedArray($this->size);
    }

    /**
     * 通过此简单函数转换成指定映射成一个指定位置
     *
     * @param string $key
     * @return float
     */
    public function buildHashValByKey(string $key)
    {
        $hashVal = 0;
        $len     = strlen($key);

        for ($i = 0; $i < $len; $i++) {
            $hashVal += ord($key[$i]);
        }

        return fmod($hashVal, $this->size);
    }

    /**
     * 插入 key val
     *
     * @param string $key
     * @param $val
     */
    public function insert(string $key, $val)
    {
        $index = $this->buildHashValByKey($key);

        if (isset($this->bukets[$index])) {
            //为了解决 Hash 冲突，这里采用常用的 拉链法
            //如果有值 采用链表的头插法插入新数据
            $newHashNode = new HashNode($key, $val, $this->buckets[$index]);
        } else {
            $newHashNode = new HashNode($key, $val, null);
        }

        $this->buckets[$index] = $newHashNode;
    }

    /**
     * 通过指定 Key 查询 值
     *
     * @param string $key
     * @return mixed|null
     */
    public function find(string $key)
    {
        $index = $this->buildHashValByKey($key);

        /** @var HashNode $node */
        $node  = $this->getNodeByIndex($index);

        if (!$node) {
            return null;
        }

        while ($node) {
            if ($node->getKey() == $key) {
                return $node->getVal();
            }
            //断续寻找下一个结点
            $node = $node->getNextNode();
        }

        return null;
    }
    
    /**
     * 直接获取节点
     *
     * @param float $index
     * @return |null
     */
    public function getNodeByIndex(float $index)
    {
        return $this->buckets[$index] ?? null;
    }

}

//链表节点
class HashNode
{
    private $key;
    private $val;
    private $nextNode;

    public function __construct($key, $val, HashNode $nextNode = null)
    {
        $this->key = $key;
        $this->val = $val;
        $this->nextNode = $nextNode;
    }

    /**
     * @return mixed
     */
    public function getKey()
    {
        return $this->key;
    }

    /**
     * @return mixed
     */
    public function getVal()
    {
        return $this->val;
    }

    /**
     * @return mixed
     */
    public function getNextNode()
    {
        return $this->nextNode;
    }
}

测试

<?php

namespace Tests;

class HashTableTest extends TestCase
{

    /**
     * @test
     */
    public function testTable()
    {
         $table = new HashTable();

        $table->insert('key1', 'value1');
        $this->assertEquals(8, $table->buildHashValByKey('key1'));
        $this->assertEquals('value1', $table->find('key1'));

        $table->insert('key12', 'value12');
        $this->assertEquals(8, $table->buildHashValByKey('key12'));
        $this->assertEquals('value12', $table->find('key12'));

        //Hash碰撞后采用的拉链法存储
        $this->assertEquals('key1', $table->getNodeByIndex(8)->getNextNode()->getKey());


        $table->insert('key13', 'value13');
        $this->assertEquals(9, $table->buildHashValByKey('key13'));
        $this->assertEquals('value13', $table->find('key13'));
    }
}

谢谢~~