大数据学习之BigData常用算法和数据结构
1.Bloom Filter
由一个很长的二进制向量和一系列hash函数组成
优点:可以减少IO操作,省空间
缺点:不支持删除,有误判
如果要支持删除操作:
改成计数布隆过滤器
2.SkipList(跳表)
核心思路:
由多层组成,每层都是一个有序链表,最底层包含所有元素,元素数逐层递减。每个节点包含两个指针,一个->,一个向下。
并行编程情况下可以用锁或者CAS操作。
CAS:
compare and
swap,解决多线程并行情况下使用锁造成性能损耗的一种机制,CAS操作包含三个操作数——内存位置(V)、预期原值(A)和新值(B)。如果内存位置
的值与预期原值相匹配,那么处理器会自动将该位置值更新为新值。否则,处理器不做任何操作。无论哪种情况,它都会在CAS指令之前返回该位置的值。CAS
有效地说明了“我认为位置V应该包含值A;如果包含该值,则将B放到这个位置;否则,不要更改该位置,只告诉我这个位置现在的值即可。
用CAS实现的插入:
void
insert(Node *prev, Node *node) { while (true)
{ node->next =
prev->next; if
(__sync_compare_and_swap(&prev->next,
node->next, node))
{
return; } }
}
3.LSM树(Log-Structured Merge-Tree)
与B
树相比,牺牲部分读性能,大幅提高写性能。
宗旨:把大量随机写改为批量序列写。
在内存中维护多个小的有序结构,在查找时要二分遍历这些结构,不断把小树合并为大树,进行批量插入。
为了优化查找,可以使用Bloom Filter。(判断小结构中有没有目标数据)
4.HashTree
用于快速定位海量数据中少量变化的内容
对每一项数据进行Hash,多项组合之后再Hash,再Hash,最后到Top Hash。
5.Cuckoo哈希
使用两个哈希函数H1(X)和H2(X),插入X时,同时计算H1(X)和H2(X),如果任意一个桶为空,将X插入相应位置,如果都满了,选一个桶把y踢掉,放入X,对y执行上述过程。设定最大替换次数,达到次数时增大桶的数量或者重选Hash函数。
最新文章
- 警惕USB键盘记录器
- java实现图片与base64字符串之间的转换
- windows 2003 远程登录时如何修改管理员密码
- vbs运行批处理
- Cinder-1 TinderBox
- GNU DAEMON THREAD <;1>;
- 第4章 分治策略 monge阵列
- CSS3 旋转3D立方体
- gulp报错
- Rsync:一个很实用的文件同步命令
- 前端js优化方案(连续更新)
- 分享python分析wave, pcm音频文件
- java设计模式之代理设计模式(Proxy)
- (cx_Oracle.DatabaseError) DPI-1047: 64-bit Oracle Client library cannot be loaded: ";libclntsh.so: cannot open shared object file: No such file or directory";
- IDEA配置打可运行jar包
- OSError: Could not find library geos_c or load any of its variants [&#39;libgeos_c.so.1&#39;, &#39;libgeos_c.so
- [工具] 护眼宝 – 傻瓜版屏幕蓝光过滤应用[Win/Android]
- System.Web.UI.Page.Cache 页面 缓存 清除
- Python之numpy基本指令
- Android 改变字体颜色的三种方法
热门文章
- Python Django 编写一个简易的后台管理工具3-运行项目
- Maven Could not open ServletContext resource [/WEB-INF/applicationContext.xml]
- T1387:搭配购买(buy)
- 面试题40:最小(大)的K个数
- python zip 压缩
- Java数据访问对象模式
- mysql自带压测工具--mysqlslap
- laravel打印查询的sql
- linux缺頁異常處理--內核空間[v3.10]
- Java中的动态代理(jdk和cglib)