假如你有一個web站點，人們可以通過一個密碼訪問。 沒有用戶名，只需要一個密碼。 你的站點會有一批合法的密碼。 判斷一個密碼是否在密碼集中是一個安全性敏感的問題： 如果一個用戶輸入合法的密碼，那么他可以訪問一些私密的信息；否則站點顯示404頁面。你如何判斷一個密碼是否合法？

對于這類問題，大部分程序員首先想到的解決方案是用一個 hash表。 一個 hash表是一個鍵值對的集合，由于它不用逐個驗證集合中的映射關(guān)系，因此它有一個很好的特性：根據(jù)鍵可以快速找到值。

哈希表通常被實現(xiàn)為一種存儲結(jié)構(gòu)的數(shù)組，每一元素都有包含有相關(guān)的信息。例如這個數(shù)組的可容納32個該元素，假設(shè)它的hash方法是H，H的實現(xiàn)就是通過對32求余的值來查找元素。 這個哈斯表存儲了一系列key-value鍵值對。查找一個key需要遍歷該列表直到首次匹配到某個元素的key與給定key的相等；如果沒有匹配到，則查找失敗。

不幸的是，將密碼存儲在普通的哈希表的中不是一個好注意。問題在不在于計算哈希值的函數(shù)而在于判斷相等的函數(shù)；通常判斷相等的函數(shù)的時間復(fù)雜度并不是常數(shù)階的。攻擊者可以根據(jù)系統(tǒng)判斷不相等所需要的響應(yīng)時間不同來發(fā)現(xiàn)規(guī)律,并以此來破解你的密碼。

如果你能確保你的哈希表使用一個常數(shù)時間的比較函數(shù)，以此防御駭客的攻擊，那么你就安全了么？不！因為不是每個鏈式結(jié)構(gòu)的長度都是一樣的，例如，有些”有興趣的人“可以搜集信息，據(jù)此分辨那個鏈式結(jié)構(gòu)上的查找操作究竟是進行了一次比較還是兩次。通常，他們有能力獲取各個長度的鏈式結(jié)構(gòu)在你的哈希表的那個數(shù)組中所占的百分比。如果給定這個哈希表的粒度（granularity），那么他們可能就會得到這個數(shù)組的長度。

據(jù)我得知微小的時間差仍然會泄露敏感信息，導(dǎo)致完全失守。所以我們試圖尋找一個在查詢一個值這個操作上與哈希表消耗了同樣的算法步驟的數(shù)據(jù)結(jié)構(gòu)。例如，在一個已排序的長度為SIZE的數(shù)組上進行二分查找需要ceil(log₂(SIZE))步來找到某個值（譯注：ceil(x)指比x大的最小整數(shù)），這并不取決于我們想找的這個鍵是什么或者所進行查找的集合中究竟有什么。在每一步中，我們比較這個鍵和一個”中點“的值哪個較大，并在其中一半上重復(fù)該操作。

一個問題是，我不知道比較160位字符串時間復(fù)雜度為常量的算法。（我想，站點的密碼是服務(wù)器隨機生成的，并且密碼的長度可能達到160位。） 我非常感謝如果有人能夠給出一個時間復(fù)雜度不超過常量的算法。 一個更大的問題是，訪問內(nèi)存的時間不是固定的：訪問一個有序數(shù)組中0耗費的時間可能與訪問10耗費的時間或多或少存在差異。 在算法方面，我們可以在一個更高抽象級別上使用一般模型進行訪問，但是在硬件方面，低級別的內(nèi)存有一個復(fù)雜的并行和并發(fā)協(xié)議，它對于任意指定的訪問，耗費時間為一個非確定的值。“熱”內(nèi)存（經(jīng)常訪問的存儲空間）的讀取速度比“冷”內(nèi)存快。

內(nèi)存訪問的非確定性泄漏了時間信息，如果進行二進制搜索，將會發(fā)生災(zāi)難： 通過觀察時間的差異，攻擊者可以從字面上二分密碼集。 這是最糟糕的事情！

你可以有辦法應(yīng)付這密碼排序，不再通過它們的真實值而是通過它們加密后的hash值（例如通過SHA256加密的值）。這種做法迫使攻擊者不再以密碼值二分空間，而是以hash值，這樣做法可以保護真實的密碼受到攻擊者的攻擊。你還是會泄露一些關(guān)于關(guān)于哪些路徑是‘熱’的，哪些是‘冷’的時間信息，但是你不會真正暴露真實密碼值。

就我所知，有一件事情很明顯，就是我們無法在常見的硬件上設(shè)計出一個鍵值對的map,可以在常量級時間內(nèi)讀取并且map中的實體數(shù)量是亞線性分布的。例如Zooko 存入進去，運行時間常量集意味著最好的情況和最壞的情況都在相同時間量上。當然對于鏈表散列的hash表來說這是錯誤的，對于二進制搜索來說也是錯誤的，因為‘熱’的內(nèi)存訪問時比‘冷’的訪問快。這僅僅似乎合理的常量時間訪問，是在一個數(shù)據(jù)結(jié)構(gòu)上每一次以相同的順序訪問每一個元素。所有在數(shù)據(jù)結(jié)構(gòu)上常量時間的操作都依據(jù)數(shù)據(jù)大小成線性。消息泄露，你所能做的是對那些在你的模型泄露的信息做出解釋，因為我們是以他們的hash值排序而不是他們的真實值排序。

一旦你說服自己，可以從計時上泄露一些密碼的位，那么你完全可以使用不同的哈希表——直接使用一個加密哈希函數(shù)和一個常數(shù)時間復(fù)雜度的相等函數(shù)，這沒有什么問題。我們不需要發(fā)明一個常數(shù)時間復(fù)雜度的小于符號。你從計時上泄露了大概 log ₂ (COUNT)個密碼位，但是因為它們被加密過，你不能將它們用于二分真正的鍵值。當然，你需要確保這個哈希表沒有按順序存放數(shù)據(jù)。這類實現(xiàn)細節(jié)并不是大多常見的哈希表實現(xiàn)所具備的，所以你仍然可能需要實現(xiàn)你自己的哈希表。

還有一種其他的解決方案，你可以改變對數(shù)據(jù)的編碼方式。例如，讓鍵本身就包含被只服務(wù)端（譯注：接受這個鍵并返回鍵所對應(yīng)值的那頭）知道的私有key簽名加密過的數(shù)據(jù)。但是這種方案被網(wǎng)絡(luò)帶寬所限制，同時，對數(shù)據(jù)的重復(fù)拷貝也造成了浪費。這對例如照片這樣的東西并不適用，它們太大了。

歡迎有見解的讀者的指正:) 當我意識到?jīng)]有什么很好的常數(shù)時間復(fù)雜度數(shù)據(jù)結(jié)構(gòu)的時候我很沮喪，但是我很高興如果你能證明我是錯的。感謝在Twitter上的 Darius Bacon, Zooko Wilcox-O'Hearn, Jan Lehnardt,和Paul Khuong的見解，指出了我的錯誤。

英文原文：there are no good constant-time data structures

譯文出自：http://www.oschina.net/translate/there-are-no-good-constant-time-data-structures