2014年10月24日

コレクション系インターフェース 早見表

コレクション系インターフェースの型パラメータの共変性、および、実装されるメソッド、プロパティの早見表。
※IReadOnly~ は .NET 4.5 から導入
※非ジェネリックはもう使わないと思うので省略

共変 <out T>
メソッド プロパティ
GetEnumerator()
Add( T )
Clear()
Contains( T )
CopyTo( T[], int )
Remove( T )
IndexOf( T )
Insert( int, T )
RemoveAt( int )
Count { get; }
IsReadOnly { get; }
this[ int ] { get; }
this[ int ] { set; }
IEnumerable<T>
ICollection<T>
IList<T>
IReadOnlyCollection<T>
IReadOnlyList<T>

メソッド プロパティ
Add( TKey, TValue )
ContainsKey( TKey )
Remove( TKey )
TryGetValue( TKey, out TValue )
this[ TKey ] { get; }
this[ TKey ] { set; }
Keys { get; }
Values { get; }
IDictionary
<TKey, TValue>
他の項目は ICollection<T> 参照
Keys と Values は ICollection<T>
IReadOnlyDictionary
<TKey, TValue>
他の項目は IReadOnlyCollection<T> 参照
Keys と Values は IEnumerable<T>

雑感

元々あまり使われなかっただろう IsReadOnly プロパティは、IReadOnly~ インターフェースが導入されたため、完全に要らない子に・・・

IReadOnlyDictionary の Keys/Values プロパティの戻り値が IReadOnlyCollection<T> ではなく IEnumerable<T> なのは、Count プロパティの使用頻度と実装のし易さあたりが理由?
確かに Keys や Values の Count プロパティなんてほぼ使わないだろうし、IEnumerable<T> だと yield で簡単実装できるから、いい判断だと思う。
逆に、IDictionary の Keys/Values プロパティの戻り値 ICollection<T> は機能が過剰だし、実装も面倒。

.NET 4.5 からは IReadOnly~ を積極的に使っていこう・・・かな

2014年10月10日

SQL Server IDENTITY 列 1 個のテーブルの更新方法

ID 生成専用として、IDENTITY 列 1 個だけのテーブルを用意したりする。

CREATE TABLE IdGenerator (
  Id int IDENTITY(1,1)
);

これを更新(INSERT)する方法。

INSERT INTO IdGenerator DEFAULT VALUES;

-- 同時に id を取得するなら
INSERT INTO IdGenerator OUTPUT inserted.Id DEFAULT VALUES;

INSERT なので、1 列だけだがデータは溜まっていく。
気になる場合は、INSERT と同時に消すか、削除バッチなどで。

参考URL

2014年10月3日

Dictionary<TKey, TValue> の実装について

Dictionary<TKey, TValue> の実装について、ソースからの説明。
知ってるといいことあるかもしれない・・・

Dictionary の本体


// Dictionary の要素の構造体
// KeyValuePair をそのまま保持しているわけではない
private struct Entry {
    public int hashCode;  // 正の数にしたハッシュコード(0~7FFFFFFF)、-1 は未使用
    public int next;      // buckets 位置が同じ要素の次インデックス、-1 は次の要素無し
    public TKey key;      // キー
    public TValue value;  // 値
}

// ハッシュコード -> entries インデックスのマップ
// 実際は、正のハッシュコード % buckets.Length で buckets のサイズに合わせる
private int[] buckets;

// 要素の配列
private Entry[] entries;

ソースだけだとピンとこないかもしれないので、追加処理を図で。
Dictionary Add image
IEqualityComparer<TKey>.GetHashCode() でキーからハッシュコードを求める
0x7FFFFFFF との論理積で、ハッシュコードを正の数にする

ハッシュコードを buckets 位置 B に変換(剰余を求める)

buckets[B] に entries の次の未使用インデックス E を設定

entries[E] に hashCode, key, value を設定

ちなみに、ハッシュコードの衝突(buckets 位置が使用済)が起こった場合。
Dictionary Add image (collision)
buckets 位置 B を求める

buckets[B] に entries の次の未使用インデックス E を設定

entries[E] に hashCode, key, value を設定、next に buckets[B] の元の値を設定

Dictionary の容量

ハッシュテーブルの容量については素数派と 2^n 派が存在するが、Dictionary では素数を採用している。
※素数のメリットはハッシュ関数が多少ダメでも衝突が起こりにくいこと、2^n のメリットは剰余の計算が速いことらしい。

Dictionary で採用される素数については、HashTable ソースの HashHelpers.primes 参照。
HashHelpers.primes 以降の素数は、その場で計算される。(HashHelpers.GetPrime 参照)

Dictionary コンストラクタの capacity 引数で素数以外を指定しても、それ以上の素数に切り上げられる。
容量拡張が発生するタイミングは、entries を使い切った場合で、現在の容量×2 以上の素数に切り上げられる。
(buckets も同時に拡張される)

Dictionary の列挙

entries の順序どおり列挙される。
entries は先頭から埋められていくので、Add とインデクサによる追加・変更のみならば、Dictionary への追加順で列挙される。

Remove による削除が発生した場合、次の追加処理では、削除された領域を先に使うため、追加順による列挙ではなくなる。
※複数削除の場合は、Entry.next を利用して空き領域リストが構築される

[Remove → Add 後の列挙]

static class TestDic
{
    static void Main()
    {
        var dic = new Dictionary<string, int>();
        var val = 0;
        foreach( var c in "abc" ) dic.Add(c.ToString(), val++);
        Console.WriteLine("ADD a b c");
        Console.WriteLine(string.Join(" ", dic));

        dic.Remove("b");
        Console.WriteLine("REMOVE b");
        Console.WriteLine(string.Join(" ", dic));

        dic.Add("d", val++);
        Console.WriteLine("ADD d");
        Console.WriteLine(string.Join(" ", dic));
    }
}
[結果]
ADD a b c
[a, 0] [b, 1] [c, 2]
REMOVE b
[a, 0] [c, 2]
ADD d
[a, 0] [d, 3] [c, 2]

また、列挙時に追加・変更・削除が検知できるよう、version メンバ変数がある。
追加・変更・削除が発生した場合は version をインクリメントして、IEnumerator の MoveNext 時に version が変わっていたら、InvalidOperationException を発生させる。

IEqualityComparer<TKey>

キーのハッシュコードの計算や一致比較を担当する IEqualityComparer<TKey> は、コンストラクタの comparer 引数で指定することができる。
未指定や null を渡した場合は EqualityComparer<TKey>.Default が使用される。
MSDN にある「既定の等値比較子」がこれに該当する。

int や string など基本的な型は EqualityComparer<TKey>.Default で問題ないが、配列や自前のクラスなどは IEqualityComparer<TKey> を自分で用意する必要がある。
※EqualityComparer<T>.Default については、いつか説明予定・・・

ちなみに、値を担当する IEqualityComparer<TValue> はコンストラクタで指定できないため、問答無用で EqualityComparer<TValue>.Default が使用される。
実際に使用されているメソッドは下記。
  • ContainsValue
  • ICollection<KeyValuePair<TKey, TValue>>.Contains
  • ICollection<KeyValuePair<TKey, TValue>>.Remove

EqualityComparer<TValue>.Default で正確な一致比較ができない場合は、これらを使用しない方がいい。