问题标签 [perfect-hash]

我有一个整数类型，比如说long，它的值在Long.MIN_VALUE = 0x80...0(-2^63) 和Long.MAX_VALUE = 0x7f...f(2^63 - 1) 之间。Long.MAX_VALUE我想以干净有效的方式将它与〜50％的冲突散列到相同类型的正整数（即在 1 和 之间）。

我的第一次尝试是这样的：

• Math.abs(x) + 1
• (x & Long.MAX_VALUE) + 1

但是那些和类似的方法总是在某些值上存在问题，即 when xis 0// Long.MIN_VALUE。Long.MAX_VALUE当然，天真的解决方案是使用 2 个 if 语句，但我正在寻找更清洁/更短/更快的东西。有任何想法吗？

注意：假设我在 Java 中工作，其中没有定义到布尔和移位语义的隐式转换。

这是我需要的（语言：C# 4）：

我正在建立一个您可以提交投诉的系统。提交投诉后，您将获得一个唯一的 9 位数字，用于在系统中识别您的投诉。

出于安全（通过默默无闻的安全）的目的，我不希望票证 ID 是连续的。但我确实想使用数据库来生成顺序 ID。

所以我需要的是一个双向快速的单射函数：序号到我的票号，然后从票号返回到序号。

这样我ticketId的 in 数据库是连续的，但在向用户显示之前我会对其进行混淆，同样，当我从用户那里得到一个数字时，我会对其进行去混淆处理并使用它在数据库中查找投诉。

混淆部分不需要太复杂，对普通大众来说“不够明显”即可。

例如，我可以简单地更改值的位数，这将得到我（对于 8 位值）：

0 -> 0
1 -> 128
2 -> 192
3 -> 64
4 -> 160
5 -> 96

等等

我有一个从 0xc0003000 到 0xc04a0144 的内存地址列表，列表中有很多间隙和 < 4096 个条目。它在编译时就知道了，我想为它做一个完美的哈希。

然而，在网上查找完美散列给我的信息主要与散列字符串相关，而且它们似乎翻译得不好。

为了清楚起见，我希望能够在运行时获取内存地址并快速检查它是否在散列中。目前我正在使用平均大约 8 个循环来找到答案的二进制搜索。

任何想法我应该吠叫什么树？

首先，定义两个整数N和K，其中N >= K，都在编译时已知。例如：N = 8和K = 3。

接下来，定义一组整数[0, N)（或者[1, N]如果这使答案更简单）并将其命名为S. 例如：{0, 1, 2, 3, 4, 5, 6, 7}

S带有元素的子集的数量K由公式给出C(N, K)。例子

我的问题是：为这些子集创建一个完美的最小散列。示例哈希表的大小将为C(8, 3)或56。

我不关心排序，只关心哈希表中有 56 个条目，并且我可以从一组K整数中快速确定哈希。我也不关心可逆性。

示例哈希：hash({5, 2, 3}) = 42. （数字 42 并不重要，至少在这里不重要）

是否有适用于任何值N和的通用算法K？我无法通过搜索谷歌或我自己的天真努力找到一个。

我正在使用 Google Maps API 并觉得有更好的方法来搜索全景图像而不是大量switch声明。我认为使用外部哈希表会更有效且更易于维护。每个图像都有一个唯一的panoID，我可以定义它。阅读哈希表，我相信我说我可以制作一个表和完美的函数来在恒定时间内获取我需要的数据是正确的。有没有关于如何构建它的好资源？我根本没有散列经验。

我的逻辑是这样的：每个图像都保存在一个目录中sometext_panoID.jpg，其中sometext是一个字符串，panoID是我想要的任何东西。在上述 switch 语句中初始化数据时，所有的切换都是根据 panoID 完成的，并在那里访问其他元数据。例如：

因为我会知道所有的panoIDs，并且一旦构建表就不需要排序、添加或以其他方式更改任何内容，我觉得有一种方法可以制作完美的哈希，但不知道从哪里开始。有小费吗？提前致谢

当要散列的元素数量已知时，是否有可能拥有从字符串到整数的完美散列函数？通过完美的哈希函数，我的意思是没有碰撞的机会。

基本上我正在从一个文件中读取多个表的签名（例如，id、name、address）。不同的表可能有共同的属性（例如名称），但在不同的位置（例如列）。我希望能够问这样的问题：table1 [“name”] 是什么？或表 2 [“名称”]。

更新：我更愿意自己学习而不是使用已经存在的东西。

我有一个描述地址的结构，它看起来像：

我正在寻找一种方法来为这个结构创建一个唯一标识符（我假设它也应该属于 类型string），这取决于所有结构属性（例如，更改AddressLine1也会导致结构标识符的更改）。

我知道，我可以将所有属性连接在一起，但这会给出太长的标识符。我正在寻找比这短得多的东西。

我还假设不同地址的数量不应该超过100M。

关于如何生成此标识符的任何想法？

提前致谢。

史前史：

数据库中有几个不同的表，其中包含一些信息+地址数据。数据以类似于上述格式的格式存储。

不幸的是，现在将地址数据移动到单独的表中非常昂贵，但我希望将来会这样做。

我需要将一些附加属性与地址数据相关联，并为此创建一个单独的表。这就是为什么我需要唯一标识地址数据。

根据http://java-bytes.blogspot.com/2009/10/hashcode-of-string-in-java.html：“首先，众所周知的事实是没有完美的散列算法，其中有没有碰撞。”

作者说的是实际而不是理论上的，对吗？因为理论上，这里有一个完美的哈希函数：“对于给定的对象，给它分配一个新的数字”。有无限数量的数字，所以我们总是有一些东西可以分配给一个独特的对象。但在实践中这是不可行的，因为我们的内存量有限。

我一直在阅读和学习散列和散列表，并使用了一些代码（我对此仍然很陌生，所以我可能会说一些我误解的错误）。我遇到了完美哈希函数的问题。假设我有自己的自定义类型，它以某种方式具有完美的哈希函数：

Anint的哈希码就是它int本身，所以我有一个完美的哈希函数，对吧？但是当我们使用哈希函数通过简单的公式将对象映射到哈希表时：

我们得到一个变量索引，它也取决于我们在哈希表中有多少元素。如果哈希表的大小仅为 int.MaxValue，那么我们将拥有一个完美的哈希函数。例如，假设我们有一个大小为 2 的哈希表。如果我们对数字 1 和 3 进行哈希处理，我们得到

碰撞！我对哈希和哈希表有什么误解吗？结果表明，完美的哈希函数并不完美。

如果散列函数的散列键列表是已知的且不可变的，则可以生成完美的散列函数。Java 中的枚举是已知和不可变元素的列表。因此，应该可以将EnumMap实现为完美的散列。目前（1.7）是用Java完成的吗？