HashMapの容量圧縮について

質問

初期サイズがわからない状態でHashMap(Hashtableでも可）を作成し、HashMapの容量を圧縮する方法などありますか？

ArrayListのTrimToSizeメソッドのようなものがあったらいいのですが、ご存知でしょうか？

回答No.4

KSOH

ユースケースを拝見しましたが、少なくともHashMapを使う限りにおいては質問者さんがおっしゃるようなメモリーの節約の仕方を気にする益はあまりないと思います。

>後は、値の参照だけですので、高速にアクセスできればよく（←このためハッシュを採用）、ハッシューキーの衝突等一切考慮する必要がありません。

いえいえ、衝突はハッシュ法に関して言えば最も重要なファクターなのでユーザが気にしなくいとしてもHashMapの方で大いに気にしています。ハッシュ法はキーの衝突を避けることが性能の確保に繋がりますから。

HashMapに関して言えば内部テーブルの拡張戦略は単純で充填率がload factorを超えたところで次の２のべき乗のサイズに拡張されます。よって、最終的なテーブルのサイズを節約するためには初期サイズの指定は無関係（初期登録時の性能だけに影響）で、load factorにのみ左右されます。運よく登録キー数が２のべき乗より少しだけ小さい数であればload factor=1.0にしてやることでほぼ空きエントリーはなくなります。しかし、２のべき乗より何割か小さい数だとどうしてもそれだけの空きが生じます。結局load factor=1.0と指定したとしても充填率は最悪50%、最良100%です。充填率をそれ以上あがるような使い方（外から制御する方法）はありません。

この何割かの空き領域のサイズが本当に気になるのであればHashMapとは異なる実装のクラスを用いることになります。もしそうしたければHashMapのソースをコピーしてきてtableSizeForなどを書き換えればある程度空きが小さくなるようにできるとは思います。

ただ、ご質問のユースケースでそこまで気にすることもないと思います。

お礼

お礼遅くなりすみません。

ありがとうございます。
英語の質問ページも見ましたが、やはりNo4さんのおっしゃるとおりでした。

回答No.3

ninoue

>アプリケーション起動時に設定ファイルの内容をHashMapに読み込み、以降はHashMapに対して、削除、追加、更新といったことを一切いたしません。

それでしたら設定ファイルのentry数は最初に分るので、それに対応したinitial capacityを指定してHashMapをnewすれば解決するのではと思われます。

default load factor=0.75が標準のようですので、entry数が例えば15000でしたら、次のようにしてみれば良いのではないでしょうか。

HashMap myMap;
....
myMap = new HashMap(20000); // 15000/0.75=20000;

補足

ご回答ありがとうございます。

また、こちらが提供した情報が不足していたようですみません。
現在のロジックでは、設定ファイル読み込みが”逐次処理”のためHashMap作成時にはわからないです。最後の設定値をHashMapに登録した時点でわかるロジックになっています。。。

なので、ご指摘どおり設定ファイルのエントリー数がわかるようにプログラムを修正すればHashMap生成時に要素数を設定できるのですが・・・
ちょっと、そこまでロジックいじるのが面倒だったので、ArrayListのTrimToSizeみたいな便利なメソッドがあれば、１行追加で楽ができると思ってしまいました。

やはり、設定ファイルの要素数をHashMap生成時にわかるように修正するしかないですかね。。。？

回答No.2

KSOH

何故ハッシュ法を使用しているのにテーブルを圧縮しようとするのでしょうか？どういったケースなのかもう少し説明されたほうがよいと思います。

上記の説明を拝見するとArrayListの内部のテーブルサイズとHashMapの内部のテーブルサイズを同列のものとして捉えておられるような印象があります。そのためハッシュ法というのがどういうものなのかを理解されていないようにも見えてしまいます。ハッシュ法ではキーの衝突をなるべくさけるためある程度の空きがある状態で使うのが普通ですので。

例えばもしメモリー使用量を極力少なくしたいという場合ならハッシュ法を用いずに二分探索（あるいは容量が非常に少ないなら線形探索）するようなMapを使うという選択肢もあるかも知れません。ひょっとしたらそういうものを期待されているのでしょうか？

補足

情報が少ない中でのご回答ありがとうございます。

アプリケーション起動時に設定ファイルの内容をHashMapに読み込み、以降はHashMapに対して、削除、追加、更新といったことを一切いたしません。

後は、値の参照だけですので、高速にアクセスできればよく（←このためハッシュを採用）、ハッシューキーの衝突等一切考慮する必要がありません。

ですので、パソコンで動くアプリですが、メモリ使用量を少しでも節約したく、質問ました。優先順位としては動作速度＞メモリ使用率なもので。。。
１番　設定値に高速アクセスすること
２番　メモリ使用量が少ないほうがいい
何かいい方法があればいいなといった感じです。

回答No.1

ninoue

Java Development Kitに同封されているソースを確認してみて下さい。
HashMap の登録Objectエントリ数に応じてHashTableのエントリ数は適当なタイミングで自動調整するようにコントロールされているので、通常の使用方法では容量の圧縮などを気にしないでも良いように調整されています。

殆ど空のHashTable Entryに有効Objectがパラパラと登録されている状態、
或いは複数の同一Hash値に多数のObjectが登録されている状態など、Hash値の種類不足状態、
等がObject登録中等に見つかると、Hash値等のTable再構成が自動的に行われるようです。

java\util\HashMap.java
のソース中のresize()、DEFAULT_LOAD_FACTOR、DEFAULT_INITIAL_CAPACITY
等を確認してみて下さい。

補足

情報が少ない中でのご回答ありがとうございます。

ソースはチラッと読みました。ご指摘どおり、値の更新などあったらハッシュテーブルのサイズが更新されていますが、なにぶん値の更新を一切おこなわないもので、何かいい方法があればいいなと思い質問いたしました。