专栏首页互联网技术杂谈朝花夕拾-哈希表(hashTable)
原创

朝花夕拾-哈希表(hashTable)

复习一下常见的数据结构与算法

一、走进哈希表(hashTable)

1.哈希表的目的

实现数据的快速查找

2.哈希表的设计原理

image.png

二、哈希表的设计要素

  • 哈希函数-hash function
  • 冲突解决方案-collision solution
  • 重哈希-rehashing

1.哈希函数-hash function

基本概念

一个哈希函数需要具备如下特征:

  • 确定性
  • 不可逆

其输入为: 任意二进制数据,输出为:整数(Buckets的位置)

优秀的哈希函数

如何评价一个哈希函数是否优秀了?这里我们主要看:

  • 尽可能少的发生碰撞
  • 计算复杂度不要太高

常见的哈希函数包括:

  • 除余法modulo division
  • 平方取中法 mid square
  • 基数转换法 radix transformation

Java中字符串的hash函数

实现逻辑:

for(char c : str){
    hashCode = 31 * hashCode + c;
}

所以在Aa,BB、Ab,BC时会出现碰撞。通过如下测试代码可以发现,他们的hashCode是相同的。

 System.out.println("Aa".hashCode());
 System.out.println("BB".hashCode());

2.冲突解决方案-collision solution

开散列

open hashing, 又称拉链法 separate chaining

一言以蔽之,每个Bucket放的都是一个链表头结点的引用,假如冲突了就在这个链表后面加一个结点即可。(链表,往下拉)

闭散列

closed hashing,又称开址法 open addressing

当前位置已有其他元素后,再通过新算法为其找新的位置,(如这个位置的下一个空位).

(有哪些常见的查找新位置的算法呢?线性探查,待补充!)

3.重哈希-rehashing

哈希表扩缩容时,需要对已有数据的位置进行重新编排,这个就是常说的重哈希。

负载因子

负载因子load factor,等于哈希表元素的个数/哈希表容量,用于描述哈希表当前的负载。

一般当负载因子大于0.5的时候,检索性能急剧下降,冲突概率变高,此时一般就要进行哈希表扩容与重哈希了。

重哈希的描述

  • 调整哈希表的大小,并将元素重新摆放。
  • 当哈希表过于稀疏,进行重哈希可以节省空间
  • 当哈希表过于稠密,进行哈希可以加速查找( 空间换时间)

三、简易实现

四、参考资料

九章算法

算法导论

MIT-算法导论课程

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • mac下制作windows10的安装镜像

    在瓜大的时候曾经在计算机志愿者服务队做过志愿者,帮助很多人安装过各种各样的系统。毕业后很长一段时间,因为各种原因就没有自己装过新的操作系统(比如mac系统很稳定...

    皮皮熊
  • 【kafka源码】kafka内部的一些术语

    自己阅读kafka源码时的一些记录,更多内容见: https://github.com/pierre94/kafka-notes/blob/master/kaf...

    皮皮熊
  • 【HBase】HBase迷你版MiniBase学习笔记

    HBase相对复杂,想要快速啃下来比较困难。而MiniBase吸收了HBase最核心的引擎部分的精华,希望可以通过学习MiniBase以小见大,能够对自己理解H...

    皮皮熊
  • 图像检索:基于内容的图像检索技术(四)

    基于树结构的最近邻搜索方法和基于哈希的最近邻搜索方法在理论计算机科学、机器学习以及计算机视觉中是一个很活跃的领域,这些方法通过将特征空间划分成很多小的单元,以此...

    用户3578099
  • 哈希表的理论知识

    哈希表又称散列表,若要存储的元素个数为n,设置一个长度为m(m >= n)的连续内存单元,以每个元素的关键字为自变量,通过一个称为哈希的函数把关键字映射为内存单...

    晚上没宵夜
  • AI综述专栏| 大数据近似最近邻搜索哈希方法综述(上)(附PDF下载)

    在科学研究中,从方法论上来讲,都应先见森林,再见树木。当前,人工智能科技迅猛发展,万木争荣,更应系统梳理脉络。为此,我们特别精选国内外优秀的综述论文,开辟“综述...

    马上科普尚尚
  • 哈希

    我们知道,通过对数组进行直接寻址(Direct Addressing),可以在 O(1) 时间内访问数组中的任意元素。所以,如果存储空间允许,可以提供一个...

    对弈
  • 哈希算法的设计要点及应用场景

    大家好,我是多选参数的程序锅,一个正在 neng 操作系统、学数据结构和算法以及 Java 的硬核菜鸡。本篇主要介绍了哈希算法相关的内容,包括什么是哈希算法、哈...

    syy
  • 浅谈哈希表

    哈希表是一种根据哈希键去寻找哈希值的数据映射结构。通过该结构找到哈希键映射的位置,再根据映射的位置去寻找存放哈希值的地方。

    小蜜蜂
  • LeetCode | 你不得不了解的哈希算法 !

    问大家一个问题 。如果手机上存储了 1000 个联系人 ,现在要你给小詹打个电话 ,跟他说 ,他老婆喊他回家吃饭 。你会怎么做 ?

    小小詹同学

扫码关注云+社区

领取腾讯云代金券