哈希的替代方法可用于快速比较以避免冲突

Question

我正在实现一个缓存表，以避免执行从一组描述对象的参数创建通用对象的昂贵操作。一旦请求了对象，就会计算这些参数的哈希，并查询包含已创建对象的Dictionary以检查是否已创建副本，在这种情况下，它返回而不需要再次创建它。

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

除了哈希之外，还有什么解决方案可以解决这个缓存问题，或者可以使用不同的哈希来避免冲突？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类更新了ObjectDescriptor类：

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位，这个解决方案仍然会有冲突，但它对我来说很有效，因为许多字段只有bools或Enum，值很少，这样组合非常有益。