dict 设计与实现

### dict/map 设计方案
在计算机科学中，Map（也称作 Dictionary 或 Hash Map）是一种常用的数据结构，用于存储键-值对（Key-Value Pairs）。实现 Map 的数据结构有多种选择，每种选择都有其优缺点和使用场景。
以下是一些常见的可以用来实现Map的数据结构。

### 1. 哈希表 (Hash Table)
哈希表是一种用来实现 Map 的经典数据结构，通过哈希函数将键映射到存储桶（Bucket）或槽（Slot）的数组索引。支持 O(1) 时间复杂度的平均情况下的查找、插入和删除操作。

>- 优点：快速的查找、插入和删除操作`时间复杂度O(1)`
>- 缺点：
>	- `哈希冲突`需要额外处理，常见处理方法有`链表法(Chaining)`和`开放寻址法(Open >Addressing)`；
>	- 当哈希表的`负载因子（Load Factor）`很高时，性能可能下降，需要扩容并重新哈希`Rehash`；
>- 适用场景：需要高效进行插入、查找和删除操作的场景。
>- python 的 dict 就是用的哈希表；

#### 哈希表冲突的解决方案
- `链表法（Chaining）`
- `开放寻址法（Open Addressing）`
	- `线性探测（Linear Probing）`
	- `二次探测（Quadratic Probing）`
	- `双哈希（Double Hashing）`

> 注意：
> 在使用`开放寻址法`进行哈希表的冲突处理时，删除元素可能会破坏探测序列。这样的破坏会导致后续查找操作失效，因为某些有效元素可能因为中间的删除而无法被找到。
为了正确处理删除操作并保持探测序列的完整性，通常使用以下两种方法：
> - `标记删除（Lazy Deletion）`
	- 用一个特殊标记（比如 Deleted）来标记已删除的槽位；
	- 在插入操作时，遇到“已删除”标记的槽位可以复用；
	- 在查找操作时，遇到“已删除”标记的槽位继续查找下一个槽位；
	- (标记删除是较为常见的方法)
> - `重新哈希（Rehashing）`
	- 创建一个新的、更大的哈希表（如原哈希表的两倍大小）；
	- 将所有不为 None 或 Deleted 的元素重新插入新的哈希表；
	- 更新哈希表引用为新哈希表；
	- (重新哈希是一种较为彻底但开销较大的方法)

### 2. 自平衡二叉搜索树 (Balanced Binary Search Tree)
常见的`平衡二叉搜索树`有红黑树（Red-Black Tree）、AVL树等。它们可以用来实现 Map，并保证 O(log n) 时间复杂度的查找、插入和删除操作。
>- 优点：
	- 保持元素的排序，容易实现有序遍历；
	- 保证了最坏情况下的时间复杂度；
>- 缺点：相较于哈希表，平均查找、插入和删除操作的效率稍低`时间复杂度O(logn)`。
>- 适用场景：需要保持键的有序性，并且支持范围查询的场景。
>- java的TreeMap用的是红黑树；

### Python dict 扩容机制
在 Python 中，dict 是通过数组来实现的，每个键-值对都存储在数组的槽（Slot）中。当数组容量达到一定阈值时，需要对哈希表进行扩容。以下是 dict 扩容的大致过程：

1. 定义初始大小和扩容因子：
	**dict 默认的初始大小大致为 8。扩容因子通常为 2，也就是说，每次扩容都会使哈希表的容量翻倍**。

2. `负载因子`：**负载因子是已用槽的数量与总槽数量的比例**。
	Python dict 在达到某个负载因子后（一般是 2/3），会触发扩容。

3. 扩容过程
	① 创建新的哈希表：分配一个比现有数组更大的数组，新的数组大小一般是现有数组的 2 倍；
	② 重新散列：对现有哈希表中的每个键重新计算哈希值，并根据新数组的大小分配它们在数组中的位置。这称为重新散列；
	③ 将键和值迁移到新的数组中；
	④ 更新引用：完成重新散列后，将哈希表的引用从旧数组更新为新的数组；

### Python dict 优化措施
需要注意的是，Python 内部对 dict 的实现进行了非常多的优化。以下是一些关键点：

>- `动态变化`：Python dict 实现了对哈希表条目的动态分配和释放，这意味着它可以在运行时自动调整表的大小；
>- `优化的哈希函数`：Python 使用了优化的哈希函数来减少哈希冲突；
>- `增强的哈希冲突处理`：即使使用了优化的哈希函数，冲突在所难免。Python 使用开放寻址法（Open Addressing）中的`二次探测`（Quadratic Probing）策略来处理冲突。具体步骤如下：
>	- 如果计算出的初始索引 hash(key) % table_size 位置已被占用，会按照二次探测算法寻找下一个>可用位置；
>	- 探测序列通常为 hash(key) + 1², hash(key) + 2², hash(key) + 3², ...，这种策略可以有效避免线性探测中的 “堆积” 问题；
>- `小对象优化`：对于较小的对象，如短字符串和小整数，Python 使用了特殊的优化技术来减少哈希计算和比较的开销；
>- `减少内存碎片`：Python 使用了一些技术来减少内存碎片，使得 dict 更加高效；

### 哈希表的堆积问题
哈希表的`堆积问题（Clustering）`是指在哈希表中，某些哈希槽（bucket）发生冲突后，连续或接近的多个槽位都被占用了，从而形成一个“堆积”区。堆积问题会导致新的元素在插入这些槽位附近时，探测到空槽所需的步骤数增多，从而显著降低哈希表的性能。

堆积问题会严重影响哈希表的性能：
- `查找效率下降`：当我们查找一个键时，如果哈希槽已经被占用，我们需要依次检查下一个槽位，直到找到目标或确定目标不存在。这显著增加了查找操作的时间复杂度。
- `插入效率下降`：类似地，插入操作也需要找到一个空槽位，堆积区域越大，需要检查的槽位数就越多。
- `删除操作复杂化`：删除一个键后，其它键的探测序列可能会被破坏，需要额外的操作来维护哈希表的一致性。

#### 堆积问题解决方案
假设我们使用哈希函数 h(k) 来计算键 k 在哈希表中的位置。哈希冲突发生时，`开放寻址法（Open Addressing）`会利用`探测（Probing）`策略在哈希表中寻找下一个可用的位置。常见探测策略包括
- `线性探测（Linear Probing）`
- `二次探测（Quadratic Probing）`
- `双哈希（Double Hashing）`

**线性探测**
线性探测是最简单的`开放寻址策略`。如果一个槽位已经被占用，它会检查下一个槽位（原始哈希位置加1），直到找到一个空位。

> 线性探测示例
> 假设我们有一个大小为 10 的哈希表，哈希函数为 h(k) = k % 10，插入键值如下：
插入10，位置 h(10) = 0
[10, -, -, -, -, -, -, -, -, -]
插入20，位置 h(20) = 0，冲突，线性探测找到下一个空位 1
[10, 20, -, -, -, -, -, -, -, -]
插入30，位置 h(30) = 0，冲突，线性探测到位置 2
[10, 20, 30, -, -, -, -, -, -, -]
这时，位置 0, 1, 2 形成了堆积。

>w 线性探测的堆积问题会比较严重。

**二次探测（Quadratic Probing）**
二次探测在冲突时按二次方公式计算下一个槽位。探测序列为：
```
hash(k)+0,hash(k)+1^2,hash(k)+2^2,…
```

> **二次探测示例**
假设有一个大小为 10 的哈希表，插入键值如下：
插入10，位置 h(10)=0
[10, -, -, -, -, -, -, -, -, -]
插入20，位置 h(20)=0，冲突，二次探测到位置 1
[10, 20, -, -, -, -, -, -, -, -]
插入30，位置 h(30)=0，冲突，二次探测到位置 4
[10, 20, -, -, 30, -, -, -, -, -]

>s 二次探测是非线性探测，可以显著减少堆积现象。

**双哈希（Double Hashing）**
双哈希使用两个不同的哈希函数，一个用于计算初始位置，一个用于计算探测步长。探测序列为：
```
hash1(k)+i×hash2(k)
```
> 双哈希示例
假设有一个大小为 10 的哈希表，哈希函数 h1(k) = k % 10 和 h2(k) = 1 + (k % 9)，插入键值如下：
插入10，位置 h1(10)=0
[10, -, -, -, -, -, -, -, -, -]
插入20，位置 h1(20)=0，冲突，双哈希探测到位置 0+1*5
[10, -, -, -, -, 20, -, -, -, -]
插入30，位置 h1(30)=0，冲突，双哈希探测到位置 0+1*4，再冲突探测位置 0+2*4
[10, -, -, -, 30, 20, -, -, -, -]

>s 双哈希的非线性步长显著减少了堆积现象。

**链表法（Chaining）**
链表法为每个哈希槽位分配一个链表，在冲突发生时，将冲突键值对添加到对应槽位的链表中。这样可以完全避免堆积问题，但会增加内存消耗。
> 优点
	- 简单直观：实现和理解相对简单；
	- 高效处理冲突：即使在哈希表高度饱和时，也能有效处理冲突，不影响其他槽位的查找效率；
	- 扩展性好：可以使用其他数据结构（如平衡树、跳表）替代链表，提高复杂度性能；
	- 删除操作简单：从链表中删除元素比从开放寻址法中的哈希表删除元素更简单，且不影响其他元素的探测序列；

> 缺点
	- 额外内存消耗：需要为每个槽位存储一个链表节点，内存利用率不如开放寻址法高；
	- 局部性能差异：链表长度不均匀时，长链表可能导致局部查找性能下降；
	- 缓存不友好：大量链表节点可能分布在内存的不同位置，缓存命中率较低；