存储整数的java HashMap替代方案

Question

我有一个小的整数集（大范围）。我需要能够在0（1）处查询此数据结构，并说明集合中是否存在整数。我目前正在使用Java&；科尔特开放地图。 我有很多这样的OpenInthintAshMaps数据结构，每个都包含5-15个整数。我的查询量很大。我只关心整数的存在——我不关心为键存储值。是否有其他表示或更快的方法来帮助解决此问题

Answer 1

恐怕我不是专家，但我认为很难实现真正的O（1）查找。不过，您可能想看看某种完美的哈希。如果这些集合很小，那么您可能有机会为它们生成一个“完美”的哈希函数，即集合中的项目之间不会发生冲突。这样就可以进行O（1）查找——取整数，对其进行散列，散列会将您精确带到一个位置，然后进行一次比较，以检查整数是否在集合内或外。您只需要检查一次，因为与不完全散列不同，集合中的任何内容都不会发生冲突（内部和外部的内容可能会发生冲突），所以您只需要检查表中的一个单元格，查看集合中是否有整数。这应该是O（1）查找，但计算此类哈希函数的成本可能很高，并且哈希函数本身可能比通用哈希函数昂贵得多（尽管仍然是O（1））。我完全没有在Java中使用它们的经验，但JPerf似乎有为任何类型的Java对象生成它们的方法，我想您可能可以对这些方法进行修改，以专门用于基本INT（JPerf是GPLv2）

http://www.anarres.org/projects/jperf/

http://en.wikipedia.org/wiki/Hash_function#Minimal_perfect_hashing

Answer 2

有了这么小的“n”，我不会根据结构的复杂性来做决定；我会分析一下，看看什么是最快的

在n的某个特定值内，一个ц（log（n））算法可能比一个ц（1）算法更快。ц符号只是告诉您算法的规模。事实上，如果你有很多这样的地图，你可能更担心空间效率

Answer 3

对于10个数字，哈希集和树集的性能大致相同——在我的旧机器上大约为10^7

import java.util.*;
public class Main {
    int n = 10;
    Random random = new Random();
    Set<Integer> hashSet = new HashSet<Integer>(n);
    Set<Integer> treeSet = new HashSet<Integer>(n);
    {
        List<Integer> numbers = new LinkedList<Integer>();
        for (int i = 0; i < n; i++)
            numbers.add(random.nextInt());
        System.out.println(numbers);
        hashSet.addAll(numbers);
        treeSet.addAll(numbers);
        System.out.println(numbers);
    }
    int hits, misses;
    void init() {

    }
    long time(Set<Integer> set, int n) {
        long t0 = System.currentTimeMillis();
        for (int i = 0; i < n; i++)
            if (set.contains(random.nextInt())) hits++;
            else
                misses++;
        return System.currentTimeMillis() - t0;
    }
    void print(long dt, int n, String set) {
        System.out.println(set + " " + n + " trials in " + dt + " ms. = " + 1000. * n / dt + "trials/sec.");
    }
    public static void main(String[] args) {
        int trials = 10000000;
        long dt=0;
        for (int i = 0; i < 10; i++) {
            Main main = new Main();
            dt = main.time(main.hashSet, trials);
            main.print(dt, trials, "hashSet");
            dt = main.time(main.treeSet, trials);
            main.print(dt, trials, "treeSet");
        }
    }
}