微信号:JoneTalk

介绍:热爱生活,分享感悟;研究技术,共同成长.

浅谈哈希表

2017-05-22 08:04 小飞

哈希表是一种 key-value 存储数据的结构,根据待查找的 key,在表中查找关联的 value,如果不存在则返回空。它底层是基于数组实现的,根据 key 求得哈希值,但是哈希值可能非常大,如果直接作为数组的下标会造成空间的浪费,所以需要预设表的大小,将 key 的哈希值对表的大小取模,再存入表中。

在 Swift 中像 Dictionary 中的 key 就需要实现 Hashable 协议。

1

2

3

4

5

6

7

8

public protocol Hashable : Equatable {

/// The hash value.

///

/// Hash values are not guaranteed to be equal across different executions of

/// your program. Do not save hash values to use during a future execution.

public var hashValue: Int { get }

}

本文涵盖的内容:

  • 哈希表的结构

  • 哈希值是如何计算的

  • 如何解决哈希冲突

  • 重哈希对表性能的影响




哈希表的结构

哈希表实际上是一个数组,放置每个元素的位置被称为槽位(bucket),待存放的数据称为实体(entity)。举一个实体是链式结构的例子:

1

2

3

4

5

typedef struct node {

char *key;

char *value;

struct node *next;

} Node;

该结构体表示链表的一个节点,当槽位为空时,将节点存入槽位,如果当前位置被占用,就将节点插入表头。

下图是一个简单的哈希表,假设表只能存 6 个元素,那么根据 key 求得的 hash 必须取模映射到 [0, 5] 的区间内。第二个插图是存入 gender 发生冲突的处理。

在实际使用中,哈希表需要设定一个合适的大小。如果太大会造成空间的浪费;太小又容易造成哈希冲突,这会在后面讲到,同时如果槽位使用率到一定规模之后,会触发扩容,也是就重哈希,频繁的扩容也会影响表的性能。

哈希表中实体的数量除以槽位的数量叫做负载因子(load factor),随着负载因子的变大,哈希表会变得更慢甚至停止工作,所以一般在负载因子大于某一个值的时候,哈希表会自动扩容。

因为数组的存储的效率是 O(1),所以在理想情况下哈希表的存储效率也是 O(1),但哈希表的效率会受到哈希冲突以及重哈希的影响。

哈希函数

哈希函数是体现哈希表性能的关键。在上面的图中将字典的 key 转化成哈希值的函数,就叫做哈希函数。哈希函数要做到生成的哈希值尽可能的均匀分布。举一个简单的例子 f(x) = kx + b, x 为键值,f(x) 为哈希值,像这样的哈希函数就是均匀分布的。但实际设计中并不会这么简单,通常会进行多次的掩码以及位运算。

实际中,我们的键值并不都是数字,有可能是字符串,所以需要我们实现自己的哈希函数。

哈希冲突

即使再完美的哈希函数,都无法避免的会引起哈希冲突。引起冲突的原因是两个不相同的 key,经过哈希函数运算,得到相同的哈希值。处理哈希冲突已经有比较成熟的方案,常见的有链式存储法开发寻址法

链式存储法,就是前面插图所使用的方式,存储元素以链表的形式保存,如果当前位置已经存在节点,则将后来的节点插入链表的头部,伪代码:

1

2

3

4

5

6

7

Node *newNode = malloc(sizeof(newNode));

if (!newNode) return NULL;

newNode -> key = key

newNode -> value = value

h = hashFucntion(key);

newNode -> next = table[h]

table[h] = newNode

开放寻址法,所有的元素都放在哈希表中,每一个表项中包含一个元素或者为空。当插入元素时,如果当前位置占用,便进行线性探测,直到寻找到一个空的位置来放置待插入的关键字。探测的方法有三种:线性探测,二次探测以及双重探测。

线性探测最为简单,如果探测到当前位置被占用,则自动往后移一个位置,如果还是被占用则继续向前,当探测到表的尾部还没有找到时,会跳转到表开始的位置继续开始探测。探测函数为:h(k,i) = (h’(k)+i)mod m,i=0,1,….,m-1。

但是如果是循环探测,一直没有找到空的位置,探测就不会停止,所以需要有一个探测结束的标记位,该位置被称为洞。

开放寻址法将产生哈希冲突的值散列到表中,如果我们用其中一个 key 去查找,如果确保找到的值是这个 key 对应的呢?将当前查找的 key 于哈希值查找到的 key 对比是否相同即可。

理想情况下哈希表的时间复杂度是 O(1),根据哈希表的实现原理,也不排除出现连续的哈希冲突,导致时间复杂度变为 O(N)。

Hashtable 是线程安全的,它在 HashMap 的基础上加锁同步机制。有兴趣的可以参考这里

重哈希

前面 Hashable 协议中对 hashValue 的注释注释,讲到不要保存哈希值来操作对象,是因为同一个对象在未来它的 key 的哈希值可能发生变化。这个变化的原因就是哈希表扩容,重哈希导致的。

触发重哈希有三种情况:
(1)当哈希表快要满了,比如槽位占用率达到 80%
(2)当插入一个元素失败时
(3)负载因子超过一定比例的时候,一般是 0.75 时,就应该重哈希

使用哪种方式触发重哈希要根据具体表结构的设计来定,比如链接法一个槽位可以存放多个实体,合适采用第三种方式。

一般哈希表在扩容的时候,哈希值都会发生变化,导致哈希表暂时的停止工作。而有些语言会同时使用两个哈希表,在扩容的时候使用另一个表,待扩容完成又迁移回第一个表,具体可以参考 Redis dict 的实现。

参考

散列表
深入理解哈希表
浅谈算法和数据结构:十一 哈希表

微信不支持外链,可阅读原文查看。

 
iOSTalk 更多文章 你担心失业吗? 如何提高选择能力 隐式动画 我的面试经历 学本身没有价值
猜您喜欢 交互设计不受追捧,产品经理就混不下去了? 情人节前一个需要普及的概念 你误解用户研究了吗? 感恩这一年支持过我的所有人——从今以后,人生无数可能 Docker Live时代 | 畅聊容器生态之线下系列-北京站