はじめに
固定長のペア配列KeyValuePair<TKey, TValue>[] とDictionary<TKey, TValue>の良いとこ取りをしたかった。
以下パブリックドメインです。
目次
使い方
使い方です。
//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());
}
}
実装
固定長というアイデアはneue ccさんのFixedTypeKeyHashtableから得ました。
neue ccさん曰く「ハヤイデス。」。
&を使うとかも使わせていただきました。
Bucket配列をハッシュ値でとるのは一般的なHashTableと同様ですが、実際にはペアとBucketは結びついていないという特徴があります。
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と(IEqualityComparer<TKey>を使わないように置き換えた場合)パフォーマンスは同じです。
ソートも累積分布を用いたソートなので、(調べてないですが)速いはずです。