算法特点、哈希表

基于算法思想

比较排序

1. 冒泡排序（Bubble Sort）：
   1. 反复交换相邻的逆序元素
2. 快速排序（Quick Sort）：
   1. 通过分区交换来排序，递归地对分区进行排序
3. 堆排序（Heap Sort）：
   1. 利用堆结构进行排序，构建最大堆，然后依次将最大元素移到数组末尾
4. 归并排序（Merge Sort）：
   1. 分治法，将数组分成两部分分别排序，然后合并有序的部分

非比较排序

1. 计数排序（Counting Sort）：
   1. 统计每个元素出现的次数，然后根据计数进行排序
2. 桶排序（Bucket Sort）：
   1. 将元素分配到多个桶中，每个桶内部进行排序，然后合并所有桶中的元素
3. 基数排序（Radix Sort）：
   1. 按位或数位对元素进行排序，从最低位到最高位逐步排序

基于时间复杂度

n方

1. 冒泡排序（Bubble Sort）：
   1. 简单直观，适用于小规模数据
2. 选择排序（Selection Sort）：
   1. 逐步选择最小（或最大）元素放到已排序部分的末尾
3. 插入排序（Insertion Sort）：
   1. 逐步将元素插入到已排序部分的适当位置

n log n

1. 快速排序（Quick Sort）：
   1. 平均情况下性能较好，最坏情况下为 O(n^2)
2. 堆排序（Heap Sort）：
   1. 稳定的 O(n log n) 性能
3. 归并排序（Merge Sort）：
   1. 稳定的 O(n log n) 性能，适用于大规模数据

n

1. 计数排序（Counting Sort）：
   1. 适用于范围较小的整数排序
2. 桶排序（Bucket Sort）：
   1. 适用于均匀分布的数据
3. 基数排序（Radix Sort）：
   1. 适用于固定长度的整数或字符串排序

基于空间复杂度

原地排序

1. 冒泡排序（Bubble Sort）：
   1. 原地排序
2. 快速排序（Quick Sort）：
   1. 原地排序（有些实现可能需要辅助栈空间）
3. 堆排序（Heap Sort）：
   1. 原地排序

非原地排序

1. 归并排序（Merge Sort）：
   1. 需要额外的存储空间用于合并
2. 计数排序（Counting Sort）：
   1. 需要额外的数组空间
3. 桶排序（Bucket Sort）：
   1. 需要额外的桶空间
4. 基数排序（Radix Sort）：
   1. 需要额外的数组或桶空间

稳定性

稳定

1. 冒泡排序（Bubble Sort）：稳定
2. 归并排序（Merge Sort）：稳定
3. 计数排序（Counting Sort）：稳定
4. 桶排序（Bucket Sort）：稳定（桶内部使用稳定排序算法）
5. 基数排序（Radix Sort）：稳定

不稳定

1. 快速排序（Quick Sort）：不稳定
2. 堆排序（Heap Sort）：不稳定

哈希表

概述

1. 散列表（Hash Table）和哈希表是同一种数据结构
2. 它们都是一种用于实现关联数组（或字典）的数据结构，可以通过键来快速查找值

核心概念

1. 哈希函数
   1. 将输入的键转换为数组中的索引
   2. 好的哈希函数能均匀地分布键，减少冲突
2. 冲突处理
   1. 由于不同的键可能会映射到相同的索引，需要处理这种情况冲突，方法如下。
3. 常见的冲突处理方法有：
   1. 链地址法（Chaining）：将映射到相同索引的所有键值对存储在一个链表中
   2. 开放地址法（Open Addressing）：当冲突发生时，通过寻找数组中的下一个空闲位置来存储键值对

插入

1. 通过哈希函数计算键的初始哈希值，作为数组的下标
2. 如果该下标位置没有存数据，则直接存储键值对
3. 如果该下标位置已经存有数据，比较存储数据的键与待插入数据的键
   1. 如果键值相同，可以根据需要更新值（如果允许更新）
   2. 如果键值不同，则发生冲突
      使用开放地址法中的探查方法（如线性探查、二次探查或双重哈希）找到下一个空闲位置，将新的键值对存储在那里

查找

1. 通过哈希函数计算键的初始哈希值，作为数组的下标
2. 如果该下标位置的键与要查找的键匹配，则返回相应的值
3. 如果不匹配，使用开放地址法中的探查方法继续查找下一个位置，直到找到匹配的键或遇到空位置：
   1. 如果找到匹配的键，返回相应的值
   2. 如果遇到空位置，则说明哈希表中不存在该键

删除

1. 删除过程在开放地址法中稍微复杂一些，因为简单地将元素删除并标记为空可能会破坏查找的正确性
2. 为了解决这个问题，通常使用一个特殊的标记，表示某个位置曾经存储过数据，但现在已经删除（通常称为“懒删除”或“墓碑标记”）
   1. 通过哈希函数计算键的初始哈希值，作为数组的下标
   2. 使用与查找过程相同的探查方法，找到要删除的键所在的位置
   3. 将找到的位置标记为删除状态，而不是简单地标记为空

时间复杂度

1. 平均情况下，插入、查找和删除操作的时间复杂度为 O(1)
2. 最坏情况下，如果所有键都映射到同一个索引（极端情况），时间复杂度为 O(n)

使用场景

1. 数据缓存
   1. 哈希表用于实现缓存机制，如内存缓存（例如 LRU 缓存）和数据库缓存
   2. 通过哈希表可以快速查找到缓存的数据，提高访问速度
2. 关联数组（字典）
   1. 哈希表广泛应用于实现关联数组（或字典），即通过键快速查找对应的值
   2. 常见的编程语言如 Python、JavaScript、Java 和 C++ 都提供了哈希表的内置实现（如 Python 的 dict，Java 的 HashMap，C++ 的 unordered_map）
3. 数据去重
   1. 哈希表可以用于检测和删除数据中的重复项
   2. 例如，从一个列表中去除重复的元素，可以将元素插入哈希表，如果元素已经存在，则跳过插入
4. 计数
   1. 哈希表用于统计元素出现的频率
   2. 例如，统计一段文本中每个单词出现的次数，可以使用哈希表存储每个单词及其对应的出现次数
5. 数据库索引
   1. 哈希表用于实现数据库的索引结构，以便快速查找特定记录
   2. 哈希索引通过计算记录键的哈希值来确定记录存储的位置，从而加快查询速度
6. 字符串匹配
   1. 哈希表用于字符串匹配算法，如 Rabin-Karp 算法，通过哈希值快速比较子串和模式串，提高字符串匹配的效率
7. 密码学
   1. 哈希表用于密码学中的哈希函数实现
   2. 如哈希表中存储密码的哈希值，用于快速验证用户输入的密码是否正确
8. 负载均衡算法
   1. 哈希表用于负载均衡算法
   2. 如一致性哈希（consistent hashing），将请求均匀分配到不同的服务器或资源上，提高系统的可扩展性和容错性
9. 路由表
   1. 在网络路由中，路由器使用哈希表存储路由信息，根据目标 IP 地址的哈希值快速查找下一跳地址
10. 词法分析器
    1. 编译器中的词法分析器使用哈希表存储关键字、标识符等符号，通过哈希表快速识别和查找符号

示例代码

问题

1. 如果解决冲突用的开放地址法，会通过寻找数组中的下一个空闲位置来存储键值对，那么，这个索引是怎么处理的？
   1. 上面的插入过程