目录
不在合理范围内（used > size or used < 0.1size()）:
hash的应用:
什么时候使用哈希呢？
一般情况下是判断某字符串在大量的数据中是否存在，比如
散列表
hash与平衡二叉树比较:
二叉树通过比较,结构有序,提升搜索效率
key与节点存储位置的映射古关系（无序），通过空间去换取时间
散列表组成:
hash函数(将key映射到某一个地址)
数组
hash(key) % size = index
散列表（Hash Table）是一种基于键值对的数据结构，它通过哈希函数将键（'key'）映射到数组中的特定索引位置，实现快速存储和查找。具体组成和原理如下：
1. 哈希函数（Hash Function）
- 作用：将输入的键（如字符串、整数等）转换成一个整数地址，称为哈希值。哈希值决定了这个键在数组中的存储位置。
- 映射过程：哈希函数会对键进行某种算法处理，使得不同的键尽可能产生不同的哈希值。例如，把一个字符串键映射到一个整数值。
2. 数组
- 作用：哈希表的核心存储空间。数组的每一个元素称为“桶”（Bucket），每个桶可以存储一个或多个值。
- 大小（size）：数组的长度是有限的，因此选择合适的大小（即 'size'）有助于减少哈希冲突（当不同的键映射到相同的索引）。
- 存储方式：哈希表利用数组的索引位置来存储键值对，这样可以在 O(1) 时间内完成查找。
3. 哈希函数映射过程
- 通过 'hash(key) % size = index' 计算出键值对应该存放在数组中的位置。具体步骤为：
- 首先，将 'key' 通过哈希函数转化为一个哈希值（整数）'hash(key)'。
- 然后，用 'hash(key) % size' 对哈希值进行取模操作，以确保结果在数组范围内（'[0, size-1]'）。
- 最后，得到一个数组索引 'index'，将键值对存储到这个位置。
例如：
'''cpp
int hashIndex = hash(key) % size;
'''
示例
假设我们有一个哈希表大小为 '10' 的数组，用来存储字符串键：
1. 选择一个哈希函数 'hash(key)'，将字符串转化为整数。
2. 对数组大小 'size = 10' 进行取模：'hash(key) % 10'，以确定键存储的索引。
3. 若 'key = "apple"'，经过哈希函数得到整数 'hash("apple") = 38'，则 '38 % 10 = 8'，所以将 '"apple"' 存储在数组第 '8' 个位置上。
这样，哈希表实现了通过键快速定位值的功能。
hash函数
作用：
映射关系
怎么选择hash：
选择标准:
计算速度快
强随机分布性
常用hash:
murmurhash2,cityhash,siphash
hash的操作:
插入和删除
本质上都是先靠搜索找到位置,然后进行相关操作
hash冲突
产生原因
哈希冲突产生的原因是不同的键经过哈希函数映射后得到了相同的数组索引，从而导致多个键试图存储到相同的位置。
如何描述冲突程度:
使用负载因子:
解决冲突:
在合理范围内:used < size:
1.链表法
2.开放寻址法:
不在合理范围内（used > size or used < 0.1size()）:
当used > size()：扩容 （一般情况下是翻倍扩容）
当used < 0.1 size():缩容
之后要rehash(因为size改变了)
stl中散列表的实现
哪些stl使用了散列表？
stl(unordered_*)散列表实现
为了实现迭代器，将后面具体节点串成一个单链表
布隆过滤器:
背景:
内存有限，只想确定某个key存不存在,不想知道具体内容
构成:
位图 和 n个hash函数
怎么操作的
(hash(key) & bit_size = index):
查询和插入的操作是一样的
布隆过滤器只能确定某个key是否不存在,但是是否一定存在不能证明。
不支持删除操作的原因:
在位图中每次槽位只有两种状态(0 or 1),一个槽位被设置位1状态,但不确定它被设置了多少次,也不知道被多少个key哈希映射而来以及是被具体哪个hash函数映射而来。
要点:
确定一个key一定不存在,可控假阳率确定存在
不能删除
根据n和p算出m和k
应用分析:
由n和p确定m和k:
https://hur.st/bloomfilter
变量关系:
为什么是哈希函数中，经常对31进行操作
当k为31，假阳率(冲突概率)最低
确定哈希函数
只用2GB内存在20亿个整数中找到出现次数最多的数
k 整数(4个字节)
v 出现次数
用散列表来解决，同时用4个字节来(unit32)来存储数据,因为4个字节可表示21亿多个数字>20亿
现在一组kv要8字节,20亿组要16GB内存
所以对20亿个整数拆分成若干等份
把20亿个整数丶大文件拆分到多个文件中
目的是把相同的整数放在一个文件中
使用哈希函数,哈希函数会生成64位的整数，一方面可以对文件数取余，另一方面可以应用到散列表中
在各个文件中找出出现次数最多的值再比较就可以确定答案
分布式一致的哈希:
解决的问题:
分布式缓存中扩容的问题
（分布式缓存：缓存存储怎么优雅的扩容）
怎么解决的
固定算法
哈希偏移
增加虚拟节点:
解决了哈希偏移和是哈希迁移数据量变少
目的
避免缓存失效:
固定算法
数据迁移
保证数据均衡:
虚拟节点
标签：hash,哈希,海量,函数,数组,key,过滤器,size From： https://blog.csdn.net/jianbaigreat/article/details/143748399