【数据结构】你真的了解哈希表吗？看完你会对数据结构——哈希表， 会有更深更全面的认识 （理论篇）

本篇会加入个人的所谓鱼式疯言

❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言

而是理解过并总结出来通俗易懂的大白话,

小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.

🤭🤭🤭可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 ！！！

前言

在当今这个信息爆炸的时代，数据的快速检索和处理变得尤为重要。想象一下，如果你有一个巨大的图书馆，而你需要在几秒钟内找到特定的一本书，你会怎么做？这正是哈希表的魔力所在。哈希表以其高效的数据检索能力，成为了现代计算机科学中的一个关键技术。本文将深入探讨哈希表的工作原理、它如何优化数据存储和检索，以及它是如何解决数据存储中的冲突问题的。

目录

1. 哈希表的初识

2. 哈希冲突

一. 哈希表的初识

1. 哈希表的理解

什么是哈希表？ 简单来说

哈希表就是一种把 key值 通过 哈希函数 映射到 数组中指定位置 的 方便快速查找， 插入， 删除 的一种数据结构。

这里的 快速 ， 可以达到多快呢? 大体上可以达到 O(1) 的 时间复杂度 的 常数级别 的效率。

其中这里的 Key 值， 不仅仅是 整数数据 ， 也可以是 字符串 ， 包装类类型 的数据当做key 然后映射成数组的 索引（下标） ， 用来方便查找。

试想一下， 如果有一排加了锁的柜子， 和手中有一串钥匙。

如果你的都 没有标记哪把钥匙对应几号柜子 ， 就需要一个一个的进行比对， 这时就需要遍历 每一个把钥匙 来进行开锁， 这时的 效率就会很低 。

但是如果你标记了哪把钥匙对应着哪个柜子 ， 比如这把黑色的钥匙上面标记着五号柜子， 然后我只要把黑色的钥匙对着五号柜子就可以很快的开锁， 不必遍历所有的钥匙来开五号柜子， 这样的 效率就会很高 。

对于 key 怎么利用 哈希函数 转化成 数组索引位置， 下面就让我们来看看吧 🥩🥩🥩

鱼式疯言

补充说明 ：

哈希表又称之为 散列表 ， 其中散列的英文就是 hash ， 而key 的中文名称又称之为 关键码 。

哈希表的快就在于， 关键码不用进行多次比较来找到 自身的位置 ， 就可以 快速的通过索引的位置 进行操作。

2. 哈希函数

对于 哈希函数 的设计有常用的两种方式

1. 直接定制法

2. 除留余数法

<1>. 直接定制法

直接定制法， 用公式法表示就是

Hash(k) = A* k + B 通过这样的方式， 将 key 的值转为通过这样的哈希函数转化为 一个值 。

这个哈希函数我们称之为 线性函数 ， 而我们通过这个线性函数得到的这个值我们称之为 哈希值。

小伙伴们可以先写下这道题：