1

我在 C# 中有以下结构来表示图形边缘：

struct Edge
{
    public Edge(int leftA, int leftB, int leftC, int leftD, int rightA, int rightB, int rightC, int rightD)
    {
        LeftIdA = leftA;
        LeftIdB = leftB;
        LeftIdC = leftC;
        LeftIdD = leftD;

        RightIdA = rightA;
        RightIdB = rightB;
        RightIdC = rightC;
        RightIdD = rightD;
    }

    public readonly int LeftIdA;
    public readonly int LeftIdB;
    public readonly int LeftIdC;
    public readonly int LeftIdD;

    public readonly int RightIdA;
    public readonly int RightIdB;
    public readonly int RightIdC;
    public readonly int RightIdD;
}

并且需要在 HashSet 中存储很多（大约 500 万），所以没有重复。GetHashCode 的一个好的实现是什么，所以它针对速度进行了优化？

我试图将每个 id 的 4 位存储在返回的整数中，如下所示：

    public override int GetHashCode()
    {
        int A = LeftIdA & 0xF;
        int B = LeftIdB & 0xF;
        int C = LeftIdC & 0xF;
        int D = LeftIdD & 0xF;

        int E = RightIdA & 0xF;
        int F = RightIdB & 0xF;
        int G = RightIdC & 0xF;
        int H = RightIdD & 0xF;

        int result = A;
        result = (result << 4) | B;
        result = (result << 4) | C;
        result = (result << 4) | D;
        result = (result << 4) | E;
        result = (result << 4) | F;
        result = (result << 4) | G;
        result = (result << 4) | H;

        return result;
    }

但这比将项目添加到列表中要慢 80%。

4

3 回答 3

1

GetHashCode 的一个好的实现是什么，所以它针对速度进行了优化？

由于您的所有字段都是只读的，因此最好的选择可能是在构造函数中预先计算哈希码，然后从GetHashCode.

要预先计算哈希码，您可以使用 Guffa 答案中的公式。

于 2013-07-15T15:33:27.947 回答
0

添加到HashSet将需要更长的时间，这不是因为实施中的任何错误策略 GetHashCode()。事实上，这个实现看起来相当不错。AHashSet必须在里面做各种疯狂的废话，例如设置水桶并将东西放入其中。

性能提升在于查找哈希集中的元素。尝试将 500 万个不同的项目添加到列表和哈希集中，看看哪个容器能够更快地告诉你它是否包含特定的边缘。那时您可能愿意支付不到两倍的设置时间。

于 2013-07-14T23:41:56.377 回答
0

为了达到最佳效果，散列码应该尽可能少地发生冲突，即产生尽可能多的散列码。

尝试生成哈希码，以便使用来自所有成员的所有数据：

public override int GetHashCode() {
  return
    LeftIdA ^ LeftIdB ^ LeftIdC ^ LeftIdD ^
    RightIdA ^ RightIdB ^ RightIdC ^ RightIdD;
}

与素数相乘可以提供非常好的分布，因此您应该测试在您的情况下是否可以提供更好的性能：

public override int GetHashCode() {
  return
    ((((((LeftIdA * 251 + LeftIdB) * 251 + LeftIdC) * 251 +
    LeftIdD) * 251 + RightIdA) * 251 + RightIdB) * 251 +
    RightIdC) * 251 + RightIdD;
}

注意：确保您还为结构提供了优化的相等比较。默认实现将使用反射来确定要比较的所有成员，因此非常慢。

编辑：

我做了一些测试，通过第二个实现，我可以在大约两秒内向 HashSet 添加 500 万个项目。

于 2013-07-15T00:04:13.600 回答