Home > 聞いて欲しい独り言 > JavaのMapとVC++のMap

JavaのMapとVC++のMap

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++のを見てみるか!
・・・
・・・
・・・
テンプレートみづれぇ。めんどくさい!挫折!

以上

Comments:0

Comment Form
Remember personal info

Trackbacks:0

Trackback URL for this entry
http://red-treasure.com/report/wp-trackback.php?p=124
Listed below are links to weblogs that reference
JavaのMapとVC++のMap from コスミー報告書[社外秘]

Home > 聞いて欲しい独り言 > JavaのMapとVC++のMap

Search
Feeds
Meta
 合計:011975
 今日:0102 昨日:0116

Return to page top