数据结构与算法 | 哈希表（Hash Table）

2023-11-02 15:04 由 Java研究者发表于 #其他

哈希表（Hash Table）

在二分搜索中提到了在有序集合中查询某个特定元素的时候，通过折半的方式进行搜索是一种很高效的算法。那能否根据特征直接定位元素，而非折半去查找？哈希表（Hash Table），也称为散列表，就是一种数据结构，用于实现键-值对的映射关系。它通过将键映射到特定的值（哈希值）来实现快速的数据检索。

	// Java 中Hash表JDK中有提供两种结构Hashtable、HashMap，使用接口上区别不大
	// Hashtable 是Dictionary类的子类，而 HashMap 是AbstractMap类的子类。
	// 由于 Dictionary类已经被废弃，因此Hashtable也不再推荐使用。
	// 在工程应用上值得注意的是 Hashtable是线程安全的，而HashMap不是

    public HashMap<Integer,Long> records1 = new HashMap<>();
    public Hashtable<Integer,Long> records2 = new Hashtable<>();

一般而言，哈希表基于哈希函数将键转换为哈希码，然后使用这个哈希码作为索引获取相应的元素。哈希表的优点是具有快速的平均查找时间，通常为O(1)。然而，它也具有一些挑战，如处理哈希冲突、设计良好的哈希函数和维护适当的装载因子。装载因子表示哈希表已用空间与总空间的比例，需要适时进行动态调整以保持哈希表的性能。

	// 示例java中初始化 HashMap的容量以及装载因子。
	Map<Integer,Integer> sumMap = new HashMap<>(2000,0.75f);

哈希表在计算机科学中有广泛的应用，包括实现关联数组、数据库索引、缓存、编程语言中的字典和集合等等。

基本概念

哈希函数（Hash Function）：哈希表使用哈希函数来将键转换为整数，通常是数组的索引。哈希函数应该是确定性的，即对于相同的键，它应该生成相同的哈希码。理想情况下，不同的键应该映射到不同的哈希码，但由于哈希函数的有限性，可能会出现哈希冲突。

哈希冲突（Hash Collision）：当两个不同的键映射到相同的哈希码时，发生哈希冲突。哈希表需要处理哈希冲突，以确保不同的键可以正确存储和检索。

存储结构：哈希表通常由一个数组和一个哈希函数组成。数组的每个元素称为桶（Bucket），它可以存储一个或多个键-值对。

PS：Java 中由于都已经封装好了 HashMap，一般使用可能感知不到这些概念，但要熟练掌握还是需要理解这些基本理念。

基本操作

插入（Insertion）：将键-值对插入哈希表时，首先通过哈希函数计算键的哈希码，然后确定存储位置（桶）。如果存在哈希冲突，通常会使用链表、数组或其他数据结构来解决冲突，并将键-值对添加到存储位置。

查找（Lookup）：查找键对应的值时，使用相同的哈希函数计算哈希码，并在存储位置中查找该键。如果存在哈希冲突，必须在冲突的元素中搜索以找到正确的键-值对。

删除（Deletion）：删除键-值对时，使用相同的哈希函数计算哈希码，然后从存储位置中删除对应的键-值对。

基本应用

Leetcode 383 赎金信【简单】

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。

字符可以转换成ASCII数字，数组的下标也是数字。那么利用这种数字映射作为哈希函数，就能够通过字符直接读取数组存储的信息。通过ASCII数组来记录 magazine 里面包含的各个字符数量，再遍历 ransomNote 使用到的字符判断是否存在于 ASCII数组，并减少数量来标识已经使用过。

借这题不妨讲一讲分块的编码风格。在日常生活中，我们一定有记忆手机号码的经历，一个长长的数字串（比如1234567890）可能很难记忆，但如果将其分成更小的组块，例如(123) 456-7890，就更容易记忆和处理。这个其实在认识心理学里面概念叫："信息分块"（chunking），指的是将大量的信息分割成更小的、有意义的单元，以便更容易处理和记忆。关键点是人类大脑通过将信息分成较小的组块，可以更有效地处理和记忆信息。

所谓代码可读性其实就是对代码的认识，将信息认识心理学的分块理论应用到代码可读性就是提倡的分块编码。可以将冗余的代码分成一块一块的逻辑，块与块之间用空行来进行视觉上的分块，方便小段小段的去理解代码逻辑；每一块代码可以适当的加上注释以方便阅读。当然这些都是形式上的，更重要的是每一块代码逻辑都会聚焦一个目标，这样写法也有利于编码者自身对逻辑的梳理以及减少bug。

不妨练习下类似问题，参考代码就不附上了，相信一定能够完成。

Leetcode 242. 有效的字母异位词【简单】

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。