哈希表：数据结构与快速查找

88 浏览量更新于2024-07-14 收藏 316KB PDF 举报

"这篇资源是关于哈希表的讲解，出自Jeff Erickson的2014年算法课程，讨论了如何使用哈希表快速查找集合中的元素。引用了 Narcotics Anonymous 的名言来引出主题，并通过 Calvin 和 Hobbes 的对话来形象地展示了随机编码的概念。文中还提到了RFC1149.5标准和xkcd漫画的相关内容，以幽默的方式阐述哈希表的基础知识。" 哈希表是一种数据结构，它的主要功能是存储一组元素，以便我们能够迅速判断某个元素是否存在于这组元素中。核心思想是选择一个哈希函数h，该函数将每个可能的元素x映射到一个小整数h(x)。然后我们将x存储在数组的索引h(x)处，这个数组就是哈希表。为了更具体些，我们的目标是实现“常数时间复杂度”的查找操作。理想情况下，当我们在哈希表中查找、插入或删除元素时，这些操作应该具有O(1)的时间复杂度。这是通过良好的哈希函数设计来实现的，它尽可能地确保不同的元素被均匀地分布在整个哈希表中，避免冲突。哈希函数的设计至关重要。一个优秀的哈希函数应该具备以下特性： 1. **均匀性**：哈希函数应该将输入映射到哈希表的索引上，使得每个索引都有相同的可能性被选中。 2. **简单性**：哈希函数应当易于计算，以减少计算时间。 3. **抗冲突性**：尽管难以完全避免冲突，但哈希函数应尽量减少冲突发生的可能性。冲突处理是哈希表设计的另一个关键方面。常见的解决冲突的方法有： - **开放寻址法**：当发生冲突时，寻找下一个空的哈希槽，直到找到为止。 - **链地址法**：在每个哈希表索引位置存储一个链表，所有哈希到同一位置的元素都链接在这个链表上。 - **双重散列**：使用第二个哈希函数来确定在发生冲突时的偏移量。哈希表的性能还受到负载因子的影响，即已存储元素数量与哈希表大小的比例。当负载因子过高时，冲突的概率会增加，性能会下降。因此，通常会采用动态调整大小的策略，如当元素达到一定比例时扩大哈希表的容量。在实际应用中，哈希表广泛用于数据库索引、缓存系统、编程语言的字典结构等场景。例如，在Python中，字典就是一种内置的哈希表实现。理解并优化哈希表的性能对于提高软件系统的效率至关重要。

Algorithms Lecture 12: Hash Tables [Fa’13]

One property of ideal random hash functions that seems intuitively useful is

uniformity

. A

family

of hash functions is uniform if choosing a hash function uniformly at random from

makes every hash value equally likely for every item in the universe:

Uniform: Pr

h∈H



h(x) = i



for all x and all i

We emphasize that this condition must hold for every item

x ∈ U

and every index

. Only the

hash function h is random.

In fact, despite its intuitive appeal, uniformity is not terribly important or useful by itself.

Consider the f amily

of constant hash f unctions deﬁned as follows. For each integer

between

and

m −1

, let

const

denote the constant function

const

(x) = a

for all

, and let

K = {const

| 0 ≤ a ≤ m −1}

be the set of all such functions. It is easy to see that the set

both perfectly uniform and utterly useless!

A much more important goal is to minimi ze the number of collisions. A f amily of hash

functions is

universal

if, for any two items in the universe, the probability of collision is as small

as possible:

Universal: Pr

h∈H



h(x) = h( y)



for all x 6= y

(Trivially, if

x = y

, then

Pr[h(x) = h( y)] = 1

!) Again, we emphasize that this equation must hold

for every pair of distinct items; only the function

is random. The family of constant functions

is uniform but not universal; on the other hand, universal hash families are not necessarily

uniform.¹

Most elementary hashing analysis requires a weaker versions of universality. A family of hash

functions is near-universal if the probability of collision is close to ideal:

Near-universal: Pr

h∈H



h(x) = h( y)



≤

for all x 6= y

There’s nothing special about the number

in this deﬁnition; any other explicit constant will do.

On the other hand, some hashing analysis requires reasoning about larger sets of collisions.

For any integer

, we say that a family of hash functions is

strongly k -universal

k-uniform

for any sequence of

disjoint keys and any sequence of

hash values, the probability that each

key maps to the corresponding hash value is 1/m

k-uniform: Pr



j=1

h(x

) = i



for all distinct x

, . . . , x

and all i

, . . . , i

Ideal random hash functions are k-uniform for every positive integer k.

12.4 Chaining

One of the most common methods for resolving collisions in hash tables is called chaining. In a

chained hash table, each entry

T [i]

is not just a single item, but rather (a pointer to) a linked

list of all the items that hash to

T [i]

. Let

`(x)

denote the length of the list

T [h(x)]

. To see if

Confusingly, universality is often called the

uniform hashing assumption

, even though it is not an assumption

that the hash function is uniform.

剩余14页未读，继续阅读

weixin_38739837

粉丝: 2
资源: 912

哈希表：数据结构与快速查找

Matlab实现Hashin-Shtrikman界限代码解析

#S - Hash Scratch-crx插件：让Scratch教育更高效

64位HashTools压缩包下载-最新版HashTools-4.6

Concurrent Hash Tables - Fast and General - ACM - 2019 (3309206)-计算机科学

Cuckoo++ Hash Tables - High-Performance Hash Tables for Networking Applications - 2017 (1712.09624)-计算机科学

Concurrent Hash Tables - Fast and General - 2016 (1601.04017v2)-计算机科学

GNU libdbh - Disk based hashtables-开源

Ideal Hash Trees - Phil Bagwell - ACM-计算机科学

hash-tables-app:简单的React App可显示哈希表的行为和性能

google-hash-2014

最新资源