散列技术【哈希表】查找算法 PHP 版

散列技术:将记录的存储地址【散列地址】存储在一块连续的存储单元中,这一块存储单元称为散列表或叫哈希表HashTable,根据散列【哈希】函数f求得给定key的f(key)的映射,key对应的存储地址称为散列地址,跟数学中的函数差不多。
散列【哈希】函数设计方法:
本文使用的是除留余数数作为哈希函数。
冲突解决方案:
开放定址法【中的线性探测法,每次加1向右探测】
五大查找算法:顺序查找,二分查找,二叉树查找,索引查找,hash表查找

<?php
/**
 * Created by PhpStorm.
 * User: 1655664358@qq.com
 * Date: 2018/8/13
 * Time: 12:41
 */
define("HASHSIZE",5);

class Node
{
    private $data;
    private $index;
    public function setData($data)
    {
        $this->data = $data;
    }
    public function setIndex($data)
    {
        $this->index = $data;
    }
    public function getData()
    {
        return $this->data;
    }
    public function getIndex()
    {
        return $this->index;
    }
}
function hashData($data)
{
    return $data->getIndex()%HASHSIZE;
}
function insertNode(&$hashTable,$data)
{
    $hashAddress = hashData($data);
    while ($hashTable[$hashAddress]!=-1){
        $hashAddress = (++$hashAddress)%HASHSIZE;
    }
    $hashTable[$hashAddress] = $data;
}
function searchNode(&$hashTable,$data)
{
    $hashAddress = hashData($data);
    while ($hashTable[$hashAddress]->getIndex()!=$data->getIndex()){
        $hashAddress = (++$hashAddress)%HASHSIZE;
        if ($hashTable[$hashAddress]->getIndex()==-1||$hashAddress==hashData($data)){
            return -1;
        }
    }
    return $hashAddress;
}
(function(){

    $hashTable = [];
    for($i=0;$i<HASHSIZE;$i++){
        $hashTable[$i] = -1;
    }
    $node = new Node();
    $data = [
        [
            'index'=>1,
            'data'=>'php'
        ],
        [
            'index'=>3,
            'data'=>'python'
        ],
        [
            'index'=>2,
            'data'=>'java'
        ],
        [
            'index'=>5,
            'data'=>'arm'
        ],
        [
            'index'=>4,
            'data'=>'unix'
        ],
        [
            'index'=>3,
            'data'=>'linux'
        ],
    ];
    for ($j=0;$j<HASHSIZE;$j++){
        $obj = clone $node;
        $obj->setData($data[$j]['data']);
        $obj->setIndex($data[$j]['index']);
        insertNode($hashTable,$obj);
    }

    $obj = clone $node;
    $obj->setIndex(5);
    $result = searchNode($hashTable,$obj);

    $nodeResult = $hashTable[$result];
    echo $nodeResult->getData();
})();
勺颠颠
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 1

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!