文档章节

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

liangwt
 liangwt
发布于 2016/09/29 20:14
字数 369
阅读 42
收藏 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
粉丝 2
博文 12
码字总数 8274
作品 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和HashTable

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

就是小灰灰
2017/07/17
0
0
HashMap 并发 Map 是什么 内部原理什么 存储方式 hashcode 扩容 默认容量等

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

宇你同在
07/08
0
0
哈希相关知识再学习

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

静默加载
2017/10/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java 并发编程原理

为什么要使用多线程? 通过多线程提高吞吐量 伸缩性比较好,可以增加 CPU 核心来提高程序性能 什么场景下使用多线程? 如:tomcat BIO Java 如何实现多线程? Thread、Runnable、ExecutorSer...

aelchao
15分钟前
0
0
谨慎的覆盖clone方法

说在前面 有些专家级程序员干脆从来不去覆盖clone方法,也从来不去调用它,除非拷贝数组。 其他方式 可以提供一个构造函数或者工厂去实现clone功能。 相比于clone,它们有如下优势: 不依赖于...

XuePeng77
16分钟前
0
0
什么是最适合云数据库的架构设计?

分布式数据库技术发展多年,但是在应用、业务的驱动下,分布式数据库的架构一直在不断发展和演进。 开源金融级分布式数据库SequoiaDB,经过6年的研发,坚持从零开始打造数据库核心引擎。在技...

巨杉数据库
25分钟前
0
0
源码模仿之RPC

源码模仿之RPC RPC - 远程过程调用,概念不多赘述,可自行百度。 场景 统一api接口 生产者(提供远程接口调用方) 使用者(主动调用远程接口) 代码实现 API接口(公共依赖包) DemoEntity (...

GMarshal
26分钟前
0
0
Linux之安装Tomcat8

最近要在Linux上安装Tomcat,记录下 1.进入tomcat8的安装目录 List-1 root@iZwz9bjiawhqzfsklyht4rZ bin]# pwd/opt/app/tomcat8/bin[root@iZwz9bjiawhqzfsklyht4rZ bin]# ll总用量 83......

克虏伯
26分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部