【愚公系列】2023年11月 七大查找算法(六)-哈希查找
🏆 作者简介，愚公搬代码 🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，阿里云专家博主，腾讯云优秀博主，掘金优秀博主，51CTO博客专家等。 🏆《近期荣誉》：2022年CSDN博客之星TOP2，2022年华为云十佳博主等。
🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。
🏆🎉欢迎 👍点赞✍评论⭐收藏
🚀前言
在编程语言中，查找算法是指在一个数据集合中查找某个元素是否存在的算法。常见的查找算法包括：
- 顺序查找（Sequential Search）：逐个遍历数据集来查找目标元素，时间复杂度为O(n)。
- 二分查找（Binary Search）：在有序数据集合中，从中间位置作为起点不断划分区间并查找，时间复杂度为O(log n)。
- 插值查找（Interpolation Search）：在有序数据集合中，根据目标元素与数据集合首尾之间的差值，利用插值估算目标元素的位置，时间复杂度为O(log log n)或O(n)。
- 斐波那契查找（Fibonacci Search）：在有序数据集合中，根据斐波那契数列调整中间点的位置来查找，时间复杂度为O(log n)。
- B树查找（B-Tree Search）：在平衡的B树中查找元素，时间复杂度为O(log n)。
- 哈希查找（Hash Search）：通过哈希函数将元素映射到哈希表中，并在哈希表中查找元素，时间复杂度为O(1)。
- 分块查找（Block Search）：将数据集合划分为若干块，在每个块中进行二分查找或顺序查找，时间复杂度为O(sqrt(n))。
以上算法都有各自适用的场景，开发者需要根据数据集合的特性和需求选择最适合的算法来进行查找。
🚀一、哈希查找
🔎1.基本思想
哈希查找算法的基本思想是将关键字通过哈希函数映射为一个索引值，然后在索引值对应的桶或者链表中查找目标元素。
具体地说，哈希查找算法包含两个过程：
- 哈希函数：将关键字映射为一个索引值。哈希函数需要满足以下两个条件：
- 映射函数确定：对于每个关键字，哈希函数都映射到相同的索引值；
- 均匀性：尽可能使得不同的关键字映射到不同的索引值。
- 查找过程：通过哈希函数映射得到的索引值，在索引值对应的桶或者链表中查找目标元素。
哈希查找算法的时间复杂度是O(1)，但是在处理哈希冲突时，需要进行一定的额外操作，如开放地址法、链地址法等，会导致时间复杂度变高。因此，在设计哈希函数时，需要综合考虑哈希函数的效率和冲突处理方法。
🔎2.复杂度分析
哈希查找算法的时间复杂度一般为O(1)，即它的查找时间不随数据规模的增加而增加，但是最坏时间复杂度是O(n)，即在极端情况下，哈希函数可能将所有的键值映射到同一个槽中，此时查找一个关键字需要遍历整个链表，时间复杂度就变成了O(n)，但是这种情况发生的概率很小，可以通过优化哈希函数来尽可能地避免这种情况的发生。
除了时间复杂度之外，哈希查找算法还需要考虑空间复杂度，因为需要维护哈希表和链表等数据结构，所以需要分配额外的空间来存储这些数据结构，空间复杂度为O(n)。但是，由于哈希表可以实现O(1)的查找时间，因此在空间可以承受的情况下，哈希查找算法是一种非常高效的查找算法。
🔎3.应用场景
哈希查找算法主要适用于以下场景：
- 查找速度要求高，数据量大的情况下，哈希表的平均查找时间复杂度为O(1)，相比于其他查找算法有较大优势。
- 数据需要频繁的插入、删除和更新，哈希表对于这些操作的时间复杂度也是O(1)。
- 数据集合无序的情况下，哈希表可以通过哈希函数将数据映射到表格中的任意位置，避免了对数据的排序操作。
- 需要对数据进行分组或分类的情况下，哈希表可以将数据分散到不同的桶中，便于统计分析。
- 在实现缓存、索引、字典、路由表等数据结构时，哈希表也是一种常用的解决方案。
🔎4.示例
namespace HashSearch.CSharp
{
class Program
{
//初始化哈希表
static int hashLength = 7;
static int[] hashTable= new int[hashLength];
//原始数据
static List<int> list = new List<int>() { 13,29,27,28,26,30,38 };
static void Main(string[] args)
{
Console.WriteLine("********************哈希查找(C#版)********************\n");
//创建哈希表
for (int i = 0; i < list.Count; i++)
{
Insert(hashTable,list[i]);
}
Console.WriteLine("展示哈希表中的数据：{0}",String.Join(",",hashTable));
while (true)
{
//哈希表查找
Console.Write("请输入要查找的数据:");
int data = int.Parse(Console.ReadLine());
var result = Search(hashTable, data);
if (result == -1) Console.WriteLine("对不起，没有找到!");
else Console.WriteLine("数据的位置是：{0}", result);
}
}
/// <summary>
/// 哈希表插入
/// </summary>
/// <param name="hashTable">哈希表</param>
/// <param name="data">待插入值</param>
public static void Insert(int[] hashTable, int data)
{
//哈希函数,除留余数法
int hashAddress = Hash(hashTable,data);
//如果不为0，则说明发生冲突
while (hashTable[hashAddress] != 0)
{
//利用开放定址的线性探测法解决冲突
hashAddress = (++hashAddress) % hashTable.Length;
}
//将待插入值存入字典中
hashTable[hashAddress] = data;
}
/// <summary>
/// 哈希表查找
/// </summary>
/// <param name="hashTable">哈希表</param>
/// <param name="data">待查找的值</param>
/// <returns></returns>
public static int Search(int[] hashTable, int data)
{
//哈希函数,除留余数法
int hashAddress = Hash(hashTable,data);
//冲突发生
while (hashTable[hashAddress] != data)
{
//利用开放定址的线性探测法解决冲突
hashAddress = (++hashAddress) % hashTable.Length;
//查找到了开放单元或者循环回到原点，表示查找失败
if (hashTable[hashAddress] == 0 || hashAddress==Hash(hashTable,data)) return -1;
}
//查找成功,返回值的下标
return hashAddress;
}
/// <summary>
/// 哈希函数(除留余数法)
/// </summary>
/// <param name="hashTable">待操作哈希表</param>
/// <param name="data"></param>
/// <returns>返回数据的位置</returns>
public static int Hash(int[] hashTable, int data)
{
return data % hashTable.Length;
}
}
}腾讯云开发者
