hash和hash tree

简介: hash和hash tree

在理想情况下,我们希望不经过任何比较,一次存取便能得到所查的记录,那就必须在记的存储位置和它的关键字之间建立一个确定的对应关系,使每个关键字和一个唯一的存储位置对应,因而在查找时候,根据这个对应关系与找到对应的值K的像f(K).由此,不需要进行比较便可以直接取得所查结果。在此,我们称这个对应关系是hash函数,按这个思想建立的表为hash表。

在hash表中,对于不同的关键字可能得到同一个hash地址,这种现象称为冲突。

hash tree算法就是要提供一种在理论上和实际应用中都可以有效的处理冲突的方式,一般的hash算法都是O(1)的,而且基本是以空间换区时间。这很容易导致对存储空间的无限制的需求。

理论基础:n个不同的质数可以分辨连续整数的个数和他们的乘机相等。

利用质数分辨法建立哈希表:从2开始到n个质数建立n层hashtree 对质数进行取余决定了处理路径,结点中有一标志位标注这个结点是否有效。

优点:1、结构简单。2、查找迅速,查找次数和元素个数无关,仅与层数有关。3、结构不变,删除时,仅仅改变标志位,不做物理删除。

缺点:非排序性,hash tree不支持排序,没有顺序特性。

相关文章
|
5月前
|
存储 缓存 搜索推荐
Hash Table
【6月更文挑战第12天】
30 1
|
6月前
|
Shell
|
存储 算法 安全
Hash 算法详细介绍与实现 (二)
书接上回,昨天写了第一部分,《Hash 算法详细介绍与实现 (一)》详细介绍了Hash表和Hash算法的相关概念以及算法的基本原理。同时简单介绍几种hash算法的实现:直接取余法和乘法取整法;本文接着详细唠唠Hash算法和Hash表这个数据结构的具体实现以及Hash算法和Hash表常见问题的解决方案,比如解决Hash表的冲突问题等等.相关的理论知识已在上篇文章详细介绍,这里就不再赘述,多的不说少的不唠,直接进入今天的主题:利用Hash算法实现Hash表
477 1
|
存储 算法
hash
一.什么是hash 百度百科上的定义是: 是把任意长度的输入通过散列算法变换成固定长度的输出,该输出就是散列值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
102 0
|
前端开发 JavaScript
hash、chunkhash和contenthash
webpack 通用配置优化
125 0
hash、chunkhash和contenthash
|
存储 算法 安全
什么是 Hash 算法?
散列算法(Hash Algorithm),又称哈希算法,杂凑算法,是一种从任意文件中创造小的数字「指纹」的方法。与指纹一样,散列算法就是一种以较短的信息来保证文件唯一性的标志,这种标志与文件的每一个字节都相关,而且难以找到逆向规律。因此,当原有文件发生改变时,其标志值也会发生改变,从而告诉文件使用者当前的文件已经不是你所需求的文件。
什么是 Hash 算法?
|
存储 算法
Hash 算法有哪些?
Hash 算法有哪些?
197 0
Hash 算法有哪些?
|
存储 NoSQL 关系型数据库
B-Tree和哈希索引比较
MySQL B-tree hash 哈希 索引 InnoDB
125 0
|
存储 编译器
查找——HASH
查找——HASH
242 0
查找——HASH