去年看到字節(jié)跳動給golang提了issue建議把map的底層實現(xiàn)改成SwissTable的時候，我就有想寫這篇博客了，不過因為種種原因一直拖著。

直到最近遇golang官方開始討論為了是否要接受SwissTable作為map的默認實現(xiàn)，以及實際遇到了一個hashtable有關(guān)的問題，促使我重新思考了常見的hashtable算法，并決定寫下這篇文章。

友情提示：本文不會從零教你寫hashtable或者swisstable，并且需要你對hashtable有一點了解（至少用過且知道常用操作的時間復(fù)雜度）；文中給出的示例代碼為了簡單易懂，放棄了一些實現(xiàn)細節(jié)上的優(yōu)化，所以會和一些現(xiàn)成的實現(xiàn)不一樣，還請注意。

接下來我們先簡單復(fù)習下hashtable，哈希表。

傳統(tǒng)的哈希表

哈希表提供了一個key到對應(yīng)value的映射，通過一個hash函數(shù)把key轉(zhuǎn)換成某個“位置“，從這個位置上可以直接拿到我們想要的value，這就是哈希表的能力。

哈希表一般來說空間復(fù)雜度為O(n)，查找、插入、刪除的平均時間復(fù)雜度是O(1)，最壞情況均為O(n)。

可見哈希表在理論上是個性能非常好的數(shù)據(jù)結(jié)構(gòu)。事實上在大多數(shù)情況下也確實是這樣。

在更進一步探討之前，我們先要假設(shè)幾個前提。

1. 假設(shè)相同的數(shù)據(jù)作為key時計算出的hash結(jié)果總是一模一樣的；而數(shù)據(jù)不同時（哪怕只有一個bit不同時）計算出的hash結(jié)果也會完全不同。

根據(jù)鴿巢原理，上述假設(shè)在真實世界里是不成立的，不過一般hash函數(shù)可產(chǎn)生的hash值的數(shù)量很大，通常比較難遇到不同數(shù)據(jù)產(chǎn)生相同hash的情況，所以這里我們暫且讓這條假設(shè)成立。

2. 對于hash函數(shù)產(chǎn)生的hash值，每一個bit都是隨機的，且隨機概率均等。

這條假設(shè)確保了不會有某些bit會有固定值或者某些值的權(quán)重比另一些高導(dǎo)致不平衡，工業(yè)級強度的hash函數(shù)一般都會盡量保證這條假設(shè)里提出的要求。

符合以上兩條的我們認為它是一個“理想的hash函數(shù)”，這樣的函數(shù)可以最高效的利用hashtable的內(nèi)存并減少沖突。換句話說，有了這樣的函數(shù)的話影響傳統(tǒng)hashtable性能的就只有數(shù)據(jù)在內(nèi)存中的組織方式了。這樣也方便我們接下來的討論。

不過hash函數(shù)再完美，把key映射到一個有限大小的內(nèi)存空間內(nèi)也還是不可避免得會產(chǎn)生沖突：兩個不同的key會被映射到同一個位置。

為了解決這個問題，傳統(tǒng)的hashtable有好幾個解決方案，我們挑最常見的解決沖突的辦法——“鏈表法”和“線性探測法”簡單復(fù)習一下。

鏈表法

鏈表法是最常見的，它的中心思想在于如果key映射到了相同的位置，那么就把這些key和value存在一張鏈表里。

查找的時候先用hash函數(shù)計算得到位置，然后再從存放在該位置上的鏈表里一個個遍歷找到key相等的條目。

它的結(jié)構(gòu)類似這樣：

淡藍色的表示還沒有元素存在。

這個是最原始的實現(xiàn)方式，實際上很多庫不會每個位置（以后簡稱為slot）存一個鏈表，而是用一張大鏈表把每個有值存在的slot串聯(lián)起來，這樣可以節(jié)約n-1個頭結(jié)點和n-1個為節(jié)點的內(nèi)存。

還有一些庫會在鏈表過長的時候把它轉(zhuǎn)換成搜索樹等時間復(fù)雜度更低的結(jié)構(gòu)。所以總體來看拉鏈法實現(xiàn)的哈希表常用操作的平均時間復(fù)雜度都接近于O(1)。

優(yōu)點：

1. 實現(xiàn)很簡單，沒那么多邊界條件要考慮
2. 插入數(shù)據(jù)和刪除數(shù)據(jù)很快，插入用鏈表的頭插法，刪除只需要移動部分節(jié)點的next指針
3. 能采取擴容之外的手段阻止查詢性能退化，比如前面提到的把過長鏈表轉(zhuǎn)換成搜索樹
4. 保證了指針穩(wěn)定性，所以可以放心地用指針去引用哈希表內(nèi)的元素

缺點：

1. 鏈表本身對緩存不夠友好，沖突較多的時候緩存命中率較低從而影響性能。
2. 不同的slot之間數(shù)據(jù)在內(nèi)存里的跨度較大（即使是用大鏈表串聯(lián)的情況下），數(shù)據(jù)結(jié)構(gòu)整體的空間局部性較差

設(shè)計上的注意點：

1. 為什么不同雙鏈表？因為單鏈表夠用了操作是有點麻煩還需額外的頭節(jié)點，但雙鏈表每個節(jié)點都會比單鏈表多出一個指針，會浪費比一個頭結(jié)點更多的內(nèi)存。
2. 為什么不直接用vector？因為刪除元素的時候vector需要移動大量元素，性能和指針穩(wěn)定性上都得不到保證，不實用。

線性探測法

線性探測是另一種常見的哈希表沖突解決方法。

它解決沖突的方式于鏈表法不同，在遇到hash沖突的時候，它會從沖突的位置開始向后一個個查找，直到找到一個空位，或者沒找到然后索引回到了沖突發(fā)生的位置，這時會進行擴容然后再重新執(zhí)行上述插入流程。

查找也是一樣的，首先通過hash函數(shù)計算得到元素應(yīng)該在的位置，然后從這個位置開始一個個比較key是否相等，遇到被刪除的元素就跳過，遇到空的slot就停止搜索，這表示元素不在這個哈希表中。

可以看到大多數(shù)操作都需要從某個位置開始一個個向后比較，這就是它得名線性探測的原因。

這種方法實現(xiàn)的hash表可以是一個數(shù)組，它的結(jié)構(gòu)大致如下：

淡藍色的仍然是沒有元素的空位。值得注意的是虛線標記的被刪除元素。

元素是不能直接刪除后把slot設(shè)置為空的，那樣會破壞查找的流程，例如上面圖里如果把K2刪了然后slot設(shè)置成空，那你就永遠找不到K3了。所以需要把slot設(shè)置成“已刪除”。

插入的時候可以復(fù)用“已刪除”的slot，但需要先檢查key是否存在，否則還是上面那個例子，刪除K2后我們想插入一個K3，實際上K3已經(jīng)存在，但因為他本身應(yīng)該在的slot空了出來，如果不提前檢查的話插入操作就會把新的K3存進錯誤的位置，此時一張哈希表里會有兩個K3，數(shù)據(jù)混亂了。這里得批評下github上某本很受歡迎的算法書，它在給出的insert示例里沒考慮這種問題，這導(dǎo)致了它給出的代碼在一些情況下會導(dǎo)致錯誤的結(jié)果。

這里只是簡單復(fù)習，更詳細的代碼實現(xiàn)可以看這篇。

時間復(fù)雜度上和鏈表法差不多，我們來看看優(yōu)缺點：

優(yōu)點：

1. 對緩存友好，現(xiàn)在可以用數(shù)組或者vector之類的可以在內(nèi)存里緊密排列的結(jié)構(gòu)實現(xiàn)哈希表
2. slot的利用率高，因為元素是存在slot里的，不過這也不全是好事，后面細說
3. 相對來說更節(jié)約內(nèi)存，當然是和最原始的鏈表法實現(xiàn)相比，和用大鏈表串聯(lián)過的比優(yōu)勢不是很明顯，原因在缺點里細說

缺點：

1. 實現(xiàn)復(fù)雜，一個slot得分有元素、空、元素被刪除三種狀態(tài)
2. hash沖突是連鎖式的，一處沖突可能會連續(xù)影響多處，最終導(dǎo)致插入同樣的數(shù)據(jù)，它擴容的次數(shù)會比鏈表法更多，最終可能會用掉更多的內(nèi)存
3. 因為沖突會造成后續(xù)插入和刪除的連鎖反應(yīng)，所以查找過程退化到O(n)的概率更大，而且沒法像鏈表法那樣把有大量沖突的地方轉(zhuǎn)換成搜索樹之類的結(jié)構(gòu)
4. 沒有指針穩(wěn)定性，這倒也不是太大的缺點，只有c++標準強制要求標準庫的hashmap要有指針穩(wěn)定性

因為刪除元素麻煩，加上沖突會有連鎖影響，所以很多庫實現(xiàn)的hashtable都是用的鏈表法。不過即使有這么多缺點，光緩存友好和內(nèi)存利用率高在現(xiàn)代計算機上就是非常大的性能優(yōu)勢了，所以像golang和python都會使用線性探測法的近似變種來實現(xiàn)哈希表。

SwissTable簡介

我們復(fù)習了兩種常見的哈希表實現(xiàn)，它們要么浪費內(nèi)存且對緩存不友好；要么發(fā)生沖突后會更容易導(dǎo)致查找、插入、刪除操作性能下降。這還是在有“完美哈希函數(shù)”的情況下，如果你用了個不那么好的哈希函數(shù)，那會導(dǎo)致key沖突的概率大大上升，性能問題會更加明顯，最壞的情況下性能甚至會不如在數(shù)組里進行線性搜索。

自然而然地，業(yè)界開始尋找一種既對緩存友好又不會讓查找性能退化的太厲害的哈希表算法。大多數(shù)人的研究方向是開發(fā)更好的哈希函數(shù)，在讓哈希函數(shù)不斷接近“完美哈希函數(shù)”的品質(zhì)的同時用各種手段優(yōu)化計算性能；另外一些人在改進哈希表本身的結(jié)構(gòu)力求在緩存友好、性能和內(nèi)存用量上找到平衡。swisstable就屬于后者。

swisstable的時間復(fù)雜度和線性探測法的差不多，空間復(fù)雜度介于鏈表法和線性探測之間。

swisstable的核心思想是hashtable的大部分操作都是圍繞哈希函數(shù)計算得到的結(jié)果和slot的狀態(tài)（是否能存數(shù)據(jù)是否有目標數(shù)據(jù)在slot里）進行的，而要知道這些信息不需要整個slot的數(shù)據(jù)，因此把這些操作需要的信息提取出來作為元信息進行操作，內(nèi)存效率和CPU效率都可以優(yōu)于直接操作存放完整數(shù)據(jù)的slot。

swisstable的實現(xiàn)有很多，我們主要基于將這個數(shù)據(jù)結(jié)構(gòu)推廣壯大的abseil庫的實現(xiàn)進行簡要的介紹，有關(guān)這個實現(xiàn)，cppcon中的演講比我更詳細，可以去看看，文末會給出鏈接。不過我講的可能和這兩個演講的內(nèi)容有些出入，比較又過了好幾年，代碼庫總是要隨著時代變化而發(fā)展的。

SwissTable的結(jié)構(gòu)

別看這名字都把hash改沒了，實際上swisstable依然是hashtable，而且使用改進的線性探測法來解決hash沖突。

所以大家應(yīng)該能想象到，swisstable的底層應(yīng)該也是個類似數(shù)組的結(jié)構(gòu)。有了這樣大致的模糊印象就可以了，現(xiàn)在我們可以來看看swisstable的結(jié)構(gòu)了：

圖里東西挺多，但基本都有詳細的注釋，對于一些比較重要的東西我會稍微再重復(fù)講解一遍。

首先是哈希函數(shù)計算的結(jié)構(gòu)，在swisstable里會被分成兩部分：57bits長度的為H1，用于確定元素存在哪個slot里，slot的索引和control bytes的是對應(yīng)的；剩下的7bits叫做H2，被用作是當前key的哈希特征值，用于后面的查找和過濾。

接著是swisstable的主體結(jié)構(gòu)，實際上就是一塊連續(xù)的內(nèi)存，但除了slot外還在頭部帶有描述每個slot狀態(tài)的控制信息，以及為了內(nèi)存對齊而放進去的填充數(shù)據(jù)。

swisstable比傳統(tǒng)哈希表更快的秘訣就在于這些被叫做“control bytes”的slot控制信息里，即前面說的“元信息”。

控制信息主要是下面這幾種：

• slot是否為空
• slot里的元素是否已經(jīng)被刪除
• slot里存的鍵值對的key的哈希特征（H2）

對于空、刪除和邊界這幾種特殊狀態(tài)，對應(yīng)的值都是特意設(shè)置的，目的是為了在SIMD指令操作時獲得最高的性能，如果你想自己實現(xiàn)swisstable，注意這些狀態(tài)值需要和圖里給的一樣（或者你也可以找到在X86和ARM以外的平臺上的最佳值并使用它們）。

查找、插入、刪除都是基于這些control bytes的，它們非常小，可以盡量多的被放入CPU的高速緩存，同時又包含了足夠的信息以滿足哈希表的增刪改查。而slot就只用來存數(shù)據(jù)，control bytes和slot一一對應(yīng)，控制信息在control bytes里的索引就是對應(yīng)的數(shù)據(jù)在slot里的索引。

另外還可以看到圖里還有一個group的結(jié)構(gòu)，這個結(jié)構(gòu)沒有實體存在（雖然在abseil的實現(xiàn)里有對應(yīng)的類存在），它由連續(xù)的N個控制信息組成，swisstable的線性探測是以group為基礎(chǔ)單位的，一次探測一個group，沒有找到目標就會移動到下一個group繼續(xù)查找。現(xiàn)在看不懂也沒關(guān)系，下節(jié)會簡要說明查找的算法。

到目前為止我們了解了swisstable的結(jié)構(gòu)，至于它為什么這么快，有一個比較次要的原因我們已經(jīng)知道了：所有的操作基本都在control bytes上進行，一個控制信息只有8bit，而且控制信息們緊密排列在連續(xù)的內(nèi)存里對緩存更友好，所以哈希表操作時的緩存命中率會更高，客觀上會提高一點性能。但這不是swisstable最精明的地方，我們接著看看查找一個元素的過程。

在進入下一節(jié)之前我還有另外一個重要的說明需要做：對于control bytes以及對它的操作，我會用前后左右這種方位詞，但實際上操作control bytes時要考慮的不是方位而是內(nèi)存的高低位以及字節(jié)序，后者會影響到索引的計算方式，為了方便敘述我故意省略了這些細節(jié)而使用“前后左右”，我的圖也是按照從左到右從前往后的順序繪制的，如果要考慮這些圖會畫的比較復(fù)雜，算法的描述也將變得繁瑣，因此請原諒我偷一個小小的懶。

SwissTable的查找

提高CPU緩存命中率可以極大提升性能，但不會達到很多性能測試里展示的那種云泥之別。所以swisstable的快主要體現(xiàn)在別的地方——更巧妙的查找算法。

上一節(jié)我們已經(jīng)提到了group，swisstable會根據(jù)H1的值來確定group的起始位置，然后按照一個個group去做“線性探測”。

假設(shè)我們有一個key叫Key1，它已經(jīng)存在了swisstable里，這時候swisstable里的局部數(shù)據(jù)是下面那樣的：

我們要找的數(shù)據(jù)正好在這個group里，但還有另一個key的哈希特征和我們要找的目標沖突了。按照正常的線性探測法的流程，我們應(yīng)該根據(jù)這個group里的控制信息的索引，找到對應(yīng)的slot，然后把里面的key拿出來一一做相等比較，直到找到我們要的目標，在這里我們需要相等比較六次。

這樣也太小看人類的智慧了，下面才是真正的比較過程，也是swisstable的精華：

事實上swisstable會先一次比較一整個group里的哈希特征信息，先把特征值不相等的元素全部排除，特征值不相等那說明key肯定不會相等。

這樣一次檢查了16個值，在這個例子里我們過濾出了兩個需要檢查的索引值，相等比較的次數(shù)一次減少了三分之二。上面這樣的比較借助現(xiàn)代CPU的SIMD功能，只需要三到四條指令即可完成。

將哈希特征比較結(jié)果轉(zhuǎn)換成uint32的整數(shù)也是很巧妙的一步。不轉(zhuǎn)化的話我們?nèi)匀恍枰闅v去尋找有效的數(shù)據(jù)的索引，然而轉(zhuǎn)換成數(shù)字之后我們只需要去計算這個數(shù)字的二進制數(shù)據(jù)里有多少個尾隨的0即可，這在大部分平臺上都只需要一條指令就能完成；想要查找下一個有效的所以，只需要一個小小的位運算技巧就可以把上次找到的為1的位轉(zhuǎn)換成0，然后再次計算尾隨0的數(shù)量即可。整體會比遍歷快很多倍。

如果當前的group里沒找到，那么就會移動到下一個group，重復(fù)上面的步驟，直到找到數(shù)據(jù)或者遇到了control bytes的結(jié)束標志。

這個例子里我們在第一個group里就找到了，而且運氣很好只需要一次相等比較（這里計算尾隨0的話會導(dǎo)致從后往前檢查找到的索引，我們要找的Key1正巧在最后面），而普通的線性探測需要相等比較6次。

這就是swisstable擁有驚人性能的主要原因：它盡量避免線性探測法導(dǎo)致的大量等值比較和鏈表法會帶來的緩存命中率低下，以及在單位時間內(nèi)它能同時過濾N個（通常為16，因為16x8=128，是大多數(shù)平臺上SIMD指令專用的向量寄存器的大小）元素，且可以用位運算代替對數(shù)據(jù)的遍歷。這會為哈希表的吞吐量帶來質(zhì)的飛躍。

SwissTable的插入、更新和刪除

因為swisstable本質(zhì)是使用了改進了的線性探測法，因此一些在線性探測法中遇到的問題在這里也跑不掉。所以插入、更新和刪除都得基于上一節(jié)介紹的查找。

所以對于插入和更新，算法的大致步驟是這樣的：

1. 利用查找的過程嘗試找到目標key，如果存在那就直接進行更新
2. 不存在的時候會選擇合適的有空位的group，當前group沒有位置的時候就會順延到下一個group，這步和線性探測一樣
3. 然后選擇有空位的group里最左側(cè)的一個空位（控制信息顯示為刪除或者空的slot），寫入控制信息，然后把key和value插入對應(yīng)的slot（這里的左側(cè)只是個形象的說法，實際上根據(jù)實現(xiàn)的不同略有出入，但group是一次比較一整組的，所以相對順序通常沒有那么重要）
4. 如果沒找到合適的空位，先嘗試把標記為delete的slot按算法將符合條件的標記為空，依然沒有合適的空位則會嘗試擴容，然后再插入

查找是否有合適的空位和將標記為刪除的slot更新為empty這兩個操作都是借助SIMD指令和位運算批量完成的。

刪除的操作需要考慮一些邊界條件，并為減少內(nèi)存使用量做了一些優(yōu)化：

1. 根據(jù)給的key找到對應(yīng)的control byte和slot
2. 將slot里存的數(shù)據(jù)釋放掉，slot本身保留
3. 將control byte從哈希特征值改成表示數(shù)據(jù)被刪除的標記值
4. 這步是優(yōu)化，會判斷control byte前后的數(shù)據(jù)，符合條件的情況下可以不標記為被刪除，直接標記為empty。

當然了，設(shè)置control byte的值用的是位運算，而檢查是否符合直接標記為空的操作也借助了SIMD。

從這三個操作來看，SwissTable快的原因還在于：所有可以利用SIMD進行批量操作的地方都進行了對應(yīng)的優(yōu)化。

所以SwissTable為什么這么快？

看完SwissTable的實現(xiàn)，我覺得可以總結(jié)為下面幾點：

• 對hashtable的操作從slot轉(zhuǎn)移到了control bytes上，控制信息更小更容易被填入CPU的高速緩存，因此比直接在slot上操作更快，即使需要多付出一次從control bytes得到索引后再去引用slot的代價
• 記錄哈希特征值，減少了無意義的key等值比較，這是線性探測法性能下降的主要元兇
• 對slot的查找和操作是通過control bytes批量進行的，單位時間內(nèi)吞吐量有顯著提升
• 標志位的值和整個數(shù)據(jù)結(jié)構(gòu)的內(nèi)存布局都為SIMD進行了優(yōu)化，可以充分發(fā)揮性能優(yōu)勢
• 對slot也有優(yōu)化，比如對太大的數(shù)據(jù)會壓縮存儲以提高緩存命中率，不過這只是錦上添花

還有一些abseil特有的優(yōu)化，比如根據(jù)table的大小選擇更合適的擴容策略來平衡性能和內(nèi)存效率。這些不是swisstable算法的一部分，就不列進去了。

在解決了空間局部性問題的基礎(chǔ)上，swisstable還利用了現(xiàn)代CPU的特性批量操作元素，所以性能會有飛躍般的提升。

如果CPU沒有對應(yīng)的SIMD指令怎么辦

swisstable需要的主要是sse2的指令，這些指令最早在2000年由Intel發(fā)布，目前X86平臺上常見的處理器都支持，20年前發(fā)布的處理器還在運行的已經(jīng)非常稀有了。

在ARM平臺上比較特殊，雖然有NEON這樣的SIMD指令集存在，但缺少一部分SSE2的功能，雖然可以靠位運算修補，但整體要比X86上多花幾條指令。以及NEON的普及程度較SSE2稍差，新的芯片上應(yīng)該都支持，但稍微老一些的設(shè)備和部分嵌入式設(shè)備/單板計算機就夠嗆了。

最麻煩的是一些不支持算法要求的SIMD指令的平臺。當然也不是沒辦法，實際上swisstable算法中描述的批量操作可以靠位運算實現(xiàn)，其中查找的操作還可以一次批量處理8條數(shù)據(jù)。但吞吐量直接腰斬，一次查找需要的指令數(shù)也大幅超過了能使用SIMD的平臺，粗略看了下至少得多用三倍的指令，這會帶來一些性能衰退。

不過緩存友好和批量操作帶來的好處還是可以體驗到一部分的，所以即使CPU不支持需要的SIMD指令，你依舊能從swisstable中獲益。

SwissTable還有什么需要注意的地方

對于使用者來說只有一個需要注意的地方：如果你要自定義key的哈希函數(shù)，一定得提供一個質(zhì)量最上乘的。因為現(xiàn)在哈希函數(shù)計算出來的值除了要讓數(shù)據(jù)盡量均勻分布之外，還得盡量保證每一個bit的概率均等性，也就是盡量接近前面說的“完美哈希函數(shù)”，否則哈希特征值會出現(xiàn)很多重復(fù)值，這樣即使有再多的批量操作，還是會被大量等值比較拖慢速度。不過這也有上限，最低也差不多在1/128，因為我們就用了七位哈希值。如果我們用了個質(zhì)量堪憂的哈希函數(shù)，這個重復(fù)率就可能變成1/20，SIMD帶來的性能優(yōu)勢可能就蕩然無存了。

對于想實現(xiàn)swisstable的人來說，注意點會稍微多一些。

第一點是注意內(nèi)存對齊，SSE2要求操作的內(nèi)存地址是對齊過的，如果不是它會自己轉(zhuǎn)換，這個轉(zhuǎn)換非常耗時。所以abseil的實現(xiàn)上不僅分配的時候處理對齊，還用填充數(shù)據(jù)保證了這一點。

第二點的slot的個數(shù)，選擇了不合適的slot數(shù)量會導(dǎo)致H1定位沖突的增加，因此像abseil選擇了2**N-1作為slot的數(shù)量，擴容也是按照N∈{1, 2, 3, 4, ...}這樣的方式擴容的。

第三點，用作存放控制信息的數(shù)據(jù)類型大小最好是8bit，多了浪費少了不能充分表示信息并加大了沖突概率，而且這8bit必須是全部可以使用的；如果用的是c/c++，那么char不能用，因為char是否帶符號是平臺和編譯器定義的，沒有可移植性，不用unsigned char是因為標準只規(guī)定了它的最小大小，沒規(guī)定上限，所以不如intN_t這樣的類型來的保險。可以學abseil用int8_t。

總結(jié)

整篇文章其實還忽略了一個影響hashtable算法性能的點：哈希函數(shù)的算法。因為我們開篇就假設(shè)了我們有“完美哈希函數(shù)”，所以沒有對這點進行過多討論。現(xiàn)實是哈希函數(shù)的性能也很重要，但討論怎么優(yōu)化它的性能超出了本文的討論范圍。比較常見的優(yōu)化方向其實和swisstable在實現(xiàn)查找時用的辦法差不多：依賴SIMD增加數(shù)據(jù)吞吐量或者利用硬件指令（AES、SHA系列）來加速計算。詳細的就不做展開了。

如果要說swisstable有什么缺點，那應(yīng)該只有高度依賴哈希函數(shù)的品質(zhì)這一點了，依賴SIMD其實不是什么大問題，現(xiàn)代CPU都支持，新興的平臺比如RISC-V和LoongArch都有活躍的社區(qū)和維護者，隨著時間推進提供對等的支持不是太遠的事，但哈希函數(shù)的品質(zhì)是很難控制的，何況哈希函數(shù)可以使用一些用戶自己實現(xiàn)的。使用者想避免這類問題，最好的辦法就是用現(xiàn)成的被證明品質(zhì)良好的哈希算法，比如murmur3或者用庫里提供的，而不是自己去寫。

swisstable正在逐漸被業(yè)界接納，例如rust就已經(jīng)把它內(nèi)置進標準庫了；golang最后是否會接受swisstable還是未知數(shù)，不過swisstable本身最早就是谷歌設(shè)計和實現(xiàn)的，帶來的提升也是實打?qū)嵉模蚁牍俜阶罱K接納的可能性還是比較大的。

參考資料

首次提出swisstable的cppcon演講：https://www.youtube.com/watch?v=ncHmEUmJZf4

兩年后針對swisstable算法的一些改進：https://www.youtube.com/watch?v=JZE3_0qvrMg

swisstable用到的位運算可以參考這篇，原理上基本一樣：https://methane.hatenablog.jp/entry/2022/02/22/Swisstable_Hash_に使われているビット演算の魔術(shù)

前面提到的即使沒有SIMD也可以同時處理8個控制信息，使用的位運算參考這篇：http://graphics.stanford.edu/~seander/bithacks.html##ValueInWord