哈希表入门 | JianLinker Blog

哈希表入门

发表于 | 分类于 ， | 评论数： | 热度： ℃

哈希表是一种以键值对来组织数据的数据结构，它需要哈希函数，用来支持快速地插入和搜索数据。

哈希表的原理

哈希表的关键是通过哈希函数，将键( key )映射到存储桶(Bucket)：

\1. 当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；

\2. 当我们想要搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索。

设计哈希表的关键

哈希函数

哈希函数是哈希表中最重要的组件，该哈希表用于将键映射到特定的桶。

哈希函数（散列函数）取决于键值的范围和桶的数量。

可以看一下哈希函数的示例：

img

设计哈希函数的思想是尽可能将键分配到桶中，理想情况下，完美的哈希函数将是键和桶之间的一对一映射，然而很多时候是没办法达到完美的，只能在桶的数量和桶的容量之间做出权衡。

冲突解决

在大多数情况下，冲突几乎是不可避免的。

假设我们用 y = x ％ 5 作为哈希函数，1987 和 2 都分配给了桶 2，这是一个冲突。

冲突解决算法应该解决以下几个问题：

\1. 如何组织在同一个桶中的值？

\2. 如果为同一个桶分配了太多的值，该怎么办？

\3. 如何在特定的桶中搜索目标值？

这些问题都跟桶的容量和可能映射到同一个桶的键的数量有关。

一般来说，假设一个桶的最大存储键的数量为 n ，如果这个 n 是常数或者比较小，可以直接用一个数组来代表桶，如果这个 n 是可变或很大，我们就需要用到高度平衡的二叉树来做了。

img

通过代码理解哈希表

no code no talk. 了解了哈希的基本概念后，怎么也得去学一下用代码实现才能真正地理解吧。

下面就用 golang 来实现简单的 哈希集合 hashset 与 哈希映射 hashmap。要知道，哈希表中插入和搜索是最基本的操作了，实现中也是主要包含这些部分。

建议看到要求后，自己想一想该怎么实现比较好，用自己擅长的语言即可。

设计哈希集合

要求：

不使用任何内建的哈希表库设计一个哈希集合

具体地说，你的设计应该包含以下的功能

  • add(value)：向哈希集合中插入一个值。
  • contains(value) ：返回哈希集合中是否存在这个值。
  • remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
> MyHashSet hashSet = new MyHashSet();
> 
> hashSet.add(1);         
> 
> hashSet.add(2);         
> 
> hashSet.contains(1);    // 返回 true
> 
> hashSet.contains(3);    // 返回 false (未找到)
> 
> hashSet.add(2);          
> 
> hashSet.contains(2);    // 返回 true
> 
> hashSet.remove(2);          
> 
> hashSet.contains(2);    // 返回  false (已经被删除)
>

注意：

  • 所有的值都在 [1, 1000000]的范围内。
  • 操作的总数目在[1, 10000]范围内。
  • 不要使用内建的哈希集合库。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
type MyHashSet struct {

   table []bool 

}

/** Initialize your data structure here. */

func Constructor() MyHashSet {

  return MyHashSet{table:make([]bool,1000001)} 

}

func (this *MyHashSet) Add(key int)  {

   this.table[key] = true 

}

func (this *MyHashSet) Remove(key int)  {

   this.table[key] = false 

}

/** Returns true if this set contains the specified element */

func (this *MyHashSet) Contains(key int) bool {

  return this.table[key]

}

/**

 * Your MyHashSet object will be instantiated and called as such:

 * obj := Constructor();

 * obj.Add(key);

 * obj.Remove(key);

 * param_3 := obj.Contains(key);

 */

设计哈希映射

要求:

不使用任何内建的哈希表库设计一个哈希映射

具体地说，你的设计应该包含以下的功能

  • put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
  • get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。
  • remove(key)：如果映射中存在这个键，删除这个数值对。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
> MyHashMap hashMap = new MyHashMap();
> 
> hashMap.put(1, 1);          
> 
> hashMap.put(2, 2);         
> 
> hashMap.get(1);            // 返回 1
> 
> hashMap.get(3);            // 返回 -1 (未找到)
> 
> hashMap.put(2, 1);         // 更新已有的值
> 
> hashMap.get(2);            // 返回 1 
> 
> hashMap.remove(2);         // 删除键为2的数据
> 
> hashMap.get(2);            // 返回 -1 (未找到) 
>

注意：

  • 所有的值都在 [1, 1000000]的范围内。
  • 操作的总数目在[1, 10000]范围内。
  • 不要使用内建的哈希库。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
type KV struct {

    K int

    V int

}

type MyHashMap struct {

    data [1000][]KV

}

func hash(key int) int {

    return key%1000

}

/** Initialize your data structure here. */

func Constructor() MyHashMap {

    return MyHashMap{[1000][]KV{}}

}

/** value will always be non-negative. */

func (this *MyHashMap) Put(key int, value int)  {

    h := hash(key)

    bkt := this.data[h]

    insert := -1

    for i := 0; i < len(bkt); i++ {

        if bkt[i].K == key {

            bkt[i].V = value

            return

        }

        if bkt[i].K == -1 {

            insert = i

        }

    }

    if insert != -1 {

        bkt[insert].K = key

        bkt[insert].V = value

    } else {

        this.data[h] = append(bkt, KV{key, value})   

    }

}

/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */

func (this *MyHashMap) Get(key int) int {

    h := hash(key)

    bkt := this.data[h]

    for _, k := range bkt {

        if k.K == key {

            return k.V

        }

    }

    return -1

}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */

func (this *MyHashMap) Remove(key int)  {

    h := hash(key)

    bkt := this.data[h]

    for i := 0; i < len(bkt); i++ {

        if bkt[i].K == key {

            bkt[i].K = -1

            return

        }

    }

}

/**

 * Your MyHashMap object will be instantiated and called as such:

 * obj := Constructor();

 * obj.Put(key,value);

 * param_2 := obj.Get(key);

 * obj.Remove(key);

 */

以上代码借鉴于 leetcode

复杂度分析

空间复杂度

关于哈希表的空间复杂度，其实也比较明显了，也就是当有 M 个键的时候，那哈希表的空间复杂度也是 O(M) 。

时间复杂度

而时间复杂度呢，按照上面的说法，即跟桶的最大存储键值得大小有关，如果存储最大值是个常数，我们可以用数组来当桶，那插入和搜索的时间复杂度都是 O(1)。

如果在最坏的情况下，桶大小的最大值将为 N，也就是可变的，那我们就会用到高度平衡的二叉树作为桶。插入时时间复杂度为 O(1)，搜索时为 O(N)。

内置的哈希表原理

内置哈希表的典型设计是：

\1. 键值可以是任何可哈希化的类型。并且属于可哈希类型的值将具有hashcode 。此 hashcode 可以通过映射函数来获得存储区索引。

\2. 每个桶包含一个数组，用于在初始时将所有值存储在同一个桶中。

\3. 如果在同一个桶中有太多的值（会设置临界值进行判断），这些值将被保留在一个高度平衡的二叉树搜索树中。

这样设计带来的好处便是，插入和搜索的平均时间复杂度仍为 O(1)。

最坏情况下插入和搜索的时间复杂度是 O(logN)，使用高度平衡的 BST。很显然，这需要对这个临界值的设置有巧妙的处理。

今天就讲这么多啦，希望通过本篇的讲解，能让大家对哈希表的结构及原理有更深刻的认识，也十分欢迎大家能在评论区发表自己的看法哦

我是鱼卷少年，我们下次见。

JianLinker wechat
欢迎您扫一扫上面的微信公众号，订阅我的博客！