什么是哈希表

哈希表Hash table，也被称为散列表
为了搞清楚这个概念，我们来理解一下什么是散列函数
散列函数
用于把一个查找表中关键字映射成该关键字对应函数的地址函数 $ha s h （ k ey ） = v a l u e$
任意长度的数据通过算法能转换为固定长度
散列表
根据关键字直接访问的数据结构
通俗一点：
想象一下你有一个大箱子，里面装满了各种小盒子，每个小盒子都有一个独特的标签。这个标签就像是哈希表中的键（Key）。现在，如果你想快速找到某个特定标签的小盒子，而不是逐个查看每个盒子，你会怎么做呢？哈希表就是这样一个“大箱子”，它能帮助你快速找到对应的“小盒子”

这里我们 $red$ 就是两个红色小盒子的key，两个小盒子就是value
$gray$ 也是key，两个灰色小盒子就是value
我们可以通过red这个键，找到两个红色小盒子

例题

两数之和

两数之和实在是太经典了，简直是梦开始的地方

思路

来源：官方题解

Python3

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

在这段代码中，哈希表（hashtable）被用作一个字典（dict）来存储数组中的元素及其对应的索引。

Key（键）: 哈希表中的键（key）是数组nums中的元素值。
Value（值）: 哈希表中的值（value）是对应元素在数组nums中的索引。

可能这样子还是不太清晰，我们画图来理解
对于测试用例中的nums =[6,3,8,2,1]，我们创建下表，其中target = 8

测试用例	测试用例	测试用例	测试用例	测试用例	测试用例
key	6	3	8	2	1
value	0	1	2	3	4

刚开始，我们也不是一下子创建出来的这张表

1.初始时，hashtable是空的
2.我们用for循环去遍历
3.对于6,3,8这几个数字，我们刚开始没有找到两数之和，我们先添加到表中
我们执行的是hashtable[nums[i]] = i语句

测试用例	测试用例	测试用例	测试用例
key	6	3	8
value	0	1	2

4.然后遍历到了索引为3的数字2，我们知道6+2就是等于我们的target 8
也就是说满足我们if target - num in hashtable:的条件

if target - num in hashtable:
    return [hashtable[target - num], i]

hashtable[target - num]：由于target - num是hashtable中的一个键，这会返回该键对应的值，也就是之前遍历过的那个元素的索引。
而i就是当前元素的索引

所以这段代码的意思就是说，当我们遍历到2的时候
$8 - 2 = 6$

这个6是之前我们已经存储在我们的表结构中
因此我们返回return [hashtable[target - num], i]
返回6的索引0，返回当前元素2的索引3，也就是我们两数之和的结果

总的思路大概就是这样

进阶

oi wiki 哈希表

什么时候该用哈希表呢？其实遇到了大量数据，我要想要用一些标签去区分它们，就可以用
举个例子
在电话号码簿中，哈希表可以用于快速查找某个人的电话号码。通过哈希函数将人名转换为哈希值，可以直接定位到对应的电话号码，实现快速查找。

我们该怎么样在确定哈希函数呢？通常有以下几种方法

直接定址法
除留余数法
数字分析法
平方取中法

我们有时候不小心会引起哈希冲突，该怎么做呢？

开放定址法（线性探测法，平方探测法，双散列法，伪随机法）
拉链法（chaining）

理想情况下，散列表查找的时间复杂度为 $O (1)$

限于篇幅和时间精力，本次讨论就不详细说明这些方法了，朋友们可以自己找找

练习

字母异位词分组
 最长连续序列

现实应用

SHA-1算法在Git中被广泛使用，用于确保数据的完整性和安全性。通过计算文件的哈希值，Git可以检测文件是否被篡改或损坏。同时，Git也利用哈希值来实现分布式版本控制，确保每个参与者都拥有相同的文件版本和数据结构。
还有其他哈希算法可以用于压缩文件的校验，如MD5等。然而，需要注意的是，MD5算法已经被认为存在安全漏洞，因此在一些对安全性要求较高的场景下，建议使用更安全的哈希算法。
比特币使用的哈希算法主要是SHA-256（Secure Hash Algorithm 256-bit），它是一种加密散列函数，可以生成一个256位的哈希值。SHA-256算法的特点是对于任意长度的输入，都会生成一个固定长度的输出，并且这个输出是唯一的，即使输入只有微小的改变，输出的哈希值也会发生很大的变化。
比特币还使用了另一种哈希算法RIPEMD-160，它生成的是一个160位的哈希值，用于生成比特币地址。比特币地址是通过将公钥进行RIPEMD-160哈希计算，并加上一个版本前缀和校验和得到的。这样可以确保比特币地址的唯一性和安全性。