« C++/C#/JAVA コレクション比較 【インデックスによる要素アクセス】 | トップページ | C++のハッシュテーブル hash_map »

2008年12月12日 (金)

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クラスも拡張)することによる。
      2種類のoperator()をオーバーロードする
   
   C#のDictionaryの場合。
   IEqualityComparerインターフェースを実装することによる。
      Equals()とGetHashCode()の2つのメソッドを実装する。
   
   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> 木構造で要素を保持
   

« C++/C#/JAVA コレクション比較 【インデックスによる要素アクセス】 | トップページ | C++のハッシュテーブル hash_map »

パソコン・インターネット」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック


この記事へのトラックバック一覧です: C++/C#/JAVA コレクション比較 【ハッシュテーブルの比較概要】:

« C++/C#/JAVA コレクション比較 【インデックスによる要素アクセス】 | トップページ | C++のハッシュテーブル hash_map »