# 哈希表

哈希表是一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。

有两种不同类型的哈希表：哈希集合和哈希映射。

哈希集合是集合数据结构的实现之一，用于存储非重复值。
哈希映射是映射数据结构的实现之一，用于存储(key, value)键值对。

在标准模板库的帮助下，哈希表是易于使用的。大多数常见语言（如 Java，C ++ 和 Python）都支持哈希集合和哈希映射。

# 哈希表的原理

正如我们在介绍中提到的，哈希表是一种数据结构，它使用哈希函数组织数据，以支持快速插入和搜索。在本文中，我们将简要说明哈希表的原理。

哈希表的关键思想是使用哈希函数将键映射到存储桶。更确切地说

当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；
当我们想要搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索。

在示例中，我们使用 y = x ％ 5 作为哈希函数。让我们使用这个例子来完成插入和搜索策略：

插入：我们通过哈希函数解析键，将它们映射到相应的桶中。
- 例如，1987 分配给桶 2，而 24 分配给桶 4。
搜索：我们通过相同的哈希函数解析键，并仅在特定存储桶中搜索。
- 如果我们搜索 1987，我们将使用相同的哈希函数将 1987 映射到 2。因此我们在桶 2 中搜索，我们在那个桶中成功找到了 1987。
- 例如，如果我们搜索 23，将映射 23 到 3，并在桶 3 中搜索。我们发现 23 不在桶 3 中，这意味着 23 不在哈希表中。

# 设计哈希表的关键

在设计哈希表时，你应该注意两个基本因素。

# 哈希函数

哈希函数是哈希表中最重要的组件，该哈希表用于将键映射到特定的桶。在上文中的示例中，我们使用y = x % 5作为散列函数，其中 x 是键值，y 是分配的桶的索引。

散列函数将取决于键值的范围和桶的数量。

下面是一些哈希函数的示例：

哈希函数的设计是一个开放的问题。其思想是尽可能将键分配到桶中，理想情况下，完美的哈希函数将是键和桶之间的一对一映射。然而，在大多数情况下，哈希函数并不完美，它需要在桶的数量和桶的容量之间进行权衡。

# 冲突解决

理想情况下，如果我们的哈希函数是完美的一对一映射，我们将不需要处理冲突。不幸的是，在大多数情况下，冲突几乎是不可避免的。例如，在我们之前的哈希函数（y = x ％ 5）中，1987 和 2 都分配给了桶 2，这是一个冲突。

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

如何组织在同一个桶中的值？
如果为同一个桶分配了太多的值，该怎么办？
如何在特定的桶中搜索目标值？

根据我们的哈希函数，这些问题与桶的容量和可能映射到同一个桶的键的数目有关。

让我们假设存储最大键数的桶有 N 个键。

通常，如果 N 是常数且很小，我们可以简单地使用一个数组将键存储在同一个桶中。如果 N 是可变的或很大，我们可能需要使用高度平衡的二叉树来代替。

插入和搜索是哈希表中的两个基本操作。

此外，还有基于这两个操作的操作。例如，当我们删除元素时，我们将首先搜索元素，然后在元素存在的情况下从相应位置移除元素。

# 设计哈希集合

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

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

add(value)：向哈希集合中插入一个值。
has(value) ：返回哈希集合中是否存在这个值。
delete(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
clear()：清空所有成员，没有返回值

示例：

var hashSet = new HashSet();
hashSet.add(1);
hashSet.add(2);
hashSet.has(1); // 返回 true
hashSet.has(3); // 返回 false (未找到)
hashSet.add(2);
hashSet.has(2); // 返回 true
hashSet.delete(2);
hashSet.has(2); // 返回  false (已经被删除)

1
2
3
4
5
6
7
8
9

数组模拟哈希集合

var HashSet = function() {
  this.items = [];
  this.size = 0;
};

HashSet.prototype.add = function(value) {
  if (this.items.indexOf(value) < 0) {
    this.items.push(value);
    this.size++;
  }
};

HashSet.prototype.has = function(value) {
  return this.items.indexOf(value) > -1;
};

HashSet.prototype.delete = function(value) {
  var pos = this.items.indexOf(value);
  if (pos > -1) {
    this.items.splice(pos, 1);
    return true;
  } else {
    return false;
  }
};

HashSet.prototype.clear = function() {
  this.items.length = 0;
  this.size = 0;
};

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

# 设计哈希映射

应该包含以下的功能

size：属性，size 属性返回 Map 结构的成员总数。
set(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
get(key)：get 方法读取 key 对应的键值，如果找不到 key，返回 undefined。
has(key) ：has 方法返回一个布尔值，表示某个键是否在当前 Map 对象之中。
delete(key)：delete 方法删除某个键，返回 true。如果删除失败，返回 false。
clear()：清空所有成员，没有返回值

示例

var hashMap = new HashMap();
hashMap.set(1, 1);
hashMap.set(2, 2);
hashMap.get(1); // 返回 1
hashMap.get(3); // 返回 undefined (未找到)
hashMap.set(2, 1); // 更新已有的值
hashMap.get(2); // 返回 1
hashMap.delete(2); // 删除键为2的数据，true
hashMap.get(2); // 返回 undefined (未找到)

1
2
3
4
5
6
7
8
9

var HashMap = function() {
  this.values = [];
  this.keys = [];
  this.size = 0;
};

HashMap.prototype.set = function(key, value) {
  var pos = this.keys.indexOf(key);
  if (pos > -1) {
    this.values[pos] = value;
  } else {
    this.keys.push(key);
    this.values.push(value);
    this.size++;
  }
};

HashMap.prototype.get = function(key) {
  var pos = this.keys.indexOf(key);
  if (pos > -1) {
    return this.values[pos];
  }
};

HashMap.prototype.delete = function(key) {
  var pos = this.keys.indexOf(key);
  if (pos > -1) {
    this.keys.splice(pos, 1);
    this.values.splice(pos, 1);
    this.size--;
    return true;
  } else {
    return false;
  }
};

HashMap.prototype.has = function(key) {
  return this.keys.indexOf(key) > -1;
};

HashMap.prototype.clear = function() {
  this.keys.length = 0;
  this.values.length = 0;
  this.size = 0;
};

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

← 链表二叉树 →