我昨天面试，我有这样的问题 - 有服务器和数据库，存储大文本信息（每个文本可以>10 Mb）。对数据库的任何查询都是昂贵的。您需要设计一个程序（服务器），它将接受一个文本并说 - 这个文本是否在数据库中。
我要求做出这样的决定 -对每个文本进行良好的哈希处理。然后制作一组所有哈希。如果输入文本的散列不在集合中- 所以没有这样的文本，否则 - 转到数据库并尝试通过散列和更深的相等来查找此文本。减去这样的决定，它可能是数据库中的很多文本，所以设置会有点大=）可能你知道如何解决它吗？
问问题
267 次
1 回答
3
正如评论中所讨论的，基本概念是通过消除不可能在数据库中的查询文本来减少对数据库的查询次数。
正如您所建议的，散列是一种很好的方法 - 如果您使用良好的散列函数（即碰撞概率低），那么您将永远不需要实际比较文本，因为您（几乎可以肯定）永远不会得到误报.
散列的一种变体（如果内存成为问题）是使用布隆过滤器：“一种节省空间的概率数据结构，用于测试元素是否是集合的成员。” 这种方法比普通散列使用的内存少得多，但代价是一些误报（即有时您需要将文本与数据库进行比较以确保您是否有匹配项）。布隆过滤器可以让您调整内存和误报率之间的权衡。它们用于 NoSQL 数据库，例如BigTable和Apache Cassandra。
正如大卫施瓦茨正确指出的那样更新，哈希函数确实很重要，特别是在查询的重要属性位于数据库中的情况下 - 请参阅下面评论中的讨论。同样的问题也适用于 Bloom 过滤器，当您希望缩小对一小部分文件的磁盘访问范围（例如）但由于误报而不能完全消除磁盘/数据库访问时，它是理想的选择。我最初以速度基准的方式提到了 MurmurHash3，但因为它是非加密的，所以不适合这个问题。过去当我实际实现这样的方法时，我使用了 SHA1，它是加密的。
于 2012-11-23T23:41:32.537 回答