如何将一系列数字哈希到哈希表中的单个位置

Question

基本上我有一个2xN的整数数组,它表示对象位置的哪个位置.然后我有第二个整数数组,我想找到哪个整数落在哪个对象上.例如:

第一个阵列

答:0 - 500

B:501-900

C:901-1055

D:1056 - 9955等

第二阵列:1,999,3,898,55,43,1055,593,525,3099等

这应该返回A,C,A,B,A,A,C,B,B,D等.

我想弄清楚的是,是否有一种方法来使用一些散列函数来散列第一个数组,这样当散列第二个数组时,如果它落在一个对象的范围内,我将得到一个碰撞.任何想法如何做到这一点或如果可能的话？

谢谢!

Answer 1

您可以使用一个NavigableMap.

示例代码：

NavigableMap<Integer, String> map = new TreeMap<Integer, String>();
map.put(0, "A");
map.put(501, "B");
map.put(901, "C");
map.put(1056, "D");

System.out.println(map.floorEntry(1).getValue());
System.out.println(map.floorEntry(999).getValue());
System.out.println(map.floorEntry(3).getValue());
System.out.println(map.floorEntry(898).getValue());

输出：

A C A B

Answer 2

您不能使用散列，但可以对间隔端点进行排序并进行二分搜索。

像这样的东西（在Python中，但希望它对你有意义）：

endpoints = [501, 901, 1056, 9956]
for x in [1, 999, 898, 55, 43, 1055, 593, 525, 3099]:
    print x, 'ABCD'[bisect.bisect_left(endpoints, x)]