java - 整数域到定域映射数组的应用与实现

Question

假设给定了一个可以占据整个整数空间的整数数组。但是，我想将其映射到固定范围。

例如: {1, 5, 38, 5, 2^32-1} ---> {1, 2, 3, 2, 4}请注意重复的元素值“5”及其映射数组。与顺序无关。

除了分域树(分域树需要 1..N 的范围)之外，还有其他应用吗？

一种方法是，

int[] map( int[]  a) {
    int[] transArr = new int[a.length];
    Map<Integer,Integer> posValueMap = new HashMap<Integer,Integer>();
    for(int i= 0 ; i < a.length; i++) {
       if(!posValueMap.contains(i))
          posValueMap.put(a[i], i);
    }
    for(int i= 0 ; i < transArr.length; i++) {
        transArr[i] = posValueMap.get(a[i]);
    }
    return transArr;
}

是否有更简单的方法来使用不同的算法或函数式编程构造来实现这一目标？

Answer 1

看来你需要某种 perfect hashing .

最小完美散列函数将 N 个不同元素的集合映射到 0..N-1 或 1..N 范围内的 N 个整数键，如您所愿。

(有 MPH 的开源库)