首頁>Program>source

EnumerableObject : IEnumerable<Foo>

包裹一个 List<Foo>

如果 EnumerableObject a.SequenceEquals( EnumerableObject b) ,那麼它们相等。

因此,一个 GetHashCode 必须執行.問题在於,對列表中的每个元素进行XOR運算,將為所有具有所有元素且仅具有相同元素的列表返迴相同的雜湊碼,而与順序無關.就其工作而言,這還可以,但是会匯致许多冲突,這会减慢檢索速度,等等。

什麼是好快速的 GetHashCode

最新回復
  • 5月前
    1 #

    我將以与通常組合雜湊碼的方式相同的方式进行操作-加法和乘法:

    public override int GetHashCode()
    {
        unchecked
        {
            int hash = 19;
            foreach (var foo in foos)
            {
                hash = hash * 31 + foo.GetHashCode();
            }
            return hash;
        }
    }
    

    (請註意,在將雜湊表用作任何描述的雜湊表中的键之後,您不應在列表中添加任何內容,因為雜湊將發生變化。這還假定没有空條目-如果可能的话, 是的,您需要考虑這一點。)

    need

    首先,仔细檢查您是否完全需要雜湊碼.您是否要將這些列表放入雜湊對映結構(例如字典,雜湊集等)中? 如果没有,那就算了。

    現在,假設您的意思是EnumerableObject已覆盖 Equals(object) (因此希望也可以實現 IEquatable<EnumerableObject> ),出於某種原因,這確實是必要的.您想在速度与位元分佈之間取得平衡。

    一个好的起點是多加或Shift + xor:

    public override int GetHashCode()
    {
        int res = 0x2D2816FE;
        foreach(var item in this)
        {
            res = res * 31 + (item == null ? 0 : item.GetHashCode());
        }
        return res;
    }
    

    (這假設您使用item.Equals()进行序列相等性比较,如果您使用的是IEqualityComparer的等值項,則需要呼叫其雜湊碼。)

    从那裏我们可以優化。

    如果不允许使用null專案,請删除null檢查(請註意,如果確實找到了null,則会丟擲代碼)。

    如果非常大的列表很常见,我们需要减少檢查的數量,同時尽量避免造成大量冲突.比较以下不同的實現:

    public override int GetHashCode()
    {
        int res = 0x2D2816FE;
        int max = Math.Min(Count, 16);
        for(int i = 0, i != max; ++i)
        {
            var item = this[i];
            res = res * 31 + (item == null ? 0 : item.GetHashCode());
        }
        return res;
    }
    public override int GetHashCode()
    {
        int res = 0x2D2816FE;
        int min = Math.Max(-1, Count - 16);
        for(int i = Count -1, i != min; --i)
        {
            var item = this[i];
            res = res * 31 + (item == null ? 0 : item.GetHashCode());
        }
        return res;
    }
    public override int GetHashCode()
    {
        int res = 0x2D2816FE;
        int step = Count / 16 + 1;
        for(int i = 0, i < Count; i += step)
        {
            var item = this[i];
            res = res * 31 + (item == null ? 0 : item.GetHashCode());
        }
        return res;
    }
    

    每一个都会限製所檢查專案的总數,這会加快執行速度,但会帶来質量较差的雜湊值.哪个(如果有的话)最好取決於是否更可能以相同的開始或相同的結束。

    更改上面的數字16会調整餘額; 越小越快,但散列質量越高,散列冲突的风险越低。

    編輯:現在您可以使用我的SpookyHash v。2的實現:

    public override int GetHashCode()
    {
      var hasher = new SpookyHash();//use methods with seeds if you need to prevent HashDos
      foreach(var item in this)
        hasher.Update(item.GetHashCode());//or relevant feeds of item, etc.
      return hasher.Final().GetHashCode();
    }
    

    与mult + add或shift + xor相比,它建立的分佈要好得多,而且速度特別快(尤其是在64位程序中,因為该演算法针對该演算法进行了優化,尽管它在32位上也很好用).

  • 5月前
    2 #

    .GetHashCode() 方法通常只返迴基於物件引用(指標地址)的雜湊值.這是因為計算可列舉列表中每个專案的雜湊碼可能会非常耗時.与其覆盖現有的行為,不如使用擴充套件方法,仅在需要確定性確定雜湊碼的地方使用擴充套件方法:

    public static class EnumerableExtensions
    {
        public static int GetSequenceHashCode<TItem>(this IEnumerable<TItem> list)
        {
            if (list == null) return 0;
            const int seedValue = 0x2D2816FE;
            const int primeNumber = 397;
            return list.Aggregate(seedValue, (current, item) => (current * primeNumber) + (Equals(item, default(TItem)) ? 0 : item.GetHashCode()));
        }
    }
    

  • c#:同時播放两个声音
  • android巢狀列表视圖