文档章节

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

liangwt
 liangwt
发布于 2016/09/29 20:14
字数 369
阅读 56
收藏 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
08/16
0
0
hash分布式算法及冲突解决方案

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

吴之恒心
2017/02/24
0
0
HashMap 并发 Map 是什么 内部原理什么 存储方式 hashcode 扩容 默认容量等

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

宇你同在
07/08
0
0
Hashmap和HashTable

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

就是小灰灰
2017/07/17
0
0
哈希相关知识再学习

在平时工作和源码学习的过程中经常遇到哈希相关的问题,每次都会上网找资料回忆哈希相关的知识点。趁这机会记录下来,防止以后又忘记了!! 哈希表 根据关键字(Key value)至二级访问在内存...

静默加载
2017/10/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

高并发编程:解析HashMap

底层实现原理 在JDK1.8以前版本中,HashMap的实现是数组+链表,它的缺点是即使哈希函数选择的再好,也很难达到元素百分百均匀分布,而且当HashMap中有大量元素都存到同一个桶中时,这个桶会有...

小刀爱编程
26分钟前
0
0
程序员请不要假装很努力,因为结果不会陪你演戏

前言: 我一直相信这样一句话:真正的危机,来源于在正确的时间做不正确的事。没有在正确的时间,为下一步做出积累,这才是危机的根源。 比如,当你迈过了30岁这个坎,你的能力还局限于程序的...

Java干货分享
31分钟前
1
0
Fio随机读IOPS测试值可能偏大的原因分析

问题描述: 在使用fio进行虚拟机磁盘(Ceph的RBD,格式化为ext4文件系统)的IOPS测试时,发现randread比预估值高许多; 在使用相同参数进行randwrite测试之后,再进行randread时会出现此现象...

LastRitter
35分钟前
1
0
JavaScript引用类型Object常见用法实例分析

1、JavaScript数据类型 (1)基本类型 5种基本类型:Undefined、Null、Boolean、Number、String (2)引用类型 5种引用类型:Object、Array、Date、RepExp、Function (3)基本类型与引用类型的异同...

peakedness丶
42分钟前
0
0
教你理清SpringBoot与SpringMVC的关系

spring boot就是一个大框架里面包含了许许多多的东西,其中spring就是最核心的内容之一,当然就包含spring mvc。spring mvc 是只是spring 处理web层请求的一个模块。因此他们的关系大概就是这...

别打我会飞
47分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部