有没有一个解决方案来为非有限输入创建一个完美的哈希表？
因此，哈希表对于集内数据的恒时查找非常有用，但据我所知，它们受到可能的哈希冲突的限制，这会增加少量的时间复杂度。
在我看来，任何支持非有限输入范围的散列函数都是减少冲突的一个启发式方法。为任何范围的输入创建一个完美的哈希表有什么绝对的限制吗，还是仅仅是一些还没有人想出来的东西？
共有1个答案
我认为这取决于你所说的“任何输入范围”是什么意思。
如果您的目标是创建一个哈希函数，它可以接受任何内容，并且不会产生冲突，那么就没有办法做到您所要求的。这是归档原则的结果--如果您有n个对象可以哈希，那么您的哈希函数至少需要n个不同的输出，或者您必须得到至少一个哈希冲突。如果有无限多个可能的输入对象，那么就不能建立一个总能避免冲突的有限哈希表。
另一方面，如果您的目标是构建一个查找为最坏情况O(1)的哈希表（也就是说，您只需查看固定数量的位置即可找到任何元素），那么就有许多不同的选项可用。您可以使用动态perfect哈希表或cuckoo哈希表，它支持最坏情况下的O(1)查找和预期的O(1)插入和删除。这些哈希表通过使用多种不同的哈希函数而不是任何一个固定的哈希函数来工作，这有助于规避上述限制。
希望这有帮助！
-
问题内容： 是否有一个很好的方法来Map 获取和忽略案件？ 问题答案： TreeMap扩展了Map并支持自定义比较器。 字符串提供默认的不区分大小写的比较器。 所以： 比较器不考虑区域设置。在其JavaDoc中阅读有关它的更多信息。
-
我创建了一个JOOQ脚本，该脚本由Flyway执行，以创建一个带有一个枚举的表。当生成运行PostgresSQL实例的方案时，生成的POJO枚举信息将丢失，并且该字段只是一个字符串。 要从PostgresSQL数据库生成枚举到Java，我需要执行以下黑客操作并区分DB方言。因此，我需要对每次迁移都以特殊的方式处理枚举。 最后，我替换了支持枚举的H2，一切看起来都正常。我有Java POJO中的en
-
在Android上使用phonegap创建了一个应用程序。 一切都很好，除了视频不会以任何形式播放。只有音频。 错误： E/libEGL（1441）：在没有当前上下文的情况下调用OpenGL ES API（每个线程记录一次） 尝试使用非嵌入式视频，不同的格式，不同的嵌入，改变config.xml设置，基本上大约30-40种不同的解决方案。并且已经为此工作了40多个小时。 大约11个月前，我在Pho
-
我的意思是，这不是要知道列表是否排序（布尔值），而是像“排序”的比率，像统计学中的相关系数。 例如, > 如果列表中的项目按升序排列，则其比率为1.0
-
如何在不使用https的情况下使用带有参数的方案？它仅适用于https，我想使用其他代码，例如使用url打开应用程序： 这是我的实际代码： 我试过了 非常感谢。
-
我正试图将Hamcrest匹配器引入到我的团队的一些代码中。为了消除匹配实例集合的复杂性，我想为我的每个匹配器编写一个帮助器方法，我希望匹配的集合。所以本质上，我是在包装容器InAnyOrder。也就是说，如果有人以null作为预期和实际传递，我希望它匹配。但是按照我编写代码的方式，如果为预期传递null，它将抛出一个NullPointerExcION。所以我想返回一个IsNull匹配器，如果nu