目录
PHP核心技术与最佳实践之Hash算法
首页 后端开发 php教程 PHP核心技术与最佳实践之Hash算法_PHP教程

PHP核心技术与最佳实践之Hash算法_PHP教程

Jul 13, 2016 am 09:57 AM
技术 核心 算法

PHP核心技术与最佳实践之Hash算法

PHP核心技术与最佳实践之Hash算法

Hash表又称散列表,通过把关键字Key映射到数组中的一个位置来访问记录,以加快查找速度。这个映射函数称为Hash函数,存放记录的数组称为Hash表。

1. Hash函数

作用是把任意长度的输入,通过Hash算法变换成固定长度的输出,该输出就是Hash值。这种转换是一种压缩映射,也就是Hash值得空间通常远小于输入的空间,不输入可能会散列成相同的输出,而不可能从Hash值来唯一的确定输入值。

一个好的hash函数应该满足以下条件:每个关键字都可以均匀的分布到Hash表任意一个位置,并与其他已被散列到Hash表中的关键字不发生冲突。这是Hash函数最难实现的。

2. Hash算法

1) 直接取余法

直接取余法比较简单,直接用关键字k除以Hash表的大小m取余数,算法如下:

H(k) = k mod m

例如:Hash表的大小为m=12,所给关键字为k=100,则h(k) = 4.这种算法是一个求余操作,速度比较快。

2) 乘积取整法

乘积取整法首先使用关键字k乘以一个常数A(0

H(k) = floor (m*(kA mod 1))

其中,kA mod1表示kA的小数部分,floor是取整操作。

当关键字是字符串的时候,就不能用上面的Hash算法。因为字符串是由字符组成,所以可以把字符串所有的字符的ASCII码加起来得到一个整数,然后再按照上面的Hash算法去计算即可。

算法如下:

Function hash($key,$m){

$strlen= strlen($key);

$hashval= 0;

For($i=0;$i

$hashval+=ord($key{$I});

}

Return $hashval % $m;

}

3) 经典Hash算法Times33

Unsigned int DJBHash(char *str){

Unsignedint hash = 5381;

While(*str){

Hash+=(hash

}

Return (hash &0x7FFFFFFF)

}

算法思路就是不断乘以33,其效率和随机性都非常好,广泛运用于多个开源项目中,如Apache、Perl和PHP等。

3. Hash表

Hash表的时间复杂度为O(1),Hash表结构可用图表示:

\


要构造一个Hash表必须创建一个足够大的数组用于存放数据,另外还需要一个Hash函数把关键字Key映射到数组的某个位置。

Hash表的实现步骤:

1) 创建一个固定大小的数组用于存放数据。

2) 设计Hash函数。

3) 通过Hash函数把关键字映射到数组的某个位置,并在此位置上进行数据存取。

4. 使用PHP实现Hash表

首先创建一个HashTable类,有两个属性$buckets和$size。$buckets用于存储数据的数组,$size用于记录$buckets数组大小。然后在构造函数中为$buckets数组分配内存。代码如下:

ClassHashTable{

Private$buckets;

Private$size =10;

Publicfunction __construct(){

$this-> buckets =new SplFixedArray($this->size);

}

}

?>

在构造函数中,为$buckets数组分配了一个大小为10的数组。在这里使用了SPL扩展的SplFixedArray数组,不是一般的数组(array)

这是因为SplFixedArray数组更接近于C语言的数组,而且效率更高。在创建其数组时需要为其提供一个初始化的大小。

注意:要使用SplFixedArray数组必须开启SPl扩展。如果没有开启,可以使用一般的数组代替。

接着为Hash表指定一个Hash函数,为了简单起见,这里使用最简单的Hash算法。也就是上面提到了把字符串的所有字符加起来再取余。代码如下:

 

 

 

Public Function hashfunc($key){

$strlen= strlen($key);

$hashval= 0;

For($i=0;$i

$hashval+=ord($key{$I});

}

Return $hashval % $this->size;

}

有了Hash函数,就可以实现插入和查找方法。插入数据时,先通过Hash函数计算关键字所在Hash表的位置,然后把数据保存到此位置即可。代码如下:

Public function insert($key,$val){

$index= $this -> hashfunc($key);

$this-> buckets[$index] = $val;

}

查找数据方法与插入数据方法相似,先通过Hash函数计算关键字所在Hash表的位置,然后返回此位置的数据即可。代码如下:

Public function find($key){

$index= $this -> hashfunc($key);

Return$this ->buckets[$index];

}

至此,一个简单的Hash表编写完成,下面测试这个Hash表。代码清单如下:

$ht= new HashTable();

$ht->insert(‘key1’,’value1’);

$ht->insert(‘key2’,’value2’);

Echo$ht ->find(‘key1’);

Echo$ht ->find(‘key2’);

?>

完整代码:#hash.php

 

<!--?PHP
             Class HashTable{
                    Private$buckets;
                    Private $size=10;
                    Public function__construct(){
                           $this---> buckets =new SplFixedArray($this->size);
                    }
                    PublicFunction hashfunc($key){
                           $strlen= strlen($key);
                           $hashval= 0;
                           For($i=0;$i< $strlen;$i++){
                                  $hashval+=ord($key{$i});
                           }
                           return$hashval % $this->size;
                    }
                    Publicfunction insert($key,$val){
                           $index= $this -> hashfunc($key);
                           $this-> buckets[$index] = $val;
                    }
                    Publicfunction find($key){
                           $index= $this -> hashfunc($key);
                           Return$this ->buckets[$index];
                    }
 
 
             }
             $ht = newHashTable();
             $ht->insert(&#39;key1&#39;,&#39;value1&#39;);
             $ht->insert(&#39;key2&#39;,&#39;value2&#39;);
             Echo $ht->find(&#39;key1&#39;);
             Echo $ht->find(&#39;key2&#39;);
 
?>
登录后复制


 

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/984757.htmlTechArticlePHP核心技术与最佳实践之Hash算法 PHP核心技术与最佳实践之Hash算法 Hash表又称散列表,通过把关键字Key映射到数组中的一个位置来访问记录...
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解锁Myrise中的所有内容
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

CLIP-BEVFormer:显式监督BEVFormer结构,提升长尾检测性能 CLIP-BEVFormer:显式监督BEVFormer结构,提升长尾检测性能 Mar 26, 2024 pm 12:41 PM

写在前面&笔者的个人理解目前,在整个自动驾驶系统当中,感知模块扮演了其中至关重要的角色,行驶在道路上的自动驾驶车辆只有通过感知模块获得到准确的感知结果后,才能让自动驾驶系统中的下游规控模块做出及时、正确的判断和行为决策。目前,具备自动驾驶功能的汽车中通常会配备包括环视相机传感器、激光雷达传感器以及毫米波雷达传感器在内的多种数据信息传感器来收集不同模态的信息,用于实现准确的感知任务。基于纯视觉的BEV感知算法因其较低的硬件成本和易于部署的特点,以及其输出结果能便捷地应用于各种下游任务,因此受到工业

Stable Diffusion 3论文终于发布,架构细节大揭秘,对复现Sora有帮助? Stable Diffusion 3论文终于发布,架构细节大揭秘,对复现Sora有帮助? Mar 06, 2024 pm 05:34 PM

StableDiffusion3的论文终于来了!这个模型于两周前发布,采用了与Sora相同的DiT(DiffusionTransformer)架构,一经发布就引起了不小的轰动。与之前版本相比,StableDiffusion3生成的图质量有了显着提升,现在支持多主题提示,并且文字书写效果也得到了改善,不再出现乱码情况。 StabilityAI指出,StableDiffusion3是一个系列模型,其参数量从800M到8B不等。这一参数范围意味着该模型可以在许多便携设备上直接运行,从而显着降低了使用AI

自动驾驶与轨迹预测看这一篇就够了! 自动驾驶与轨迹预测看这一篇就够了! Feb 28, 2024 pm 07:20 PM

轨迹预测在自动驾驶中承担着重要的角色,自动驾驶轨迹预测是指通过分析车辆行驶过程中的各种数据,预测车辆未来的行驶轨迹。作为自动驾驶的核心模块,轨迹预测的质量对于下游的规划控制至关重要。轨迹预测任务技术栈丰富,需要熟悉自动驾驶动/静态感知、高精地图、车道线、神经网络架构(CNN&GNN&Transformer)技能等,入门难度很大!很多粉丝期望能够尽快上手轨迹预测,少踩坑,今天就为大家盘点下轨迹预测常见的一些问题和入门学习方法!入门相关知识1.预习的论文有没有切入顺序?A:先看survey,p

使用C++实现机器学习算法:常见挑战及解决方案 使用C++实现机器学习算法:常见挑战及解决方案 Jun 03, 2024 pm 01:25 PM

C++中机器学习算法面临的常见挑战包括内存管理、多线程、性能优化和可维护性。解决方案包括使用智能指针、现代线程库、SIMD指令和第三方库,并遵循代码风格指南和使用自动化工具。实践案例展示了如何利用Eigen库实现线性回归算法,有效地管理内存和使用高性能矩阵操作。

DualBEV:大幅超越BEVFormer、BEVDet4D,开卷! DualBEV:大幅超越BEVFormer、BEVDet4D,开卷! Mar 21, 2024 pm 05:21 PM

这篇论文探讨了在自动驾驶中,从不同视角(如透视图和鸟瞰图)准确检测物体的问题,特别是如何有效地从透视图(PV)到鸟瞰图(BEV)空间转换特征,这一转换是通过视觉转换(VT)模块实施的。现有的方法大致分为两种策略:2D到3D和3D到2D转换。2D到3D的方法通过预测深度概率来提升密集的2D特征,但深度预测的固有不确定性,尤其是在远处区域,可能会引入不准确性。而3D到2D的方法通常使用3D查询来采样2D特征,并通过Transformer学习3D和2D特征之间对应关系的注意力权重,这增加了计算和部署的

探究C++sort函数的底层原理与算法选择 探究C++sort函数的底层原理与算法选择 Apr 02, 2024 pm 05:36 PM

C++sort函数底层采用归并排序,其复杂度为O(nlogn),并提供不同的排序算法选择,包括快速排序、堆排序和稳定排序。

人工智能可以预测犯罪吗?探索CrimeGPT的能力 人工智能可以预测犯罪吗?探索CrimeGPT的能力 Mar 22, 2024 pm 10:10 PM

人工智能(AI)与执法领域的融合为犯罪预防和侦查开辟了新的可能性。人工智能的预测能力被广泛应用于CrimeGPT(犯罪预测技术)等系统,用于预测犯罪活动。本文探讨了人工智能在犯罪预测领域的潜力、目前的应用情况、所面临的挑战以及相关技术可能带来的道德影响。人工智能和犯罪预测:基础知识CrimeGPT利用机器学习算法来分析大量数据集,识别可以预测犯罪可能发生的地点和时间的模式。这些数据集包括历史犯罪统计数据、人口统计信息、经济指标、天气模式等。通过识别人类分析师可能忽视的趋势,人工智能可以为执法机构

改进的检测算法:用于高分辨率光学遥感图像目标检测 改进的检测算法:用于高分辨率光学遥感图像目标检测 Jun 06, 2024 pm 12:33 PM

01前景概要目前,难以在检测效率和检测结果之间取得适当的平衡。我们就研究出了一种用于高分辨率光学遥感图像中目标检测的增强YOLOv5算法,利用多层特征金字塔、多检测头策略和混合注意力模块来提高光学遥感图像的目标检测网络的效果。根据SIMD数据集,新算法的mAP比YOLOv5好2.2%,比YOLOX好8.48%,在检测结果和速度之间实现了更好的平衡。02背景&动机随着远感技术的快速发展,高分辨率光学远感图像已被用于描述地球表面的许多物体,包括飞机、汽车、建筑物等。目标检测在远感图像的解释中

See all articles