大數據學習之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函數。