'高性能C++編程分享'筆記

哈希表

散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計算一個關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。

它以理論上O(1)的時間復(fù)雜度橫掃四海八荒無敵手。在數(shù)據(jù)量很大（百萬以上）的情況下，哈希表比AVL樹的查找效率更高。

BKDRHash

  // 字符串hash函數(shù)
  public static int bkdrhash(String str) {
      final int seed = 131;
      
      int hash = 0;
      
      for (int i = 0; i < str.length(); i++) {
         hash = hash * seed + (int)str.charAt(i);
      }
      
      return hash & 0x7FFFFFFF;
   }

缺點

• 沒有通用的哈希函數(shù)
• 容易存在沖突
• 預(yù)估容量困難，存儲數(shù)據(jù)量增多導(dǎo)致沖突加劇，擴容需要重新哈希

如果想徹底避免以上的問題，可以考慮使用紅黑樹和跳表。在使用這兩個數(shù)據(jù)結(jié)構(gòu)的時候，不用考慮沖突和容量。

紅黑樹

紅黑樹是一二叉查找樹。它的查找，插入，刪除操作的時間復(fù)雜度都是O(logN)。STL中以它作為set和map的底層數(shù)據(jù)結(jié)構(gòu)。紅黑樹相對于AVL樹的好處是，它并不追求完全平衡，所以避免了AVL樹每次更改所進行的大量平衡度統(tǒng)計計算，開銷要小得多。此外，紅黑樹以此來換取增刪節(jié)點時候旋轉(zhuǎn)次數(shù)的降低，從而提高插入效率。

缺點

它將每個結(jié)點標(biāo)記成紅色或黑色，且在每個插入和刪除操作中，都要進行一次調(diào)整，來避免其不同分支太不平衡。而這種調(diào)整是通過子樹的旋轉(zhuǎn)來實現(xiàn)的。這就出現(xiàn)了一個問題：其中涉及的結(jié)點可能包括被操作結(jié)點的父親節(jié)點或者叔叔結(jié)點，往上到祖父母結(jié)點，甚至最后牽涉到根節(jié)點。因為樹之間相隔任意距離的更新，都可能觸及相同的結(jié)點。觸及相同結(jié)點的概率隨著結(jié)點所在層數(shù)的減少而增加，直到根節(jié)點。也就是說“牽一發(fā)而動全身”。
所以，紅黑樹不是一種并發(fā)友好的數(shù)據(jù)結(jié)構(gòu)。

跳表

普通鏈表

image.png

跳表

在計算機科學(xué)領(lǐng)域，跳躍鏈表是一種數(shù)據(jù)結(jié)構(gòu)，允許快速查詢一個有序連續(xù)元素的數(shù)據(jù)鏈表。快速查詢是通過維護一個多層次的鏈表，且每一層鏈表中的元素是前一層鏈表元素的子集。
基于并聯(lián)的鏈表，其效率可比擬于二叉查找樹（對于大多數(shù)操作需要O(log n)平均時間）。
基本上，跳躍列表是對有序的鏈表增加上附加的前進鏈接，增加是以隨機化的方式進行的，所以在列表中的查找可以快速的跳過部分列表，因此得名。所有操作都以對數(shù)隨機化的時間進行。

image.png

為了方便討論，我們在這里用鏈表代替跳表。鏈表是一個并發(fā)友好的數(shù)據(jù)結(jié)構(gòu)

鏈表上加鎖是可以高度局部化的。首先看寫的情況：插入只需要鎖定兩個現(xiàn)有結(jié)點，即即將插入節(jié)點的前驅(qū)和后繼；刪除只需要鎖定三個節(jié)點，即被刪除的結(jié)點，及其前驅(qū)和后繼。下面再看讀的情況，一個讀線程最多只會持有兩個結(jié)點的鎖，那就是遍歷鏈表的時候。我們可以采用 hand-by-hand 的加鎖方法，只需要保證下一個讀的節(jié)點不會在讀之前被其他線程修改（如果下個結(jié)點提前被刪除，那么我們就會訪問到一塊已經(jīng)不存在的內(nèi)存），所以持有當(dāng)前讀的結(jié)點的鎖和下一個結(jié)點的鎖就足夠了。更多情況下我們只對當(dāng)前正在讀的結(jié)點感興趣，所以不需要持有兩把鎖，只需要鎖住當(dāng)前結(jié)點就夠了。因為鎖粒度低，所以允許大量線程在同一鏈表上工作：它們只要處理鏈表的不同部分，就不會發(fā)生沖突。

再來看第二點，毋庸置疑的是，在多核系統(tǒng)里對鏈表進行操作的時候，進行高速緩存的同步成本很小。首先需要說明的是，在對高速緩存進行讀寫的時候，寫的成本總是高于讀的成本。因為寫一個高速緩存時，需要廣播其他高速緩存同步數(shù)據(jù)，而讀則什么都不用做?；谶@個認(rèn)知，我們也可以知道，大量的寫入會花費更多。那鏈表在這一點上表現(xiàn)如何呢？首先看寫中刪除結(jié)點的情況，需要傳輸?shù)奈ㄒ粩?shù)據(jù)是包含兩個相鄰結(jié)點的緩存，這些內(nèi)存會被傳輸?shù)剿衅渌鹀pu核的緩存，這些cpu會在隨后訪問該鏈表。再來看插入的情況，只需要傳遞三個結(jié)點的緩存，顯然成本是很小的。

有序數(shù)組

假設(shè)你有一個穩(wěn)定的數(shù)據(jù)集合，僅要從里面查找數(shù)據(jù)。可以考慮在程序啟動的時候，對數(shù)據(jù)排序，然后在有序集合上做二分查找。這樣做有以下優(yōu)點：第一，數(shù)據(jù)結(jié)構(gòu)和算法都實現(xiàn)簡單；第二，效率高：僅僅需要簡單的一次排序，以后的查找時間復(fù)雜度都是O(log2 n)；第三點，有序數(shù)組有較高的緩存命中率，所以更高效。

預(yù)取

要提高緩存命中率，首先得了解CPU的一個能力，預(yù)取。
在內(nèi)存和Cache之間，預(yù)取是由CPU根據(jù)過去訪問的數(shù)據(jù)地址信息，從此開始線性地往下獲取接下來的若干個內(nèi)存單元，把這些未來可能訪問的數(shù)據(jù)預(yù)先存入cache，從而在數(shù)據(jù)真正被用到時不會造成Cache失效。
在多級高速緩存之間，預(yù)取是當(dāng)高一級緩存往低一級緩存中取數(shù)據(jù)時，除了獲取目標(biāo)數(shù)據(jù)所在的一個Cache line，高一級緩存會自動預(yù)取與其相鄰的一個Cache Line。

通過了解預(yù)取我們可以知道，在對一個線性數(shù)據(jù)結(jié)構(gòu)進行操作時，由于其中數(shù)據(jù)的內(nèi)存地址都是連續(xù)的，所以要用到的數(shù)據(jù)有極大概率被裝入緩存中，避免了頻繁的各級cache數(shù)據(jù)交換所帶來的時間懲罰。

所以有序數(shù)組 + 二分查找是緩存友好的。
二分查找還有另外一個名字，折半查找，或許這個名字能更好地解釋其原理。我們都知道，二分查找每一輪查找結(jié)束之后，查詢范圍都會在原有基礎(chǔ)上縮小一半。所以，數(shù)據(jù)變得越來越密集，再加上有序數(shù)組的連續(xù)性，也就越容易被命中。所以，這就是有序數(shù)組+二分查找效率如此高的原因。