JavaのHashMapの実装をちょっとのぞいてみました。
なかなか分かりやすい。さすがJava。
以下ポイント：
・put(key, obj)でkeyからハッシュを求めて、内部配列のインデックスがハッシュ＆配列長のところにobjを入れる。（＆はビット演算ね。）
・内部配列に格納するのはobjそのものではなく、Entry型のクラス。Entryはコンストラクタで古いオブジェクトを受け取り、内部でリストを作成する。このため、上記手順でハッシュの衝突が起きた場合はこのリストを見ていけば同じハッシュを持つオブジェクトが格納されている。
具体的には下記のようなイメージ。
Entry old = table[index];
table[index]= new Entry(key, newObj, old);
・追加した値の数が一定数を超えたら、内部配列のサイズを拡張する。ハッシュの衝突を少なくするため。配列長が大きくなると、ハッシュ＆配列長でマッピングされる整数空間が広がる。拡張するときは新しい配列に古い配列を地道にコピーするしかない。
・get(key)するときはkeyからハッシュを求めて、内部配列からハッシュ＆配列長のところのEntryを取得する。ハッシュがかぶってるオブジェクトがある場合は、取得したEntryがリストを持っているので、keyが完全に一致するものを線形探索で探す。
これなら自分で作れそう。
よし、じゃあVC++のを見てみるか！
・・・
・・・
・・・
テンプレートみづれぇ。めんどくさい！挫折！
以上
