うにてぃブログ

UnityやUnreal Engineの記事を書いていきます

【C#】GetHashCode をすべて同一にした際に HashSet の Contains は遅くなるのか

GetHashCode の値は HashSet で利用しており検索の高速化に使っていると記述してあったので

GetHashCode の値をすべて同一にした場合と異なるようにした場合で、速度を見てみる

コードは 自作クラスを HashSet に突っ込んでランダムで検索してみる

var loop = 1000;
var list = new List<Value>(loop);
var hash = new HashSet<Value>();
for (var i = 0; i < loop; i++)
{
    var v = new Value(i);
    hash.Add(v);
    list.Add(v);
}
 
UnityEngine.Random.InitState(10);
Profiler.BeginSample("HashTest");
for (var i = 0; i < list.Count + 10; i++)
{
    var index = UnityEngine.Random.Range(0, list.Count);
    hash.Contains(list[index]);
}
Profiler.EndSample();
 
public class Value
{
    public int V;
    public Value(int v)
    {
        V = v;
    }
 
    public override int GetHashCode()
    {
        // もしくは return V;
        return 0;
    }
}

ついでに List で検索した際も比較するためにこれも計測

for (var i = 0; i < list.Count + 10; i++)
{
    var index = UnityEngine.Random.Range(0, list.Count);
    for (var j = 0; j < list.Count; j++)
    {
        if (list[index] == list[j])
            break;
    }
}

結果

GetHashCode 時間 (ms)
同じ値 6.0
違う値 0.2
List で検索 2.0

List のループしての検索よりも時間がかかることが分かった

HashSet を利用する際にはちゃんと GetHashCode の処理は書いたほうがよさそうです