网站建设人员的分工,镇江建工建设集团网站,网站开发前台实训,在线做GO分析的网站哈希表
哈希函数哈希表使用了哈希函数来完成key到地址的快速映射#xff0c;所以在了解哈希表之前#xff0c;需要先明白哈希函数的概念和特点。
哈希函数的定义
哈希函数
哈希函数是一种将任意长度输入的数据#xff0c;转换成固定长度输出的算法哈希函数H可以表示为yH(x)
…哈希表
哈希函数哈希表使用了哈希函数来完成key到地址的快速映射所以在了解哈希表之前需要先明白哈希函数的概念和特点。
哈希函数的定义
哈希函数
哈希函数是一种将任意长度输入的数据转换成固定长度输出的算法哈希函数H可以表示为yH(x)
H指代哈希函数x是输入数据可以是任意长度y是输出的哈希值具有固定长度Hashcode
这部分被固定长度输出的数据被称为Hashcode哈希值或散列值哈希函数的特点确定性
不管执行多少次通过某个key所得到的内存数组索引位置即哈希值是不变的固定长度输出
哈希函数的核心任务是将无限映射到有限即不管输入值数据大小是1kb还是1G数据长度是1位还是1000位它的通过哈希函数产生的哈希值长度都是固定的具体输出长度由算法决定
SHA-256算法输出永远是256位32字节MD5算法输出永远是128位16字节单向性
输入值可以单向通过哈希函数获得哈希值但是通过哈希值不可以反向获取输入值原数据。哈希函数是一个“单向门”或“单向函数”。从 x 计算 H(x) 很容易但从H(x)反推出 x 极其困难。
这一点在密码存储上至关重要系统可以存储用户密码的哈希值即时数据库泄漏攻击者也无法轻易从哈希值还原出用户的原始密码高效性
计算哈希值的过程快速且高效即时是处理大量数据也能快速完成哈希函数算法是由简单的位运算与、或、非、异或、移位、旋转构成这些操作在现代计算机上执行是非常快速的需要处理哈希冲突/哈希碰撞
哈希函数因为是无限映射到有限输入空间是无限的所以有可能出现两个不同的输入对应了同一个哈希值即出现了碰撞哈希函数设计目标需要尽可能的避免出现碰撞引申问题1哈希函数和加密函数的区别
哈希函数和加密函数最大的区别是
哈希函数是单向的不可逆即通过哈希值很困难找到原始值加密函数式双向的可逆需密钥解密通过密文也可以找到原文
维度哈希函数 (Hash)加密函数 (Encryption)可逆性单向不可逆双向可逆需密钥解密密钥无密钥有密钥对称或公私钥输出长度固定如 256 位可变通常 ≥ 明文长度速度目标尽量快便于校验对称快、非对称慢但都比哈希慢碰撞必须抗碰撞难以找到两输入同输出无碰撞概念一对一映射典型应用密码摘要、数据完整性、数字签名机密传输、磁盘加密、HTTPS示例算法SHA-256, BLAKE3, MD5AES, ChaCha20对称RSA, ECC非对称引申问题2MD5算法和SHA256算法是哈希函数还是加密函数
MD5算法和SHA256算法都是哈希算法不算加密算法
两者都是任意长度的输入压缩成固定长度摘要(SHA256为256bitMD5为128bit)两者都不设秘钥不可逆不具备加密/界面功能常见用途
校验文件完整性数字签名前置压缩密码存储配合盐值和KDF引申问题3位运算为什么快
位运算是直接在CPU寄存器上用最简硬件逻辑完成的
AND/OR/XOR/NOT/SHIFT 都只需少量晶体管组成的组合逻辑门与门、或门、异或门、移位器
零内存访问、零复杂算法、单周期延迟是所有运算中成本最低的
哈希表的定义定义
哈希表是一种动态数据结构以key-value键值对存储数据核心思想是使用哈希函数将key转换为数组下标索引保存后下次再次查询时使用仍然通过哈希函数将key转化为数组下标快速定位到数据的位置
目的
实现快速的数据存储和检索注意此处的快速检索指的是通过key来查询value是快速的如果仅仅只是查找某个value数据检索效率并不高
核心公式
index hash(key) mod capacity
组成部分哈希函数
将key转换为数组索引的算法数组
用于存储键值对数据的数组哈希冲突/碰撞解决方法
因为哈希函数式无限输入转化为有限输出一定存在不同的输入产生相同的输出即碰撞或称为冲突冲突/碰撞解决方法指的是当碰撞发生时不同的key被映射到同一个数组下标索引时如何处理一般使用以下方法
链表法开放寻址法哈希表的优点操作高效
增、删、查操作的时间复杂度为O(1)非常高效实现简单
大多数编程语言中都有内置支持Java的HashmapPython的dict灵活性强
可以存储各种类型的键值对哈希表的缺点哈希冲突处理
哈希冲突处理不当会影响性能空间浪费
为了避免哈希冲突一般都会预留较大的内存空间不支持有序遍历
哈希表中的元素是无序的因为保存时是通过hash函数计算出应该放在哪个数组下标导致整体是随机的设计复杂
需精心设计哈希与冲突策略、负载因子、并发、缩容等工程细节难度较高引申问题4哈希表为什么操作这么高效哈希表操作时可以直接定位数据存储位置前提通过key来操作
哈希表的核心是哈希函数哈希函数可以将key直接转换为数据在数组中的下标比如get(key)等同于直接查array[5]时间复杂度是常数时间 O(1)数据结构支持随机访问
因为是直接查下标不需要遍历数据哈希冲突处理优化
对于可能存在的哈希冲突哈希表会通过链表法、开放寻址法来优化防止出现哈希冲突从而减少哈希冲突对性能的影响哈希表的应用场景快速查找
通过索引key快速定位内容统计字符或单次出现的频率
计算方式对于每个字符如果它已经在哈希表这一步可以使用哈希函数通过key快速索引中将对应的值加 1。如果它不在哈希表中将其加入哈希表值设为 1。
快速判断一个元素是否在数组中数据库索引
数据库中的哈希索引比如MySQL的Memory引擎缓存系统
LRU 缓存Least Recently Used Cache常用哈希表 双向链表实现
