替代散列以进行快速比较以避免冲突

Question

我正在实施缓存 table 以避免必须执行从一组描述它的参数创建通用对象的昂贵操作。请求对象后，将计算这些参数的哈希值，并查询包含已创建对象的字典以检查是否已创建副本，在这种情况下返回它而无需再次创建它。

我的问题在于，由于描述这些对象的参数可能很多，散列函数中的冲突是不可避免的（而且过于频繁），但另一方面，检索这些对象是一项性能关键的操作，并且我无法对所有现有描述进行全面比较以在已创建的对象中进行搜索。我尝试使用许多不同的哈希函数来解决，但由于参数的性质未知，因此结果不可靠。

对于此缓存问题，除了散列之外还有哪些解决方案，或者是否可以以不同方式使用散列来避免冲突？ C#问题描述：

class ObjectDescriptor
{
    // description made of a list of parameters of unknown type
    public object[] Fields;

    // hashing procedure that may have conflicts
    public override int GetHashCode()
    {
        int hash = 1009;
        for (int i = 0; i < Fields.Length; i++)
        {
            unchecked { hash = hash * 9176 + Fields[i].GetHashCode(); }
        }
        return hash;
    }
}

abstract class ObjectCache<T>
{
    private Dictionary<int, T> indexedObjects;

    // this operation is called many times and must be fast
    public T Get(ObjectDescriptor descr)
    {
        T cachedValue;
        if(!indexedObjects.TryGetValue(descr.GetHashCode(), out cachedValue))
        {
            cachedValue = CreateObject(descr);
            indexedObjects[descr.GetHashCode()] = cachedValue;
        }
        return cachedValue;
    }

    // costly operation
    protected abstract T CreateObject(ObjectDescriptor desc);
}

Answer 1

我将保留我最终使用的解决方案。这是基于这样一个事实，即可以通过在可能的情况下将多个字段的全部值存储在单个哈希中来避免冲突：

byte b1 = 42, b2 = 255;
int naiveHash = CombineHash(b1.GetHashCode(), b2.GetHashCode()); // will always have conflicts
int typeAwareHash = b1 << 8 + b2; // no conflicts

要知道一个字段需要多少位，我需要实现 IObjectDescriptorField：

interface IObjectDescriptorField
{
    int GetHashCodeBitCount();
}

然后我用 HashCodeBuilder class 更新了 ObjectDescriptor class:

class ObjectDescriptor
{
    public IObjectDescriptorField[] Fields;

    public override int GetHashCode()
    {
        HashCodeBuilder hash = new HashCodeBuilder();
        for (int i = 0; i < Fields.Length; i++)
        {
            hash.AddBits(Fields[i].GetHashCode(), Fields[i].GetHashCodeBitCount());
        }
        return hash.GetHashCode();
    }
}

HashCodeBuilder 堆叠位直到所有 32 个都被使用，然后像以前一样使用简单的哈希组合函数：

public class HashCodeBuilder
{
    private const int HASH_SEED = 352654597;

    private static int Combine(int hash1, int hash2)
    {
        return ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ hash2;
    }

    private int hashAccumulator;
    private int bitAccumulator;
    private int bitsLeft;

    public HashCodeBuilder()
    {
        hashAccumulator = HASH_SEED;
        bitAccumulator = 0;
        bitsLeft = 32;
    }

    public void AddBits(int bits, int bitCount)
    {
        if (bitsLeft < bitCount)
        {
            hashAccumulator = Combine(hashAccumulator, bitAccumulator);
            bitsLeft = 32;
            hashAccumulator = 0;
        }

        bitAccumulator = bitAccumulator << bitCount + bits;
        bitsLeft -= bitCount;
    }

    public override int GetHashCode()
    {
        return Combine(hashAccumulator, bitAccumulator);
    }
}

如果使用超过 32 位，这个解决方案当然仍然存在冲突，但它对我有用，因为许多字段只有 bool 或 Enums，只有很少的值，这样组合起来非常有好处。

替代散列以进行快速比较以避免冲突

Alternative to hashing for quick comparison to avoid conflicts

c#

hash

caching

dictionary

hashcode