【C#】インデックスが取れる固定長辞書

# はじめに
<!-- 発端や概要を記載 -->
固定長のペア配列KeyValuePair\<TKey, TValue>[] とDictionary\<TKey, TValue>の良いとこ取りをしたかった。
以下パブリックドメインです。
# 目次
<!-- タイトルとアンカー名を編集 -->
1. [使い方](#Chapter1)
2. [実装](#Chapter2)
<!-- 各チャプター -->
<a id="#Chapter1"></a>
# 使い方
使い方です。
```C#
//Keyはclass,Valueはなんでもよい。
private KeyValuePair<string, string>[] array=new KeyValuePair<string, string>[]{ new ("何か",値),};
public void Test() {
    var dict=new FixedArrayDictionary(array);
    var tValue=dict["何か"];
    if(dict.TryGetIndex("何か",out int index){
        Debug.Assert(tValue==dict[index].Value);
    }

    foreach(var pair in dict){
         Debug.Log(pair.Key.ToString());
         Debug.Log(pair.Value.ToString());
    }
}
```

<a id="#Chapter2"></a>

# 実装
固定長というアイデアはneue ccさんの[FixedTypeKeyHashtable](https://github.com/neuecc/MicroResolver/blob/master/src/MicroResolver/Internal/FixedTypeKeyHashtable.cs)から得ました。
neue ccさん曰く「ハヤイデス。」。
&を使うとかも使わせていただきました。

Bucket配列をハッシュ値でとるのは一般的なHashTableと同様ですが、実際にはペアとBucketは結びついていないという特徴があります。
```C#
public class FixedArrayDictionary<TKey, TValue> where TKey : class {

    private readonly IntRange[] _ranges;
    private readonly KeyValuePair<TKey, TValue>[] _pairs;
    private readonly int _indexFor;
    public int Length => _pairs.Length;
    private IEqualityComparer<TKey> _comparer;
    public FixedArrayDictionary(KeyValuePair<TKey, TValue>[] pairs,IEqualityComparer<TKey> comparer=null,
     float loadFactor = 0.75f) {
        _comparer= comparer ?? EqualityComparer<TKey>.Default;
     
        var initialCapacity = (int) (pairs.Length / loadFactor);
        var capacity = 1;
        while (capacity < initialCapacity) {
            capacity <<= 1;
        }

        _indexFor = capacity - 1;
        var hashes = new int[pairs.Length];
        _ranges = new IntRange[capacity];
        for (int i = 0; i < pairs.Length; i++) {
            var hash = ( pairs[i].Key.GetHashCode()&_indexFor);
            hashes[i] = hash;
            _ranges[hash].length += 1;
        }

        var lastStart = 0;
        for (var i = 0; i < _ranges.Length; i++) {
            _ranges[i].start = lastStart;
            lastStart += _ranges[i].length;
        }

        _pairs = new KeyValuePair<TKey, TValue>[pairs.Length];
        Sort(hashes, pairs, _pairs, _ranges);
    }

    public TValue this[TKey key] {
        get {
            var range = _ranges[ key.GetHashCode()&_indexFor];
            for (int i = range.start; i < range.start + range.length; i++) {
                if (_pairs[i].Key.Equals(key)) return _pairs[i].Value;
            }

            throw new KeyNotFoundException(key.ToString());
        }
    }
    public KeyValuePair<TKey,TValue> this[int index] => _pairs[index];
    
    
    public bool TryGetValue(TKey key, out TValue value) {
        var range = _ranges[key.GetHashCode()&_indexFor];
        for (int i = range.start; i < range.start + range.length; i++) {
            if (_comparer.Equals(_pairs[i].Key,key)) {
                value = _pairs[i].Value;
                return true;
            }
        }

        value = default;
        return false;
    }
    public bool TryGetIndex(TKey key, out int index) {
        var range = _ranges[key.GetHashCode()&_indexFor];
        for (int i = range.start; i < range.start + range.length; i++) {
            if (_comparer.Equals(_pairs[i].Key,key)) {
                index = i;
                return true;
            }
        }
        index = -1;
        return false;
    }


    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() {

        return _pairs.AsEnumerable().GetEnumerator();
    }

    private static void Sort(int[] hashes, KeyValuePair<TKey, TValue>[] source, KeyValuePair<TKey, TValue>[] dest,
        IntRange[] ranges) {
        for (int i = 0; i < source.Length; i++) {
            var hash = hashes[i];
            var range = ranges[hash];
            var targetIndex = range.start;
            while (dest[targetIndex].Key!=default) {
                ++targetIndex;
            }
            dest[targetIndex] = source[i];
        }
    }

    private struct IntRange {
        public int start;
        public int length;

        public IntRange(int start, int length) {
            this.start = start;
            this.length = length;
        }

        public override string ToString() {
            return '(' + start.ToString() + ',' + length.ToString() + ')';
        }
    }
}
```
ハッシュの衝突した範囲を持つ配列を使ってハッシュ値でソートされた配列をO(1)の範囲で線形探索、つまりO(1)のオーダーで検索を行います。
Dictionaryよりも遅い理由はないし、実際速く、先ほど挙げた[FixedTypeKeyHashtable](https://github.com/neuecc/MicroResolver/blob/master/src/MicroResolver/Internal/FixedTypeKeyHashtable.cs)と(IEqualityComparer\<TKey>を使わないように置き換えた場合)パフォーマンスは同じです。
ソートも累積分布を用いたソートなので、(調べてないですが)速いはずです。

<a id="#reference"></a>
# 参考文献
- [2017年を振り返る](https://neue.cc/2017/)
- [FixedTypeKeyHashtable](https://github.com/neuecc/MicroResolver/blob/master/src/MicroResolver/Internal/FixedTypeKeyHashtable.cs)