数据结构——Hash Map

1. Hash Map简介

        Hash Map是一种基于键值对的数据结构，通过散列函数将键映射到存储位置，实现快速的数据查找和存储。它可以在常数时间内完成查找、插入和删除操作，因此在需要频繁进行这些操作时非常高效。

2. Hash Map的定义

        散列表（Hash table，也叫哈希表）是一种根据键（Key）直接访问内存存储位置的数据结构。通过计算一个键值的函数，将数据映射到表中的一个位置，以加快查找速度。这个映射函数称为散列函数，存放记录的数组称为散列表。

3. 为什么要使用Hash Map？

        理想的搜索方法是不经过任何比较，一次直接从表中得到要搜索的元素，即查找的时间复杂度为 O(1)。哈希表通过哈希函数将元素的存储位置与其关键码之间建立一种映射关系，从而实现快速查找。

4. 键值对

        键值对是一种常见的数据结构，用于表示两个相关联的数据项：一个是“键”（Key），另一个是“值”（Value）。键用于标识和查找与之关联的值。键值对在许多编程语言中都有特定的表示方法，例如C++的std::pair和Python的字典（dictionary）。

        python

dictionary = {"name": "Alice", "age": 30}

        在C++中：

std::pair<std::string, int> person("Alice", 30);

5. Hash Map的基本实现

        通过一个简单的数学公式实现Hash Map：

        假设有数据集合 {1, 7, 6, 4, 5, 9}，哈希函数为：hash(key) = key % capacity，其中capacity为10。存储位置如下：

- 1 -> 1
- 7 -> 7
- 6 -> 6
- 4 -> 4
- 5 -> 5
- 9 -> 9

6. 哈希冲突

        如果插入元素66，会与元素6冲突，因为它们的哈希地址相同（都是6）。哈希冲突是指不同关键字通过相同哈希函数计算出相同哈希地址的现象。为了避免冲突，需要设计合理的哈希函数。

7. 改进哈希函数

        哈希函数设计原则包括：

        哈希函数的定义域必须包括需要存储的全部关键码。

        哈希函数计算出来的地址能均匀分布在整个空间中。

        哈希函数应该比较简单。

        常用哈希函数设计方法：

        1. 直接定址法：Hash(Key) = A * Key + B

        2. 除留余数法：Hash(key) = key % p (p <= m)

        3. 平方取中法：假设关键字为1234，对其平方得到1522756，取中间的3位227作为哈希地址。

        4. 折叠法：将关键字分割成几部分，将这些部分叠加求和，取后几位作为哈希地址。

        5. 随机数法：选择一个随机函数，取关键字的随机函数值为其哈希地址。

8. 解决哈希冲突的方法

        解决哈希冲突的两种常见方法是闭散列和开散列。

8.1 闭散列（开放定址法）

        当发生哈希冲突时，将元素存放到冲突位置的下一个空位置中。

        线性探测：从冲突位置开始，依次向后探测，直到找到下一个空位置。

        查找公式：hashi = hash(key) % N + i（i = 0, 1, 2, 3, ...）

        二次探测：为了避免线性探测中的堆积问题，使用平方探测法。找下一个空位置的方法为：hashi = hash(key) % N + i^2（i = 1, 2, 3, 4 ...）

8.2 开散列（链地址法）

        将具有相同地址的元素归于同一桶，桶中的元素通过单链表链接起来。哈希桶的极端情况是所有元素都产生冲突，最终都放入一个桶中，此时效率退化为 O(N)。

        可以将桶中的链表结构改为红黑树结构，以提高效率。在JDK1.7中，HashMap由数组和链表组成；在JDK1.8中，引入了红黑树，当链表超过8且数组长度超过64时，链表会转换为红黑树，以提高性能。

9. 闭散列实现

        以下是闭散列法的具体实现代码：

        在python中

class ClosedHashMap:def __init__(self, capacity):self.capacity = capacityself.table = [None] * capacitydef hash_function(self, key):return key % self.capacitydef insert(self, key, value):index = self.hash_function(key)while self.table[index] is not None:index = (index + 1) % self.capacityself.table[index] = (key, value)def search(self, key):index = self.hash_function(key)while self.table[index] is not None:if self.table[index][0] == key:return self.table[index][1]index = (index + 1) % self.capacityreturn Nonedef delete(self, key):index = self.hash_function(key)while self.table[index] is not None:if self.table[index][0] == key:self.table[index] = Nonereturn Trueindex = (index + 1) % self.capacityreturn False

10. 开散列实现

        以下是开散列法的具体实现代码：

        在python中

class Node:def __init__(self, key, value):self.key = keyself.value = valueself.next = Noneclass OpenHashMap:def __init__(self, capacity):self.capacity = capacityself.table = [None] * capacitydef hash_function(self, key):return key % self.capacitydef insert(self, key, value):index = self.hash_function(key)if self.table[index] is None:self.table[index] = Node(key, value)else:current = self.table[index]while current.next is not None:current = current.nextcurrent.next = Node(key, value)def search(self, key):index = self.hash_function(key)current = self.table[index]while current is not None:if current.key == key:return current.valuecurrent = current.nextreturn Nonedef delete(self, key):index = self.hash_function(key)current = self.table[index]prev = Nonewhile current is not None:if current.key == key:if prev is None:self.table[index] = current.nextelse:prev.next = current.nextreturn Trueprev = currentcurrent = current.nextreturn False

        这些实现展示了如何通过不同的方法来解决哈希冲突，确保Hash Map能够高效地插入和查找元素。