C# user-defined class as Dictionary<> key - KBDAHOLIC

自分で作った class を System.Collections.Generic.Dictionary<TKey, TValue> の TKey に使いたい、かつその class の特性として 2 つの objcect が同値かどうかが参照等価でない場合以下の手順を踏まないといけない。

System.IEquatable<T> から派生させて public bool Equals(T other) method を実装する
- その class の instance 、つまり object の内部状態を比較して同値かどうか決定すればいい。
- すでにある key が登録されているかを調べるために使われるぽい。
public bool Object.Equals(object obj) を override する。
- obj の型が自作 class と同一かどうか調べて同じなら上で実装したのを呼び出し違うなら false を返す。
- 多分そんなに使われないはず。
public int Object.GetHashCode() を override する
- Equals() method で判定に使った object member の XOR をとればいいらしい。なんで XOR なのかがよくわからないんだけど http://efreedom.com/Question/1-2334218/XOR-Often-Used-Java-HashCode-Another-Bitwise-Operators-Used-Rarely によると AND や OR に比べて bit がバラけるから一様分布になりやすくて素晴らしいらしい。
- 名前のとおり hash を計算する method 。そして Dictionary<> は hash table なのでこの method を使って value を格納するための場所、いわゆる index key を生成するわけだ。

と、これだけじゃわからんので source 。

/*
 * Pair.cs
 *  std::pair in C++
 *
 * by janus_wel<janus.wel.3@gmail.com>
 * This source code is in public domain, and has NO WARRANTY.
 * */

namespace Utility
{
    /// <summary>
    /// pair
    /// </summary>
    /// <typeparam name="T">first type</typeparam>
    /// <typeparam name="U">second type</typeparam>
    public class Pair<T, U> : System.IEquatable<Pair<T, U>>
    {
        /// <summary>
        /// accessor for first element
        /// </summary>
        public T First { get; set; }

        /// <summary>
        /// accessor for second element
        /// </summary>
        public U Second { get; set; }

        /// <summary>
        /// default constructor
        /// </summary>
        public Pair() { }

        /// <summary>
        /// initialize constructor
        /// </summary>
        /// <param name="first">first value</param>
        /// <param name="second">second value</param>
        public Pair(T first, U second)
        {
            First = first;
            Second = second;
        }

        /// <summary>
        /// check equivalence
        /// </summary>
        /// <param name="other">test object</param>
        /// <returns>true if this and object are equivalent, otherwise false</returns>
        public bool Equals(Pair<T, U> other)
        {
            return this.First.Equals(other.First) && this.Second.Equals(other.Second);
        }

        /// <summary>
        /// check equivalence
        /// </summary>
        /// <param name="obj">test object</param>
        /// <returns>true if this and object are equivalent, otherwise false</returns>
        public override bool Equals(object obj)
        {
            Pair<T, U> other = obj as Pair<T, U>;
            return (other != null) ? Equals(other) : false;
        }

        /// <summary>
        /// calculates hash
        /// </summary>
        /// <returns>hash</returns>
        public override int GetHashCode()
        {
            return this.First.GetHashCode() ^ this.Second.GetHashCode();
        }
    }
}

と定義しておいて、

using System.Diagnostics;
using System.Collections.Generic;

namespace PairTest
{
    class Program
    {
        static void Main(string[] args)
        {
            Utility.Pair<int, int> a = new Utility.Pair<int, int>();
            a.First = 3;
            a.Second = 4;
            Utility.Pair<int, int> b = new Utility.Pair<int, int>(3, 4);

            // a and b are equivalent
            Debug.Assert(a.Equals(b));

            Dictionary<Utility.Pair<int, int>, int> dict = new Dictionary<Utility.Pair<int, int>, int>();
            dict.Add(a, 4);
            dict[b] = 10;

            // keys, a and b, are equivalent, so value was rewritten above line
            Debug.Assert(dict[a] == 10);

            b.First = 5;

            // now, b is not contained in dict as a key
            Debug.Assert(dict.ContainsKey(b) == false);
        }
    }
}

こんな感じで test する。 hash table の key を new するとかちょっとキモイけどそういう言語なので仕方ない。あー Pair<> を使って C# の standard interface だとかに慣れようか。教材にちょうどいいかもしれん。とすると github あたりに上げといたほうがいいか… ? まぁいいやそのうちやろう。

なんか C# はけっこう duck typing な言語みたい。そこらへんを本質的に表してるのが「制約」なんだけどこっちもそのうち。