-1

我想在 C# 中实现一个用于双精度的向量类，并且需要重写Equals，GetHashCode因此我可以使用我的向量类作为字典中的键或使用 HashSets。由于我需要对相等有一定的容忍度，我知道没有办法实现传递的 Equals 方法和相应的 GetHashCode 方法。

我偶然发现了一个类似线程的答案：https ://stackoverflow.com/a/580972/5333340

而且我想知道，有没有办法改变 C# 中 HashSet / Dictionaries 的查找行为，使其不仅检查一个桶，而且检查几个桶？

或者是否有一些类对 C# 有这种行为？

4

1 回答 1

0

由于 HashSet 不提供自定义存储桶搜索行为的方法，因此我编写了一个自定义类来执行多个存储桶搜索。包括一个实际使用的示例：3 维向量类。

// Implementing this interface introduces the concept of neighbouring buckets.
public interface IHasNeighbourConcept
{
    int[] GetSeveralHashCodes();
    // The returned int[] must at least contain the return value of GetHashCode.
}

// Custom HashSet-like class that can search in several buckets.
public class NeighbourSearchHashSet<T> where T : IHasNeighbourConcept
{
    // Internal data storage.
    private Dictionary<int, List<T>> buckets;

    // Constructor.
    public NeighbourSearchHashSet()
    {
        buckets = new Dictionary<int, List<T>>();
    }

    // Classic implementation utilizing GetHashCode.
    public bool Add(T elem)
    {
        int hash = elem.GetHashCode();

        if(!buckets.ContainsKey(hash))
        {
            buckets[hash] = new List<T>();
            buckets[hash].Add(elem);
            return true;
        }

        foreach(T t in buckets[hash])
        {
            if(elem.Equals(t))
                return false;
        }

        buckets[hash].Add(elem);
        return true;
    }

    /// Nonclassic implementation utilizing GetSeveralHashCodes.
    public bool Contains(T elem)
    {
        int[] hashes = elem.GetSeveralHashCodes();

        foreach(int h in hashes)
            foreach(T t in buckets[h])
                if(elem.Equals(t))
                    return true;
        return false;
    }


}


// A 3-dimensional vector class. Since its Equals method is not transitive,
// there can be vectors that are considered equal but have different HashCodes.
// So the Contains method of HashSet<Vector> does not work as expected.
public class Vector : IHasNeighbourConcept
{
    private double[] coords;
    private static double TOL = 1E-10;
    // Tolerance for considering two doubles as equal

    public Vector(double x, double y, double z)
    {
        if(double.IsNaN(x) || double.IsInfinity(x) ||
           double.IsNaN(y) || double.IsInfinity(y) ||
           double.IsNaN(z) || double.IsInfinity(z))
            throw new NotFiniteNumberException("All input must be finite!");

        coords = new double[] { x, y, z };
    }

    // Two vectors are equal iff the distance of each
    // corresponding component pair is significantly small.
    public override bool Equals(object obj)
    {
        if(!(obj is Vector))
            throw new ArgumentException("Input argument is not a Vector!");

        Vector other = obj as Vector;

        bool retval = true;
        for(int i = 0; i < 2; i++)
            retval = retval && (Math.Abs(coords[i] - other.coords[i]) < TOL);

        return retval;

    }

    // The set of all Vectors with the same HashCode
    // is a cube with side length TOL.
    // Two Vectors considered equal may have different
    // HashCodes, but the x, y, z intermediate values
    // differ by at most 1.
    public override int GetHashCode()
    {
        int x =(int) Math.Truncate(coords[0] / TOL);
        int y =(int) Math.Truncate(coords[1] / TOL);
        int z =(int) Math.Truncate(coords[2] / TOL);
        return x + 3*y + 5*z; // The purpose of the factors is to make
                              // permuting the coordinates result
                              // in different HashCodes.
    }

    // Gets the HashCode of the given Vector as well as the 26
    // HashCodes of the surrounding cubes.
    public int[] GetSeveralHashCodes()
    {
        int[] hashes = new int[27];
        int x =(int) Math.Truncate(coords[0] / TOL);
        int y =(int) Math.Truncate(coords[1] / TOL);
        int z =(int) Math.Truncate(coords[2] / TOL);

        for(int i = -1; i <= 1; i++)
            for(int j = -1; j <= 1; j++)
                for(int k = -1; k <= 1; k++)
                    hashes[(i+1)+3*(j+1)+9*(k+1)] = (x+i) + 3*(y+j) + 5*(z+k);
        return hashes;
    }
}

编辑：

上面的实现扩展了 HashSet 的概念，即使没有传递Equals方法，Contains集合的方法也能正常工作。它之所以有效，是因为Contains我们不需要知道我们寻找的元素所在的确切等价类。

但是，对于字典，它是不同的。我们确实需要得到正确的等价类（即hashCode），否则我们会得到不同的图像。因此，不同的 HashCode 必须导致元素不相等。

于 2016-07-04T17:16:14.517 回答