整数序列的完美哈希功能
给定一组整数（序列）1…999_999（例如），我需要将每个单独的整数映射到同一集合中的另一个整数1：1：随机1：1（分布取决于种子）。哈希函数必须可扩展到大型集，因此，改组和存储内存中的所有值不是一个选项。有什么好方法吗？
一些例子：
// 1..3 seq
lowerBound = 1;
upperBound = 3;
seed = 1
h1 = makeHashFn(lowerBound, upperBound, seed)
h1(1) // 2
h1(2) // 3
h1(3) // 1
newSeed = 2
h2 = makeHashFn(lowerBound, upperBound, newSeed)
h2(1) // 3
h2(2) // 1
h2(2) // 2
Given a set of integers (sequence) 1…999_999 (for example) I need to map each individual integer to another integer in the same set 1:1 randomly (distribution depends on seed). Hash function must be scalable to large sets, so shuffling and storing all values in the memory is not an option. Is there any good way of doing this?
Some examples:
// 1..3 seq
lowerBound = 1;
upperBound = 3;
seed = 1
h1 = makeHashFn(lowerBound, upperBound, seed)
h1(1) // 2
h1(2) // 3
h1(3) // 1
newSeed = 2
h2 = makeHashFn(lowerBound, upperBound, newSeed)
h2(1) // 3
h2(2) // 1
h2(2) // 2
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
没有任何形式的内存使用情况，就无法执行此操作。
如果您很高兴发生数字碰撞，那是可能的，但是否则，您实际上无法真正拥有随机和无状态。
但是，您能做的是随机将所有索引的列表随机删除。
每个列表元素只有4或8个字节，对于大多数应用程序来说，这是相当合理的。
如果您使用确定性的种子RNG将索引洗牌，则每次结果都将相同，在这种情况下，您无需存储洗牌索引，而是您可以再生它们并根据需要将其丢弃，以满足您的内存需求。
没有任何银子弹，解决此问题的所有解决方案都将具有重大的权衡。如果您有一个具有数十亿个条目的超级质量数据库，则最好以更有效的方式退后并重新定义问题。
It's not possible to do this without any kind of memory usage.
If you're happy for number collisions to happen, it is possible, but otherwise, you can't really have it be random and stateless.
What you can do though, is shuffle a list of all indices randomly.
That would be only 4 or 8 bytes per list element, which is fairly reasonable for most applications.
If you use a deterministic seeded RNG to shuffle the indices, the result will be the same every time, and in that case, you would not need to store the shuffled indices, rather you could regenerate them and discard them as needed for your memory requirements.
There aren't any silver bullets, every solution to this problem will have significant tradeoffs. If you have a supermassive database with billions of entries, it's probably better to step back and redefine the problem in a more efficient way.