哈希表的原理

---

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

哈希表的原理

---

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

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

示例

---

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

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

设计哈希表的关键

---

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

1. 哈希函数

---

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

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

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

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

2. 冲突解决

---

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

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

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

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

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

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

设计哈希集合

单独链表法

哈希函数的共同特点是使用模运算符。$\text{hash} = \text{value} \mod \text{base}$。其中，base 将决定 HashSet 中的桶数。

从理论上讲，桶越多（因此空间会越大）越不太可能发生碰撞。base 的选择是空间和碰撞之间的权衡。

此外，使用质数作为base 是一个明智的选择。例如 769，可以减少潜在的碰撞。

对于桶的设计，我们有几种选择，可以使用数组来存储桶的所有值。然而数组的一个缺点是需要O(N) 的时间复杂度进行插入和删除，而不是O(1)。

因为任何的更新操作，我们首先是需要扫描整个桶为了避免重复。选择链表来存储桶的所有值是更好的选择，插入和删除具有常数的时间复杂度。

算法：

正如我们在上面讨论的，这里将采用 LinkedList 实现 HashSet 中的桶。

对于每个功能 add，remove，contains，我们首先生成桶的散列值，操作相对应的桶。

class MyHashSet {private int bucket = 769;private Node[] array;/** Initialize your data structure here. */public MyHashSet() {this.array = new Node[bucket];}public void add(int key) {int index = hash(key);if(array[index] == null){array[index] = new Node();}array[index].add(key);}private int hash(int key){return key % bucket;}public void remove(int key) {int index = hash(key);if(array[index] != null){array[index].remove(key);}}/** Returns true if this set contains the specified element */public boolean contains(int key) {int index = hash(key);if(array[index] != null){return  array[index].contains(key);}return false;}class Node{private LinkedList<Integer> linkedList;public Node(){this.linkedList = new LinkedList();;}private void add(int key){if(!linkedList.contains(key)){linkedList.add(key);}}//注意这边需要传入一个Integer,这是因为LinkedList有两个方法 remove(int) 是根据下标删除//remove(Integer) 是删除指定的元素private void remove(Integer key){linkedList.remove(key);}private boolean contains(int key){return linkedList.contains(key);}}
}/*** Your MyHashSet object will be instantiated and called as such:* MyHashSet obj = new MyHashSet();* obj.add(key);* obj.remove(key);* boolean param_3 = obj.contains(key);*/

设计哈希映射

Java静态数组+单链表

考虑到本题目所设计的哈希表存储的键值对都是正整数，完全可以只使用Java的静态数组实现，但是实测时间和空间效率都不是很高。在静态数组的基础上添加单链表可以在较高的效率下实现，并且最终代码量并不大。

实现原理：

图中显示了存储[1=1, 2=5, 10001=1]三个键值对的哈希表，hash函数计算的哈希值作为数组的索引，数组中存储链表的虚拟头节点，当出现哈希冲突时，在链表后挂接新的节点。这样在操作哈希表时只需要判断对应hash地址是否为null，如果是null则创建虚拟头和链表头，如果已经有虚拟头则进行链表操作。使用虚拟头节点可以很方便地简化对链表的增删改操作。

• hash函数：int hash = key % N; N为静态数组的长度，本程序设为10000
• 底层数组：Node[] data = new Node[N];
• 链表节点：每个节点中存储一个键值对，操作时保证需要键唯一

 private class Node {int key;//key唯一int value;Node next;Node(int key, int value) {this.key = key;this.value = value;}}

• 代码：

• class MyHashMap {private final int N = 10000;//静态数组长度10000private Node[] data;/*** Initialize your data structure here.*/public MyHashMap() {data = new Node[N];}/*** value will always be non-negative.*/public void put(int key, int value) {int hash = hash(key);if (data[hash] == null) {//该hash地址没有链表节点data[hash] = new Node(-1, -1);//先存虚拟头data[hash].next = new Node(key, value);//再存实际头节点} else {Node prev = data[hash];//从虚拟头开始遍历while (prev.next != null) {if (prev.next.key == key) {prev.next.value = value;//有键，更新值return;}prev = prev.next;}prev.next = new Node(key, value);//没有键，添加节点}}/*** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key*/public int get(int key) {int hash = hash(key);if (data[hash] != null) {Node cur = data[hash].next;//从实际头节点开始寻找while (cur != null) {if (cur.key == key) {return cur.value;//找到}cur = cur.next;}}return -1;//没有找到}/*** Removes the mapping of the specified value key if this map contains a mapping for the key*/public void remove(int key) {int hash = hash(key);if (data[hash] != null) {Node prev = data[hash];while (prev.next != null) {//删除节点if (prev.next.key == key) {Node delNode = prev.next;prev.next = delNode.next;delNode.next = null;return;}prev = prev.next;}}}//哈希函数private int hash(int key) {return key % N;}//链表节点private class Node {int key;//key唯一int value;Node next;Node(int key, int value) {this.key = key;this.value = value;}}}
  

复杂度分析 - 哈希表

复杂度分析

---

如果总共有 M 个键，那么在使用哈希表时，可以很容易地达到 O(M) 的空间复杂度。

但是，你可能已经注意到哈希表的时间复杂度与设计有很强的关系。

我们中的大多数人可能已经在每个桶中使用数组来将值存储在同一个桶中，理想情况下，桶的大小足够小时，可以看作是一个常数。插入和搜索的时间复杂度都是 O(1)。

但在最坏的情况下，桶大小的最大值将为 N。插入时时间复杂度为 O(1)，搜索时为 O(N)。

内置哈希表的原理

---

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

1. 键值可以是任何可哈希化的类型。并且属于可哈希类型的值将具有哈希码。此哈希码将用于映射函数以获取存储区索引。
2. 每个桶包含一个数组，用于在初始时将所有值存储在同一个桶中。
3. 如果在同一个桶中有太多的值，这些值将被保留在一个高度平衡的二叉树搜索树中。

插入和搜索的平均时间复杂度仍为 O(1)。最坏情况下插入和搜索的时间复杂度是 O(logN)，使用高度平衡的 BST。这是在插入和搜索之间的一种权衡。

哈希集 - 用法

---

哈希集是集合的实现之一，它是一种存储不重复值的数据结构。

我们提供了在 Java，C++ 和 Python 中使用哈希集的示例。 如果你不熟悉哈希集的用法，那么通过这一示例将会很有帮助。

java

// "static void main" must be defined in a public class.
public class Main {public static void main(String[] args) {// 1. initialize the hash setSet<Integer> hashSet = new HashSet<>();     // 2. add a new keyhashSet.add(3);hashSet.add(2);hashSet.add(1);// 3. remove the keyhashSet.remove(2);        // 4. check if the key is in the hash setif (!hashSet.contains(2)) {System.out.println("Key 2 is not in the hash set.");}// 5. get the size of the hash setSystem.out.println("The size of has set is: " + hashSet.size());     // 6. iterate the hash setfor (Integer i : hashSet) {System.out.print(i + " ");}System.out.println("are in the hash set.");// 7. clear the hash sethashSet.clear();// 8. check if the hash set is emptyif (hashSet.isEmpty()) {System.out.println("hash set is empty now!");}}
}

c++

#include <unordered_set>                // 0. include the libraryint main() {// 1. initialize a hash setunordered_set<int> hashset;   // 2. insert a new keyhashset.insert(3);hashset.insert(2);hashset.insert(1);// 3. delete a keyhashset.erase(2);// 4. check if the key is in the hash setif (hashset.count(2) <= 0) {cout << "Key 2 is not in the hash set." << endl;}// 5. get the size of the hash setcout << "The size of hash set is: " << hashset.size() << endl; // 6. iterate the hash setfor (auto it = hashset.begin(); it != hashset.end(); ++it) {cout << (*it) << " ";}cout << "are in the hash set." << endl;// 7. clear the hash sethashset.clear();// 8. check if the hash set is emptyif (hashset.empty()) {cout << "hash set is empty now!" << endl;}
}

python

# 1. initialize the hash set
hashset = set() 
# 2. add a new key
hashset.add(3)
hashset.add(2)
hashset.add(1)
# 3. remove a key
hashset.remove(2)
# 4. check if the key is in the hash set
if (2 not in hashset):print("Key 2 is not in the hash set.")
# 5. get the size of the hash set
print("Size of hashset is:", len(hashset)) 
# 6. iterate the hash set
for x in hashset:print(x, end=" ")
print("are in the hash set.")
# 7. clear the hash set
hashset.clear()                         
print("Size of hashset:", len(hashset))

使用哈希集查重

---

我们知道，插入新值并检查值是否在哈希集中是简单有效的。

因此，通常，使用哈希集来检查该值是否已经出现过。

示例

---

让我们来看一个例子：

给定一个整数数组，查找数组是否包含任何重复项。

这是一个典型的问题，可以通过哈希集来解决。

你可以简单地迭代每个值并将值插入集合中。 如果值已经在哈希集中，则存在重复。

模板

---

在这里，我们为你提供了解决此类问题的模板：

/** Template for using hash set to find duplicates.*/
boolean findDuplicates(List<Type>& keys) {// Replace Type with actual type of your keySet<Type> hashset = new HashSet<>();for (Type key : keys) {if (hashset.contains(key)) {return true;}hashset.add(key);}return false;
}

哈希映射 - 用法

---

哈希映射是用于存储 (key, value) 键值对的一种实现。

我们提供了一个在 Java、C++ 和 Python 中使用哈希映射的示例。如果您还不熟悉哈希映射的用法，那么浏览一下这个示例将很有帮助。

c++

#include <unordered_map>                // 0. include the libraryint main() {// 1. initialize a hash mapunordered_map<int, int> hashmap;// 2. insert a new (key, value) pairhashmap.insert(make_pair(0, 0));hashmap.insert(make_pair(2, 3));// 3. insert a new (key, value) pair or update the value of existed keyhashmap[1] = 1;hashmap[1] = 2;// 4. get the value of a specific keycout << "The value of key 1 is: " << hashmap[1] << endl;// 5. delete a keyhashmap.erase(2);// 6. check if a key is in the hash mapif (hashmap.count(2) <= 0) {cout << "Key 2 is not in the hash map." << endl;}// 7. get the size of the hash mapcout << "the size of hash map is: " << hashmap.size() << endl; // 8. iterate the hash mapfor (auto it = hashmap.begin(); it != hashmap.end(); ++it) {cout << "(" << it->first << "," << it->second << ") ";}cout << "are in the hash map." << endl;// 9. clear the hash maphashmap.clear();// 10. check if the hash map is emptyif (hashmap.empty()) {cout << "hash map is empty now!" << endl;}
}

java

// "static void main" must be defined in a public class.
public class Main {public static void main(String[] args) {// 1. initialize a hash mapMap<Integer, Integer> hashmap = new HashMap<>();// 2. insert a new (key, value) pairhashmap.putIfAbsent(0, 0);hashmap.putIfAbsent(2, 3);// 3. insert a new (key, value) pair or update the value of existed keyhashmap.put(1, 1);hashmap.put(1, 2);// 4. get the value of specific keySystem.out.println("The value of key 1 is: " + hashmap.get(1));// 5. delete a keyhashmap.remove(2);// 6. check if a key is in the hash mapif (!hashmap.containsKey(2)) {System.out.println("Key 2 is not in the hash map.");}// 7. get the size of the hash mapSystem.out.println("The size of hash map is: " + hashmap.size()); // 8. iterate the hash mapfor (Map.Entry<Integer, Integer> entry : hashmap.entrySet()) {System.out.print("(" + entry.getKey() + "," + entry.getValue() + ") ");}System.out.println("are in the hash map.");// 9. clear the hash maphashmap.clear();// 10. check if the hash map is emptyif (hashmap.isEmpty()) {System.out.println("hash map is empty now!");}}
}

python

# 1. initialize a hash map
hashmap = {0 : 0, 2 : 3}
# 2. insert a new (key, value) pair or update the value of existed key
hashmap[1] = 1
hashmap[1] = 2
# 3. get the value of a key
print("The value of key 1 is: " + str(hashmap[1]))
# 4. delete a key
del hashmap[2]
# 5. check if a key is in the hash map
if 2 not in hashmap:print("Key 2 is not in the hash map.")
# 6. both key and value can have different type in a hash map
hashmap["pi"] = 3.1415
# 7. get the size of the hash map
print("The size of hash map is: " + str(len(hashmap)))
# 8. iterate the hash map
for key in hashmap:print("(" + str(key) + "," + str(hashmap[key]) + ")", end=" ")
print("are in the hash map.")
# 9. get all keys in hash map
print(hashmap.keys())
# 10. clear the hash map
hashmap.clear();
print("The size of hash map is: " + str(len(hashmap)))

场景 I - 提供更多信息

---

使用哈希映射的第一个场景是，我们需要更多的信息，而不仅仅是键。然后通过哈希映射建立密钥与信息之间的映射关系。

示例

---

让我们来看一个例子：

给定一个整数数组，返回两个数字的索引，使它们相加得到特定目标。

在这个例子中，如果我们只想在有解决方案时返回 true，我们可以使用哈希集合来存储迭代数组时的所有值，并检查 target - current_value 是否在哈希集合中。

但是，我们被要求返回更多信息，这意味着我们不仅关心值，还关心索引。我们不仅需要存储数字作为键，还需要存储索引作为值。因此，我们应该使用哈希映射而不是哈希集合。

更重要的是

---

在某些情况下，我们需要更多信息，不仅要返回更多信息，还要帮助我们做出决策。

在前面的示例中，当我们遇到重复的键时，我们将立即返回相应的信息。但有时，我们可能想先检查键的值是否可以接受。

模板

---

在这里，我们为您提供了解决此类问题的模板：

/** Template for using hash map to find duplicates.* Replace ReturnType with the actual type of your return value.*/
ReturnType aggregateByKey_hashmap(List<Type>& keys) {// Replace Type and InfoType with actual type of your key and valueMap<Type, InfoType> hashmap = new HashMap<>();for (Type key : keys) {if (hashmap.containsKey(key)) {if (hashmap.get(key) satisfies the requirement) {return needed_information;}}// Value can be any information you needed (e.g. index)hashmap.put(key, value);    }return needed_information;
}

场景 II - 按键聚合

---

另一个常见的场景是按键聚合所有信息。我们也可以使用哈希映射来实现这一目标。

示例

---

这是一个例子：

给定一个字符串，找到它中的第一个非重复字符并返回它的索引。如果它不存在，则返回 -1。

解决此问题的一种简单方法是首先计算每个字符的出现次数。然后通过结果找出第一个与众不同的角色。

因此，我们可以维护一个哈希映射，其键是字符，而值是相应字符的计数器。每次迭代一个字符时，我们只需将相应的值加 1。

更重要的是

---

解决此类问题的关键是在遇到现有键时确定策略。

在上面的示例中，我们的策略是计算事件的数量。有时，我们可能会将所有值加起来。有时，我们可能会用最新的值替换原始值。策略取决于问题，实践将帮助您做出正确的决定。

模板

---

在这里，我们为您提供了解决此类问题的模板：

/** Template for using hash map to find duplicates.* Replace ReturnType with the actual type of your return value.*/
ReturnType aggregateByKey_hashmap(List<Type>& keys) {// Replace Type and InfoType with actual type of your key and valueMap<Type, InfoType> hashmap = new HashMap<>();for (Type key : keys) {if (hashmap.containsKey(key)) {hashmap.put(key, updated_information);}// Value can be any information you needed (e.g. index)hashmap.put(key, value);    }return needed_information;
}

设计键

---

在以前的问题中，键的选择相对简单。不幸的是，有时你必须考虑在使用哈希表时设计合适的键。

示例

---

我们来看一个例子：

给定一组字符串，将字母异位词组合在一起。

众所周知，哈希映射可以很好地按键分组信息。但是我们不能直接使用原始字符串作为键。我们必须设计一个合适的键来呈现字母异位词的类型。例如，有字符串 “eat” 和 “ate” 应该在同一组中。但是 “eat” 和 “act” 不应该组合在一起。

解决方案

---

实际上，设计关键是在原始信息和哈希映射使用的实际键之间建立映射关系。设计键时，需要保证：

1. 属于同一组的所有值都将映射到同一组中。

2. 需要分成不同组的值不会映射到同一组。

此过程类似于设计哈希函数，但这是一个本质区别。哈希函数满足第一个规则但可能不满足第二个规则。但是你的映射函数应该满足它们。

在上面的示例中，我们的映射策略可以是：对字符串进行排序并使用排序后的字符串作为键。也就是说，“eat” 和 “ate” 都将映射到 “aet”。

有时，设计映射策略可能是非常棘手的。

设计键 - 总结

---

这里有一些为你准备的关于如何设计键的建议。

1. 当字符串 / 数组中每个元素的顺序不重要时，可以使用排序后的字符串 / 数组作为键。
2. 如果只关心每个值的偏移量，通常是第一个值的偏移量，则可以使用偏移量作为键。
3. 在树中，你有时可能会希望直接使用 TreeNode 作为键。 但在大多数情况下，采用子树的序列化表述可能是一个更好的主意。
4. 在矩阵中，你可能希望使用行索引或列索引作为键。
5. 在数独中，可以将行索引和列索引组合来标识此元素属于哪个块。
   组中。但是 “eat” 和 “act” 不应该组合在一起。

解决方案

---

实际上，设计关键是在原始信息和哈希映射使用的实际键之间建立映射关系。设计键时，需要保证：

1. 属于同一组的所有值都将映射到同一组中。

2. 需要分成不同组的值不会映射到同一组。

此过程类似于设计哈希函数，但这是一个本质区别。哈希函数满足第一个规则但可能不满足第二个规则。但是你的映射函数应该满足它们。

在上面的示例中，我们的映射策略可以是：对字符串进行排序并使用排序后的字符串作为键。也就是说，“eat” 和 “ate” 都将映射到 “aet”。

有时，设计映射策略可能是非常棘手的。

设计键 - 总结

---

这里有一些为你准备的关于如何设计键的建议。

1. 当字符串 / 数组中每个元素的顺序不重要时，可以使用排序后的字符串 / 数组作为键。[外链图片转存中…(img-GAs5TqnJ-1595519356020)]
2. 如果只关心每个值的偏移量，通常是第一个值的偏移量，则可以使用偏移量作为键。[外链图片转存中…(img-JHnqU729-1595519356020)]
3. 在树中，你有时可能会希望直接使用 TreeNode 作为键。 但在大多数情况下，采用子树的序列化表述可能是一个更好的主意。[外链图片转存中…(img-jjmFZI1v-1595519356021)]
4. 在矩阵中，你可能希望使用行索引或列索引作为键。
5. 在数独中，可以将行索引和列索引组合来标识此元素属于哪个块。[外链图片转存中…(img-inj282uq-1595519356021)]
6. 有时，在矩阵中，您可能希望将值聚合在同一对角线中。