文档章节

使用拉链法解决冲突的简单hash表

liangwt
 liangwt
发布于 2016/09/29 20:14
字数 369
阅读 679
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

 Hash函数的作用是把任意长度的输入,通过hash算法变换成固定长度的输出,该输出就是hash值,hash表的复杂度为O(1)。

<?php 
/**
 * 一个简单的hash表
 * 使用拉链法解决冲突
 */
class hashtable{
	private $buckets;   //存储数据数组
	private $size = 10;

	public function __construct(){
		$this -> buckets = new SplFixedArray($this->size);
	}
	/**
	 * 通过把字符串相加取余得到hash值
	 * @param  string $key 关键字
	 * @return int         hash值
	 */
	private function hashfunc($key){
		$strlen  = strlen($key);
		$hashval = 0;
		for ($i=0; $i < $strlen; $i++) { 
			$hashval += ord($key[$i]);
		}
		return $hashval%$this->size;
	}
	/**
	 * 1. 使用hsahfuc计算关键字的hash值,通过hash值定位到hash表的指定位置
	 * 2. 如果此位置已经被占用,把新节点的$NextNode指向此节点,否则把$NextNode设置为NULL
	 * 3. 把新节点保存到hash表中
	 * @param  string $key   关键字
	 * @param  string $value 值
	 * @return void        
	 */
	public function insert($key,$value){
		$index = $this->hashfunc($key);
		if(isset($this->buckets[$index])){
			$newNode = new HashNode($key,$value,$this->buckets[$index]);
		}else{
			$newNode = new HashNode($key,$value,null);
		}
		$this->buckets[$index] = $newNode;
	}
	public function find($key){
		$index   = $this -> hashfunc($key);
		$current = $this -> buckets[$index];
		while (isset($current)) {
			if($current->key == $key){
				return $current->value;
			}
			$current = $current->nextNode;
		}
	}
}

class HashNode{
	public $key;            //节点关键字
	public $value;          //节点的值
	public $nextNode;       //具有相同hash值的节点的指针
	public function __construct($key,$value,$nextNode=null){
		$this -> key      = $key;
		$this -> value    = $value;
		$this -> nextNode = $nextNode;
	}
}

$test = new hashtable();
$test -> insert('key1','value1');
$test -> insert('key12','value12');
$test -> insert('key2','value2');
var_dump($test -> find('key1'));
var_dump($test -> find('key12'));
var_dump($test -> find('key2'));

 ?>

 

liangwt
粉丝 8
博文 16
码字总数 18357
作品 0
南京
程序员
私信 提问
加载中
请先登录后再评论。
访问安全控制解决方案

本文是《轻量级 Java Web 框架架构设计》的系列博文。 今天想和大家简单的分享一下,在 Smart 中是如何做到访问安全控制的。也就是说,当没有登录或 Session 过期时所做的操作,会自动退回到...

黄勇
2013/11/03
3.6K
8
SQLServer实现split分割字符串到列

网上已有人实现sqlserver的split函数可将字符串分割成行,但是我们习惯了split返回数组或者列表,因此这里对其做一些改动,最终实现也许不尽如意,但是也能解决一些问题。 先贴上某大牛写的s...

cwalet
2014/05/21
9.7K
0
CDH5: 使用parcels配置lzo

一、Parcel 部署步骤 1 下载: 首先需要下载 Parcel。下载完成后,Parcel 将驻留在 Cloudera Manager 主机的本地目录中。 2 分配: Parcel 下载后,将分配到群集中的所有主机上并解压缩。 3 激...

cloud-coder
2014/07/01
6.9K
1
代码生成器--Codgen

Codgen是一个基于数据库元数据模型,使用freemarker模板引擎来构建输出的代码生成器。freemarker的数据模型结构通常来说都是一个Map树状结构模型,codgen也不例外,它的数据模型这棵树的根节...

黄天政
2013/01/29
1.4W
2
XLSX读写库--EPPlus

EPPlus 是使用Open Office XML格式(xlsx)读写Excel 2007 / 2010文件的.net开发库。 EPPlus 支持: 单元格范围 单元格样式(Border, Color, Fill, Font, Number, Alignments) Charts 图片 形状...

匿名
2013/02/01
1W
2

没有更多内容

加载失败,请刷新页面

加载更多

红队之windows用户和组

目录 0x01 用户账户和组策略 0x02 Windows中的访问控制 0x03 安全标识符SID 0x04 用户账户控制(UAC) 用户帐户 用户帐户是对计算机用户身份的标识,本地用户帐户、密码存在本地计算机上,只...

黑白天安全团队
昨天
9
0
厉害了!百度智能云NIRO Pro智能机器人半年内连获三项产品设计大奖

短短半年内,百度智能云NIRO Pro智能机器人连获三项产品设计大奖,其中包括有“设计界奥斯卡”之称的德国红点奖,成功引领了全球助理机器人的工业设计和发展趋势风向标。红点奖评委这样评价,...

百度智能云
2019/12/04
0
0
StringBuider 在什么条件下、如何使用效率更高?

作者:后青春期的Keats cnblogs.com/keatsCoder/p/13212289.html 引言 都说 StringBuilder 在处理字符串拼接上效率要强于 String,但有时候我们的理解可能会存在一定的偏差。最近我在测试数据...

Object_Man
今天
0
0
发布更新|腾讯云 Serverless 产品动态 20200813

一、云函数 SCF + Ckafka 联合转储方案正式发布 发布时间: 2020-08-06 产品背景: SCF + Ckafka 联合转储方案可以帮忙用户节省使用与开发成本,用户可以将 Ckafka 消息转储同步转储至消息队...

腾讯云Serverless
31分钟前
5
0
如何正确强制执行Git推送? - How do I properly force a Git push?

问题: I've set up a remote non-bare "main" repo and cloned it to my computer. 我已经建立了一个远程的非裸露的“主”仓库,并将其克隆到我的计算机上。 I made some local changes, u......

javail
32分钟前
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部