大数据常用算法——大数据日知录读书笔记

[TOC]

布隆过滤器(Bloom Filter)

场景:用于检测某个元素是否是海量数据集中的成员。

原理:即判断一个数是否在集合中。

Bloom_filter

  1. 准备一个位数组,全部置0.
  2. 准备K个散列函数,可以将该元素映射到该数组中的K个点,并将改点置为1.
  3. 如果映射中的点有一个为0则不存在,如果均为1可有可能存在。

LSM树

场景:对写效率要求高的场景,能将大量的随机写操作转换成批量的序列写。缺点读效率有降低。

Merkle哈希树(Merkle Hash Tree或称哈希树、Merkle树)

场景:海量数据下快速定位少量变化的数据内容。

Cuckoo哈希(Cuckoo Hashing)

场景:有效解决哈希冲突。

← openWRT路由器的一些小问题  数据结构温习 →