是否存在仅存储哈希码而不存储实际对象的数据结构？

Question

我的用例是我正在寻找一个Java中的数据结构，让我看看是否有一个具有相同哈希码的对象（通过调用contains（）），但我永远不需要迭代元素或检索实际对象。 HashSet很接近，但根据我的理解，它仍然包含对实际对象的引用，这将浪费内存，因为我不需要实际对象的内容。我能想到的最好的选择是Integer类型的HashSet只存储哈希码，但我想知道是否有一个内置的数据结构可以完成相同的事情（并且只接受一个类型而不是HashSet type Integer，它将接受任何对象的哈希码）。

Answer 1

Bloom filter可以判断对象是否可以是成员，或者绝对不是成员。您可以控制误报的可能性。每个哈希值映射到一个位。

Guava图书馆提供an implementation in Java。

Answer 2

您可以使用像IntSet这样的基本集合实现来存储哈希码的值。显然，正如其他人提到的那样，假设碰撞不是问题。

Answer 3

如果你想跟踪哈希码是否已经存在并且为了使记忆效率高，那么BitSet可以满足你的要求。

请看以下示例：

  public static void main(String[] args) {
    BitSet hashCodes = new BitSet();
    hashCodes.set("1".hashCode());

    System.out.println(hashCodes.get("1".hashCode())); // true
    System.out.println(hashCodes.get("2".hashCode())); // false
  }

BitSet "implements a vector of bits that grows as needed."。它是一个JDK“内置数据结构”，它不包含“对实际对象的引用”。它只存储“内部相同的哈希码”。

编辑： 正如@Steve在评论中提到的那样，BitSet的实现并不是最有效的内存。但是有一些内存有效的位集实现 - 虽然不是内置的。

Answer 4

没有这样的内置数据结构，因为很少需要这样的数据结构。不过，建立一个很容易。

public class HashCodeSet<T> {

    private final HashSet<Integer> hashCodes;        

    public MyHashSet() {
        hashCodes = new HashSet<>();
    }         

    public MyHashSet(int initialCapacity) {
        hashCodes = new HashSet<>(initialCapacity);
    }         

    public HashCodeSet(HashCodeSet toCopy) {
        hashCodes = new HashSet<>(toCopy.hashCodes);
    } 

    public void add(T element) {
       hashCodes.add(element.hashCode());
    }

    public boolean containsHashCodeOf(T element) {
       return hashCodes.contains(element.hashCode());
    }        

    @Override
    public boolean equals(o: Object) {
        return o == this || o instanceof HashCodeSet && 
                ((HashCodeSet) o).hashCodes.equals(hashCodes);
    }        

    @Override
    public int hashCode() {
        return hashCodes.hashCode(); // hash-ception
    } 

    @Override
    public String toString() {
        return hashCodes.toString();
    }
}