假设我有一个唯一编号列表(例如105,342,432,34等),我想将它们映射到索引(0,1,2,3等)。有没有一个通用的方法来做到这一点?如果不是,则假定您事先知道列表中的所有数字,并且可以硬编码它们的值。如果这没有帮助,另一个限制因素可能是这些数字“几乎是连续的”。这意味着它们大部分是连续的,但可能存在差距(您事先知道这些差距)。将唯一编号映射到索引
0
A
回答
1
你想要做的是基本上实现一个哈希映射(或字典)。许多实现这种结构的语言都有很多库。
在一个非常简单的方式下,发生了什么是一个数组和一个哈希函数,它将您的数字映射到数组中的某个索引,从而实现O(1)分期访问您的元素基于他们的关键。
第二个重要方面是如何处理碰撞。举例来说,你的数字的哈希函数是f(x) = x mod 10
。 和将被散列为。这是一次碰撞,必须予以处理。例如,您可以创建有序的元素列表并将其分配给您的阵列插槽。搜索元素时,您可以散列其密钥并在指定数组位置的列表中搜索确切的密钥匹配。
这仅仅是这一切的开始,你可能在维基百科上找到关于这一切的更多信息,在 Hash function和Hash map。
值得一提的是,在你的情况下,你只需要自己存储密钥。通常我们需要存储更复杂的对象,并通过它们的键(通常是数字或字符串)来搜索它们,但也可能是任何类型的更复杂的对象。
编辑
我只是意识到,你的问题是更多关于寻找最好的散列函数你不是更通用的解决方案来与你相似问题的具体方案。
如果我理解正确,你是说你事先知道这个数字?如果这真的是这样,你可以如果号码分配你的数组中的索引他们每个人一个一个,在一个非常硬编码的形式(如你所说你自己),如:
if (num == 105)
idx = 0;
else if (num == 342)
idx = 1;
...
如果你不知道你的号码,但你知道,也就是说,最小的和最伟大的人,你可以将它们散列到指数中:
f(x) = (x - smallest_num) mod (greatest_num - smallest_num + 1)
在这种情况下,f(x)
是一个完美的散列函数,这意味着不会有任何碰撞。考虑到你的数字并不总是连续的,你的数组仍然有一些空位。
注意:我仍然不确定您打算如何处理这个问题,因此我不确定我是否正确回答了您的问题。特别是事实上,你可能事先知道你的号码,或者你可能知道很多关于他们的事情,这使我很困惑。也许如果你的目的已经明确,我们可以给你不同的方式来实现你的目标。
相关问题
- 1. 将电源状态映射到唯一编号NFA到DFA
- 2. 将字符串映射到唯一编号?
- 3. 将唯一编号映射到6个字符的唯一字符串
- 4. 将唯一组合映射到数字
- 5. 将形状编号映射到图例
- 6. 将属性映射到索引列
- 7. 将任意对象映射到索引
- 8. C++索引到索引映射
- 9. 映射到一个数组索引
- 10. 学说2映射引用唯一键
- 11. 查找唯一向量的索引和逆映射
- 12. 唯一索引与非唯一索引
- 13. 将一系列索引映射到坐标数组
- 14. 将非唯一索引更改为唯一索引
- 15. 休眠外键映射到唯一键
- 16. sql唯一映射列
- 17. /映射/索引被找到,但没有/映射与ASP.NET MVC
- 18. 映射属性到数组索引
- 19. 映射数组索引到矩阵
- 20. Padrino如何映射:索引到'/'?
- 21. Visual Basic编号映射
- 22. Java按唯一索引号排序值
- 23. matlab反向映射索引
- 24. 映射排序索引
- 25. 将唯一的16位数字ID映射到唯一的字母数字ID
- 26. 将iphone uuid映射到电话号码
- 27. 将专长重要性的索引映射到数据框中的列索引
- 28. 如何将动态配置文件编号映射到servlet?
- 29. SQL唯一索引
- 30. SQL:唯一索引