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

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

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

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

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

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

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

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

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

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

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

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

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

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

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