文档章节

哈希表与应用

不死的达芬奇
 不死的达芬奇
发布于 2016/12/21 22:56
字数 2326
阅读 92
收藏 2

一、哈希表

       哈希表是一种数据结构,它需要配合哈希函数使用,用于建立索引,便于快速查找。

       哈希表的实现一般来说就是一个定长的存储空间,每个位置存储一个对象。如果我们假设定长为N,则可以将这N个存储位置分别编号为0,1,...,N-1。那么现在的问题就是,如何决定一个元素应该放到哪个位置?如何查找一个元素在哪个位置?最常采用的策略如下:

       插入:使用哈希函数计算待插入对象的哈希值,如果哈希值是H,则插入编号为H mod N的位置。

       查找:使用哈希函数计算待查找对象的哈希值,如果哈希值是H,则检查编号为H mod N的位置。

       下面是一个例子,假设我们有4个字符串需要建立索引,这4个字符串及其对应的哈希值如下表所示:

字符串

哈希值

algorithm

1

mathematics

5

notes

9

book

15

 

       如果哈希表的长度为10,那么我们通常将其描述为下图。

       其中,mathematics和book两个字符串的哈希值模10的余数相同,因此放入同一位置。图中所采用的是所谓的链地址法,即用链表将冲突的多个对象存储在同一位置,这也是在哈希表中解决冲突时最常用的方法。

       当我们需要查找某个字符串是否在哈希表中时,只需计算其哈希值,然后到哈希表的对应位置检查,从而达到快速查找的目的。很容易看出,如果每个字符串都放在哈希表中的不同位置,则查找速度会更快。哈希函数冲突少的特点使得不同的字符串通常具有不同的哈希值。所以,一般来说,只要增大哈希表的长度,就可以避免将两个字符串放入同一位置的情况。

       确定哈希表的长度是一个重要的难题。一方面,长度太小可能会导致冲突多,查询速度慢;另一方面,长度太长可能会白白浪费存储空间。如果事先知道需要索引的对象数目,则可以设定比较合适的哈希表大小,但许多时候并不能事先得到这个消息。一个实用的技巧是动态调整哈希表的长度;在开始时,首先选用一个较小的哈希表,当发现其使用率,即存储的对象数目与哈希表大小的比值达到某个阈值时,就建立一个更大的哈希表并将之前的哈希表中的对象迁移过来。迁移哈希表的过程往往是非常费时的,因此,可以同时保留新旧两个哈希表,逐步迁移,分散计算量。在进行查找和删除操作时,同时检查新旧两个哈希表。在进行插入操作时,只针对新的哈希表。每进行一次插入操作时,我们同时将r个对象从旧哈希表迁移到新哈希表,其中,r是一个任意指定的常数。这个策略相当于每次从旧哈希表中删除r个对象,就同时在新哈希表中增加r+1个对象。因此,只要新哈希表的长度不小于旧哈希表长度的(r+1)/r倍,我们就可以在完全删除旧哈希表的时候,保证新哈希表的使用率没有超过旧哈希表。

二、哈希的应用

       1  相似性搜索

       哈希主要用于快速查找,而查找的对象需要是完全相同的。也就是说,一般只要求当两个对象完全相同时有相同的哈希值,而两个相似的对象的哈希值不需要有任何关系。但如果哈希函数设计得足够巧妙,也可以让相似的对象有相同或相似的哈希值,这样我们就可以借助哈希来进行相似性搜索

       局部敏感哈希(Local-Sensitive Hashing,LSH)就定义了一类可以衡量相似性的哈希函数,它要求相似对象的哈希值在某种意义下相似,并且有概率保证。用数学语言来描述,局部敏感哈希的定义为满足以下两个特性的哈希函数。

  • 如果d(x,y)<=d1,则P(hash(x)=hash(y))>=p1。也就是说,当两个对象的距离不大于d1时,它们的哈希值相同的概率要不小于p1。
  • 如果d(x,y)>=d2,则P(hash(x)=hash(y))<=p2。也就是说,当两个对象的距离不小于d2时,它们的哈希值相同的概率要不大于p2。

       其中,d(x,y)表示两个对象x和y之间的距离,hash(.)是哈希函数,P(.)是概率,d1、d2、p1、p2都是常数。对于不同的场景,对距离的定义可能是不同的,因此,哈希函数的设计也会很不一样。

       下面再来看一个用于文档相似性搜索的哈希函数:Simhash。Simhash可以将文档哈希到一个64位二进制数,使得相似的文档具有相似的二进制数。对于一个文档,我们可以把文中的每个词(也可以是词组等)作为一个特征,统计各个特征的出现频率。例如,我们统计文档“To be or not to be is a tough question”,其特征与相应的频率为:(to,0.2)、(be,0.2)、(or,0.1)、(not,0.1)、(is,0.1)、(a,0.1)、(tough,0.1)、(question,0.1)。然后,我们可以利用某个传统的哈希函数将特征映射到64位二进制。为了描述方便,我们只统计到6位二进制数,并假设映射结果是to:001100,be:100100,or:001010,not:101000,is:011100,a:100101,tough:100111,question:011011。根据二进制数的各个二进制位,我们对每个特征构造一个向量。如果一个特征映射到的二进制数的某一位是1,则其向量对应位置上的分量为该特征的频率,否则为频率的相反数。于是,各个特征对应的向量为

to:(-0.2,-0.2,0.2,0.2,-0.2,-0.2),

be:(0.2,-0.2,-0.2,0.2,-0.2,-0.2),

or:(-0.1,-0.1,0.1,-0.1,0.1,-0.1),

not:(0.1,-0.1,0.1,-0.1,-0.1,-0.1),

is:(-0.1,0.1,0.1,0.1,-0.1,-0.1),

a:(0.1,-0.1,-0.1,0.1,-0.1,-0.1),

tough:(0.1,-0.1,-0.1,0.1,0.1,0.1),

question:(-0.1,0.1,0.1,-0.1,0.1,0.1).

       将这些向量相加,就得到(0,-0.6,0.2,0.4,-0.4,-0.4)。对于这一向量的每个向量,如果大于0就取1,否则就取0,这样得到的二进制数就是Simhash的最终哈希值,即001100。可以想象,出现频率高的特征,其相应的向量分量的绝对值更大,对最终向量相加的结果的影响也更大。因此,如果两个文档相似,那么它们出现频率高的特征应该比较接近,最终得到的哈希值也就会有很多二进制位都是相同的。在查找相似文档的时候,我们只需要找到哈希值的各个二进制位区别很小的文档。一般来说,我们要求至多有3个二进制位不同。

       还有一类主要用于图片相似性搜索的哈希函数是感知哈希(Perceptual Hashing)。它是一类广泛使用的图片搜索算法,可以做到以图搜图。其思想主要是通过调整大小、灰度化和二值化三个步骤,将图片映射到一个二进制数,使得相似图片具有相近的二进制数。我们以图片处理中的经典图片Lenna为例进行说明。

       假设我们希望哈希值是64位二进制数,则我们首先将图片大小通过简单的缩放调整为8像素X8像素,这样就刚好有64个像素了。在调整图片大小得到的新图中,每个像素上的RGB值实质上是原图相应位置上的RGB平均值。然后,我们将原图灰度化。灰度化最常见的方式就是将每个像素上的灰度值取为RGB三个分量的平均值。

      将灰度化后的图像个各个像素点的灰度值可以写为矩阵

155   130   131   133   123   121   127   136 
106   102   108   100   100   86    69    60 
129   121   127   112   72    96    91    70 
138   162   146   85    120   88    77    108 
127   183   165   163   149   142   151   145 
145   123   184   125   95    79    137   178 
159   123   111   97    127   147   138   123 
89    85    148   155   166   200   134   90 

       最后一步是二值化。我们首先计算出64个像素点的灰度平均值为77.090,然后将小于平均值的像素点都取为0,其余像素点都取为1。将所有64个0或1连在一起,就得到了一个64位二进制串,也就是最终的哈希值:

1111111111111100111101101111110111111111111111111111111111111111

       这样我们只需对两个图片的哈希值进行逐位比较,就可以判定他们是否相似了。

 

© 著作权归作者所有

上一篇: Netty(四)
下一篇: Netty(三)
不死的达芬奇
粉丝 38
博文 43
码字总数 42018
作品 0
朝阳
后端工程师
私信 提问
Redis数据结构之字典

一 应用场景 字典在Redis中的应用相当广泛,比如Redis的数据库就是使用字典作为底层实现的,对数据库的增删该查也是构建在对字典的操作之上。 Redis的字典使用哈希表作为底层实现,一个哈希表...

挽袖清风
2018/01/26
19
0
【Redis基本数据结构】字典实现 rehash介绍

字典, 又称为符号表 关联数组或者映射,是一种保存键值对的抽象数据结构. 字典作为一种常用数据结构被内置在许多程序语言中,由于 C 语言没有内置这种数据结构, Redis 构建了自己的字典实现. 字...

xiaomin0322
2018/03/01
241
0
在C#中应用哈希表(Hashtable)

一,哈希表(Hashtable)简述 在.NET Framework中,Hashtable是System.Collections命名空间提供的一个容器,用于处理和表现类似key/value的键值对,其中key通常可用来快速查找,同时key是区分大...

晨曦之光
2012/03/09
77
0
LeetCode | 你不得不了解的哈希算法 !

⒈哈希是什么 ? 问大家一个问题 。如果手机上存储了 1000 个联系人 ,现在要你给小詹打个电话 ,跟他说 ,他老婆喊他回家吃饭 。你会怎么做 ? 当然是按姓名搜索呀 !(假装你有小詹电话号码...

技术小能手
2018/11/29
0
0
HAWQ技术解析(七) —— 存储分布

在HAWQ中创建一个表时,应该预先对数据如何分布、表的存储选项、数据导入导出方式和其它HAWQ特性做出选择,这些都将对数据库性能有极大影响。理解有效选项 的含义以及如何在数据库中使用它们...

wzy0623
2017/04/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud 笔记之Spring cloud config client

观察者模式它的数据的变化是被动的。 观察者模式在java中的实现: package com.hxq.springcloud.springcloudconfigclient;import org.springframework.context.ApplicationListener;i...

xiaoxiao_go
昨天
6
0
CentOS7.6中安装使用fcitx框架

内容目录 一、为什么要使用fcitx?二、安装fcitx框架三、安装搜狗输入法 一、为什么要使用fcitx? Gnome3桌面自带的输入法框架为ibus,而在使用ibus时会时不时出现卡顿无法输入的现象。 搜狗和...

技术训练营
昨天
5
0
《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
昨天
8
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
昨天
10
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部