高级数据结构

优先级队列

原理

特性

应用场景

红黑树

原理

特性

应用场景

特性

java的hashmap

B+树

原理

特性

应用场景

前缀树 、 字典树

原理

特性

应用场景

跳表

原理

特性

应用场景

布隆过滤器 bloom filter

原理

构建一个大的数组向量，每个元素放入的时候计算一次hash，得到元素落入的位置。用于做元素是否存在的判别。

特性

节省空间，判别快

应用场景

web3加密货币钱包钱包dApp网站白名单过滤 实现方案：客户端判别+缓存 服务端构建+更新

缓存穿透判别

feed是否推荐过

参数

supported_domains_filter_ String representation of the domain bloom filter bit-vector

bloom_filter_array_size_ Size of the filter in terms of number of bits

number_of_hash_functions_ Number of hash funtions used for lookup in the domain filter

shift_base_  Randomization parameter used by the hashing functions

prime_bases_ Base primes used to generate hashes

误判概率计算

BF计算器

参数： k哈希次数 m数组大小 n元素数量

1. 一个bit位被置为1的概率
2. 一个bit位没有被置为1的概率
3. 一个元素k次哈希后都没有把一个bit位置为1的概率
4. n个元素都经过k次哈希后没把一个bit位置为1的概率
5. 如果一个元素存在误报，意即这个元素经过k次哈希后得到的k个索引全部都是1，概率是
6. 根据自然对数底数e的定义，可以近似表示为：

https://hur.st/bloomfilter/?n=3018&p=0.01&m=&k=4

区块链

原理

特性

应用场景

最后更新于 2023年2月6日 by qlily