C++/C#/JAVA コレクション比較 【ハッシュテーブルの比較概要】

C++/C#/JAVAのハッシュテーブル
stdext::hash_map [VC++2003]
System.Collections.Generic.Dictionary(K,V) [C#2008 Express Edition]
java.util.HashMap<K,V> [J2SE 1.6.0_03]
の比較。（自分の知識を整理するためのメモです。）

各ハッシュテーブルの具体的使い方はそれぞれまとめるとして、ここでは大雑把な比較をまとめてみた。

---

[キー値の比較・キー値のハッシュ値の取得]
   ハッシュテーブルオブジェクトを構築する前に、キー値の同値性チェックまたは大小チェック、およびキー値のハッシュ値を取得する手段を構築しなければならない。
   
   C++のhash_mapの場合。
   stdext::hash_compareクラスを拡張(そのためにstd::lessクラスも拡張)することによる。
      ２種類のoperator()をオーバーロードする
   
   C#のDictionaryの場合。
   IEqualityComparerインターフェースを実装することによる。
      Equals()とGetHashCode()の２つのメソッドを実装する。
   
   JAVAのHashMapの場合。
   キー値のクラスにメソッドを追加することによる。
      equals()とhashCode()

---

[ハッシュテーブルオブジェクトの構築]
   何れの場合もキーと値の型をパラメータとしてハッシュテーブルオブジェクトを構築するが、それに加えて上記のキー値比較・キー値のハッシュ値取得方法も指定する必要がある。
   
   C++のhash_mapの場合。
   stdext::hash_compareクラスの拡張クラスをハッシュテーブルのテンプレートパラメータとして指定する。
   
   C#のDictionaryの場合。
   IEqualityComparerインターフェースの実装クラスオブジェクトをハッシュテーブルのコンストラクタ引数として指定する。
   
   JAVAのHashMapの場合。
   キー値比較・キー値のハッシュ値取得方法はキー値の型定義に含まれているので、ハッシュテーブルの構築時に指定する必要はない。
   

---

[キー対値の登録]
   C++のhash_mapの場合。
   operator[]による
   
   C#のDictionaryの場合。
   Add()メソッドによる
   
   JAVAのHashMapの場合。
   put()メソッドによる

---

[検索と値の取得]
   C++のhash_mapの場合。
   find()メンバー関数でイテレータを取得し、イテレータで値にアクセス
   
   C#のDictionaryの場合。
   ContainsKey()メソッドで検索し、[]インデクサで値にアクセス
   
   JAVAのHashMapの場合。
   get()メソッドで値取得

---

[キー値としてintのような値型を使う]

   C++のhash_mapの場合。
   可能
   
   C#のDictionaryの場合。
   可能
   
   JAVAのHashMapの場合。
   java.lang.Integerクラスなどでキーをラッピングする。

---

[類似データ構造]

   C++のhash_mapの場合。
      std::map 木構造
      std::multimap キー重複可
   
   C#のDictionaryの場合。
      SortedDictionary(K,V) 木構造で要素を保持
      SynchronizedKeyedCollection(K,V) スレッドセーフ
   
   JAVAのHashMapの場合。
      LinkedHashMap<K,V> 要素の順序が挿入順序
      IdentifyHashMap<K,V> キーの同値性(equals)ではなく同一性(==)に基づく
      WeakHashMap<K,V> キーが使われなくなると自動的に削除される
      TreeMap<K,V> 木構造で要素を保持