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函数。

免责声明：本网站（http://www.ciotimes.com/）内容主要来自原创、合作媒体供稿和第三方投稿，凡在本网站出现的信息，均仅供参考。本网站将尽力确保所提供信息的准确性及可靠性，但不保证有关资料的准确性及可靠性，读者在使用前请进一步核实，并对任何自主决定的行为负责。本网站对有关资料所引致的错误、不确或遗漏，概不负任何法律责任。
本网站刊载的所有内容（包括但不仅限文字、图片、LOGO、音频、视频、软件、程序等）版权归原作者所有。任何单位或个人认为本网站中的内容可能涉嫌侵犯其知识产权或存在不实内容时，请及时通知本站，予以删除。