Hash与布隆过滤器

简介: Hash与布隆过滤器

hash 函数

映射函数  Hash(key)=addr ;hash 函数可能会把两个或两个以上的不同 key 映射到同一地址,这种情况称之为冲突(或者  hash 碰撞)


hash的优势

  • 计算速度快
  • 强随机分布(等概率、均匀地分布在整个地址空间)
  • murmurhash1,murmurhash2,murmurhash3,siphash( redis6.0 当中使用,rust 等大多数语言选用的 hash 算法来实现  hashmap ),cityhash 都具备强随机分布性
  • siphash 主要解决字符串接近的强随机分布性

负载因子

  • 数组存储元素的个数 / 数组1长度;用来形容散列表的存储密度;负载因子越小,冲突概率越小,负载因子越大,冲突概率越大。

冲突处理

链表法

引用链表来处理哈希冲突;也就是将冲突元素用链表链接起来。

开放寻址法

将所有的元素都存放在哈希表的数组中,不使用额外的数据结构;一般使用线性探查的思路解决。

STL unordered_* 散列表实现

在 STL 中  unordered_map 、 unordered_set 、unordered_multimap 、 unordered_multiset  四兄弟底层实现都是散列表。


布隆过滤器

布隆过滤器是一种概率型数据结构,它的特点是高效地插入和查询,能确定某个字符串一定不存在或者可能存在。

原理

当一个元素加入位图时,通过 k 个 hash 函数将这个元素映射到位图的 k 个点,并把它们置为 1;当检索时,再通过 k 个 hash  函数运算检测位图的 k 点是否都为 1;如果有不为 1 的点,那么认为该 key 不存在;如果全部为 1,则可能存在。

应用场景

布隆过滤器通常用于判断某个 key 一定不存在的场景,同时允许判断存在时有误差的情况;

常见处理场景:① 缓存穿透的解决;② 热 key 限流;

目录
打赏
0
0
0
0
24
分享
相关文章
|
9月前
|
C#多态概述:通过继承实现的不同对象调用相同的方法,表现出不同的行为
C#多态概述:通过继承实现的不同对象调用相同的方法,表现出不同的行为
198 65
|
10月前
|
C# 面向对象编程的三大支柱:封装、继承与多态
【9月更文挑战第17天】在C#中,面向对象编程的三大支柱——封装、继承与多态,对于编写安全、可维护、可复用的代码至关重要。封装通过访问修饰符和属性保护数据;继承允许子类继承父类的属性和方法,实现代码复用和多态;多态则提高了代码的灵活性和通用性。掌握这三大概念能显著提升C#编程能力,优化开发效率和代码质量。
|
10月前
|
C#
C#一分钟浅谈:委托与事件的实现方式
本文详细介绍了C#编程中委托与事件的基础知识及应用场景。首先解释了委托的概念,包括定义与使用方法;接着介绍了事件这一基于委托的特殊类型,展示了如何在类中定义事件及跨类订阅与处理事件;最后讨论了常见问题如事件未处理异常、重复订阅及内存泄漏等,并提出了相应的解决方案。通过本文,读者将全面掌握委托与事件的使用技巧,提升应用程序的设计与开发水平。
279 8
|
10月前
|
C# 一分钟浅谈:继承与多态性的实践
【9月更文挑战第2天】本文从基础入手,详细介绍了面向对象编程中继承与多态性的核心概念。通过 `Animal`、`Dog` 和 `Cat` 类的示例代码,展示了如何利用继承重用代码及多态性实现不同对象对同一方法的多样化响应,帮助读者更好地理解和应用这两个重要概念,提升面向对象编程能力。
100 5
|
11月前
|
C#
由浅入深理解C#中的事件
由浅入深理解C#中的事件
165 19
|
11月前
|
C++智能指针解析
C++智能指针解析
130 0
C++智能指针解析
【C语言】B树和B+树的解析应用
【C语言】B树和B+树的解析应用
94 0
【C语言】B树和B+树的解析应用
|
11月前
|
C#
C#中的类和继承
C#中的类和继承
全面掌握Unity游戏开发核心技术:C#脚本编程从入门到精通——详解生命周期方法、事件处理与面向对象设计,助你打造高效稳定的互动娱乐体验
【8月更文挑战第31天】Unity 是一款强大的游戏开发平台,支持多种编程语言,其中 C# 最为常用。本文介绍 C# 在 Unity 中的应用,涵盖脚本生命周期、常用函数、事件处理及面向对象编程等核心概念。通过具体示例,展示如何编写有效的 C# 脚本,包括 Start、Update 和 LateUpdate 等生命周期方法,以及碰撞检测和类继承等高级技巧,帮助开发者掌握 Unity 脚本编程基础,提升游戏开发效率。
418 0
C# - 委托与事件
这篇文档介绍了C#中的委托和事件。委托是存储方法引用的类型,支持回调、事件处理,具有引用方法、类型安全、多播性等特性,并在异步编程中发挥作用。事件是委托的封装,提供保护和订阅机制,防止外部直接访问。当需要在类内部控制方法调用,防止外部误触发时,可使用事件。
100 2

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问