无法做到常数时间复杂度的数据结构

假如你有一个web站点，人们可以通过一个密码访问。 没有用户名，只需要一个密码。 你的站点会有一批合法的密码。 判断一个密码是否在密码集中是一个安全性敏感的问题： 如果一个用户输入合法的密码，那么他可以访问一些私密的信息；否则站点显示404页面。你如何判断一个密码是否合法？

对于这类问题，大部分程序员首先想到的解决方案是用一个 hash表。 一个 hash表是一个键值对的集合，由于它不用逐个验证集合中的映射关系，因此它有一个很好的特性：根据键可以快速找到值。

哈希表通常被实现为一种存储结构的数组，每一元素都有包含有相关的信息。例如这个数组的可容纳32个该元素，假设它的hash方法是H，H的实现就是通过对32求余的值来查找元素。 这个哈斯表存储了一系列key-value键值对。查找一个key需要遍历该列表直到首次匹配到某个元素的key与给定key的相等；如果没有匹配到，则查找失败。

不幸的是，将密码存储在普通的哈希表的中不是一个好注意。问题在不在于计算哈希值的函数而在于判断相等的函数；通常判断相等的函数的时间复杂度并不是常数阶的。攻击者可以根据系统判断不相等所需要的响应时间不同来发现规律,并以此来破解你的密码。

如果你能确保你的哈希表使用一个常数时间的比较函数，以此防御骇客的攻击，那么你就安全了么？不！因为不是每个链式结构的长度都是一样的，例如，有些”有兴趣的人“可以搜集信息，据此分辨那个链式结构上的查找操作究竟是进行了一次比较还是两次。通常，他们有能力获取各个长度的链式结构在你的哈希表的那个数组中所占的百分比。如果给定这个哈希表的粒度（granularity），那么他们可能就会得到这个数组的长度。

据我得知微小的时间差仍然会泄露敏感信息，导致完全失守。所以我们试图寻找一个在查询一个值这个操作上与哈希表消耗了同样的算法步骤的数据结构。例如，在一个已排序的长度为SIZE的数组上进行二分查找需要ceil(log₂(SIZE))步来找到某个值（译注：ceil(x)指比x大的最小整数），这并不取决于我们想找的这个键是什么或者所进行查找的集合中究竟有什么。在每一步中，我们比较这个键和一个”中点“的值哪个较大，并在其中一半上重复该操作。

一个问题是，我不知道比较160位字符串时间复杂度为常量的算法。（我想，站点的密码是服务器随机生成的，并且密码的长度可能达到160位。） 我非常感谢如果有人能够给出一个时间复杂度不超过常量的算法。 一个更大的问题是，访问内存的时间不是固定的：访问一个有序数组中0耗费的时间可能与访问10耗费的时间或多或少存在差异。 在算法方面，我们可以在一个更高抽象级别上使用一般模型进行访问，但是在硬件方面，低级别的内存有一个复杂的并行和并发协议，它对于任意指定的访问，耗费时间为一个非确定的值。“热”内存（经常访问的存储空间）的读取速度比“冷”内存快。

内存访问的非确定性泄漏了时间信息，如果进行二进制搜索，将会发生灾难： 通过观察时间的差异，攻击者可以从字面上二分密码集。 这是最糟糕的事情！

你可以有办法应付这密码排序，不再通过它们的真实值而是通过它们加密后的hash值（例如通过SHA256加密的值）。这种做法迫使攻击者不再以密码值二分空间，而是以hash值，这样做法可以保护真实的密码受到攻击者的攻击。你还是会泄露一些关于关于哪些路径是‘热’的，哪些是‘冷’的时间信息，但是你不会真正暴露真实密码值。

就我所知，有一件事情很明显，就是我们无法在常见的硬件上设计出一个键值对的map,可以在常量级时间内读取并且map中的实体数量是亚线性分布的。例如Zooko 存入进去，运行时间常量集意味着最好的情况和最坏的情况都在相同时间量上。当然对于链表散列的hash表来说这是错误的，对于二进制搜索来说也是错误的，因为‘热’的内存访问时比‘冷’的访问快。这仅仅似乎合理的常量时间访问，是在一个数据结构上每一次以相同的顺序访问每一个元素。所有在数据结构上常量时间的操作都依据数据大小成线性。消息泄露，你所能做的是对那些在你的模型泄露的信息做出解释，因为我们是以他们的hash值排序而不是他们的真实值排序。

一旦你说服自己，可以从计时上泄露一些密码的位，那么你完全可以使用不同的哈希表——直接使用一个加密哈希函数和一个常数时间复杂度的相等函数，这没有什么问题。我们不需要发明一个常数时间复杂度的小于符号。你从计时上泄露了大概 log ₂ (COUNT)个密码位，但是因为它们被加密过，你不能将它们用于二分真正的键值。当然，你需要确保这个哈希表没有按顺序存放数据。这类实现细节并不是大多常见的哈希表实现所具备的，所以你仍然可能需要实现你自己的哈希表。

还有一种其他的解决方案，你可以改变对数据的编码方式。例如，让键本身就包含被只服务端（译注：接受这个键并返回键所对应值的那头）知道的私有key签名加密过的数据。但是这种方案被网络带宽所限制，同时，对数据的重复拷贝也造成了浪费。这对例如照片这样的东西并不适用，它们太大了。

欢迎有见解的读者的指正:) 当我意识到没有什么很好的常数时间复杂度数据结构的时候我很沮丧，但是我很高兴如果你能证明我是错的。感谢在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