文档章节

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

liangwt
 liangwt
发布于 2016/09/29 20:14
字数 369
阅读 83
收藏 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
粉丝 7
博文 15
码字总数 14721
作品 0
南京
程序员
私信 提问
NSDictionary实现原理

NSDictionary是基于key - value 方式,把key映射到一个hash表中实现的 key 需要支持NSCopying协议,实际上不支持也可以作为key,但在swift中就必须要支持,支持NSCopying的原因在于,NSDicit...

庄msia
2018/08/16
0
0
hash分布式算法及冲突解决方案

虽然我们不希望发生冲突,但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度,而且事先并不知道关键字的具体取值时。冲突就难免会发 生。另外,当关键字的实际取值大于哈...

吴之恒心
2017/02/24
0
0
Hashmap和HashTable

1. 关于HashMap的一些说法: HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。HashMap的底层结构是一个数组,数组中的每一项是一条链表。 HashMap的实例有俩个参数影响其...

就是小灰灰
2017/07/17
0
0
Java HashMap源码分析

原文出处:Snailclimb 本文从 Hash 方法开始,通过分析源码,深入介绍了 JDK 不同版本中 HashMap 的实现。 HashMap 简介 HashMap 主要用来存放键值对,它基于哈希表的Map接口实现,是常用的J...

Snailclimb
01/02
0
0
HashMap 并发 Map 是什么 内部原理什么 存储方式 hashcode 扩容 默认容量等

HashMap的数据结构 http://blog.csdn.net/gaopu12345/article/details/50831631 ??看一下 数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。 数组 数组存储区间是连续...

宇你同在
2018/07/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx日志自动切割

1.日志配置(Nginx 日志) access.log----记录哪些用户,哪些页面以及用户浏览器,IP等访问信息;error.log------记录服务器错误的日志 #配置日志存储路径:location / {      a...

em_aaron
昨天
1
0
java 反射

基本概念 RTTI,即Run-Time Type Identification,运行时类型识别。RTTI能在运行时就能够自动识别每个编译时已知的类型。   要想理解反射的原理,首先要了解什么是类型信息。Java让我们在运...

细节探索者
昨天
1
0
推荐转载连接

https://www.cnblogs.com/ysocean/p/7409779.html#_label0

小橙子的曼曼
昨天
3
0
雷军亲自打造的套餐了解下:用多少付多少

12月28日消息,小米科技创始人兼CEO雷军微博表示,小米移动任我行套餐方案,原则上就是明明白白消费,用多少付多少,不用不花钱!上网、电话和短信都是一毛钱,上网0.1元/M,电话0.1元/分钟,...

linuxCool
昨天
6
0
协议简史:如何学习网络协议?

大学时,学到网络协议的7层模型时,老师教了大家一个顺口溜:物数网传会表应。并说这是重点,年年必考,5分的题目摆在这里,你们爱背不背。 考试的时候,果然遇到这个问题,搜索枯肠,只能想...

Java干货分享
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部