一道程序员面试题？ 第1页

目前有的答案效率都很低。中美各一台服务器，O(n)的对比几乎相当于把整个服务器上的数据从中国传到美国(网络传输的流量正比于文件大小，即使哈希之后)，极其消耗网络流量，而流量正是这个系统中的瓶颈。把文件分成block后比较hash不是不可以，但在整体文件大小未知的情况下，难以确定Block size和数量，以至于难以Scale。

所以我们的目的明确：用尽量少的网络流量，尽可能将计算保留在本地。方法很简单：

，本质上就是多层的hash加上二分（或N分）查找。此算法被应用在很多地方，包括Git，BT协议以及Amazon Dynamo等。网络部分的时间复杂度O(Log n)，网络传输流量O(Log n)，其中n为文件大小

多说两句，其实这也是BT协议的问题。BT的种子文件实际上包含了对要下载的文件按block哈希的结果。这个hash也会被用在下载后的文件校验。所以如果block的size过小，会导致种子文件过大，增加BT种子服务器的压力；而如果size过大，比如2MB/block，又会造成下载一个block后一旦校验失败，需要丢掉2MB的数据，造成大量资源浪费。官方推荐每个block size不超过512K，但在现在文件越来越大的情况下种子文件也将越来越大。而Merkle tree的出现很好的解决了这个问题

最后一句话暴露了出题者的水平。。。

这个问题很显然瓶颈在网络数据传输而不是时间复杂度上，时间复杂度越低越好是在舍本求末，把前面一堆的铺垫丢给弄丢了。

自己算一下就知道：

直接把整个文件传过去逐字节校验的时间复杂度是O(n)。递归分块哈希最糟糕的情况下的时间复杂度是，m是每次分块数量，最好的情况也不过O(n)（至少要对整个文件所有内容哈希一次）。

因为递归哈希在最糟糕的情况下每次都要把所有块哈希一次（假定最终的结果是分到最细的所有块都有一个字节错误），所以总共要对整个文件大小的数据哈希次，其中m是分块数量。时间复杂度反而大，，，，

另外在这个最糟糕的情况下，由于分到最小的块都有错误，结果最终还是把整个文件传过去了。

很显然最符合题意的是把文件传过去，确保时间复杂度只有O(n)。另外瞎评论的已拉黑。

这道题目的最后一句话删掉，那真是一个不可多得的精品，，，

现在的题目就像是毕加索的名作上被个熊孩子写了个XXX到此一游一样，，，，

而且这个题目如果准确的知道错误的字节数量，那么有比哈希好得多的纠错算法，现在的程序员就知道哈希，，，，哎，，，，，