- Hash table based implementation of the Map interface. This
- implementation provides all of the optional map operations, and permits
- null values and the null key. (The HashMap
- class is roughly equivalent to Hashtable, except that it is
- unsynchronized and permits nulls.) This class makes no guarantees as to
- the order of the map; in particular, it does not guarantee that the order
- will remain constant over time.
ハッシュテーブルをベースにしたMapインターフェースの実装です。
この実装はオプショナルを含めたMapのオペレーションを全て提供します。
null値とnullのキーを許容します。
HashMapは雑に言えば、同期的でないこと、nullを許容することをのぞいてHashtableと等価です。
このクラスはMapの順序を保証しません。時間が経っても順序が一定に保たれることを保証していません。
この実装はハッシュ関数はバケット間に要素が適切に散らばることを仮定し、一般的な操作(get, put)をO(1)のパフォーマンスで提供します。
コレクションビューを超えたイテレーションは、Hashmapインスタンスのキャパシティ+そのサイズ(key-value mappingsの数)に比例する必要があります。
そのため、もしイテレーションのパフォーマンスが重要なのであれば、初期キャパシティを高くしすぎない、(もしくはload factorを低くしすぎない)ことがとても重要です。
HashMapのインスタンスはパフォーマンスに影響する2つのパラメーターを持っています。
初期キャパシティとload factorを低くしすぎない)ことがとても重要です。
キャパシティは、ハッシュテーブルのバケットの数で、初期キャパシティはハッシュテーブルが作られたタイミングのキャパシティのことです。
load factorはキャパシティが自動的に増加するまでにハッシュテーブルがどれくらいまで埋まるかを許容する閾値です。
ハッシュテーブル内のエントリーの数がload factorと現在のキャパシティを超えた時、ハッシュテーブルはリハッシュします。
リハッシュとは、内部のデータ構造の再構築のことです。
ハッシュテーブルはおよそバケットの数の2倍となります。
一般的なルールとして、デフォルトのload factorは時間と容量のコストの間で良いトレードオフを提供します。
高い値はスペースのオーバーヘッドを減らしますが、参照時のコストは増加します。(参照時のコストはget,putを含むHashMapのほとんどの操作に影響します)
- 🍙 高すぎるとギチギチまで詰める感じになる?
- 🍙 参照時のコストが上がる理由がよくわからない
予期されるマップにおけるエントリの数とそのload factorは、リハッシュの操作回数を最小化するように初期キャパシティがセットされる時に考慮されるべきです。
もし初期キャパシティがload factorで割ったエントリの最大数よりも大きい場合、リハッシュ操作は起こりません。
- 🍙 キャパシティ10でload factorが0.5の場合、要素数が5まではリハッシュされない
もしたくさんのマッピングがHashMapのインスタンスに保存されるなら、十分に大きなキャパシティを与えたインスタンスを作成することは、必要に応じて自動的なリハッシュによるテーブルの拡張操作をさせるよりも効率的にマッピングを保存させることができます。
多くのキーが同じキー(hashCode()の結果)を用いる場合、ハッシュテーブルのパフォーマンスは落ちます。
この影響を改善するため、キーがComparableな時はこのクラスは、同じキーに対する値の決定のため比較を利用します。
- 🍙 比較の下りがかなり適当くさい
- 🍙 衝突した時の検索にComparableを使うという話だろうなとは思う
この実装は同期的ではありません。もし複数スレッドがハッシュマップに同時にアクセスすると、 少なくとも一つのスレッドがマップを構造的に更新する場合、外部から同期される必要があります。
(構造的な変更とは、マッピングの追加や削除のことであり、すでにマップに含まれるキーに紐づいたインスタンスの変更は構造的な変更ではありません。)
これは一般的に、自然にマップをカプセル化するオブジェクトの同期によって達成されます。
- 🍙 同期するためのオブジェクトでラップして同期はそいつに任せるべき的な話?
- If no such object exists, the map should be "wrapped" using the
- {@link Collections#synchronizedMap Collections.synchronizedMap}
- method. This is best done at creation time, to prevent accidental
- unsynchronized access to the map:
- Map m = Collections.synchronizedMap(new HashMap(...));
そのようなオブジェクトが存在しない場合、マップはCollections#synchronizedMapによってラップされるべきです。これは同期的でないマップへの、意図しないアクセスを防ぐために、作成時に行うのがベストです。
このクラスの全てのコレクションビューメソッドによって返るイテレーターは、フェイルファストです。
もしイテレーターが作成された後でイテレーター自身以外によるremoveメソッド以外による構造的な変更があると、イテレーターはConcurrentModificationException
をスローします。
このように同時に更新があった場合に、イテレーターは任意のタイミングで決定的でない振る舞いが、未来における確定していないタイミングで起こるリスクを取らずに、素早く明確に失敗します。
このイテレーターにおけるフェイルファストな振る舞いは、一般的に非同期に並行に行われる変更においては明確に保障することは不可能なため、保証されません。
フェイルファストなイテレーターのスローするConcurrentModificationExceptionはベストエフォートです。
なので、この例外に依存するプログラムを書くのはよくないです。
イテレーターのフェイルファストな振る舞いは、バグの検知にのみ利用すべきです。