JavaのHashMapの実装を眺める会②

Java

そもそもクラスのJavaDocを読むべき

  • 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のオペレーションを全て提供します。

  • 🍙 putってOptionalなんだな

null値とnullのキーを許容します。 HashMapは雑に言えば、同期的でないこと、nullを許容することをのぞいてHashtableと等価です。 このクラスはMapの順序を保証しません。時間が経っても順序が一定に保たれることを保証していません。

  • 🍙 in particularがよくわからん

  • This implementation provides constant-time performance for the basic

  • operations (get and put), assuming the hash function
  • disperses the elements properly among the buckets. Iteration over
  • collection views requires time proportional to the "capacity" of the
  • HashMap instance (the number of buckets) plus its size (the number
  • of key-value mappings). Thus, it's very important not to set the initial
  • capacity too high (or the load factor too low) if iteration performance is
  • important.

この実装はハッシュ関数はバケット間に要素が適切に散らばることを仮定し、一般的な操作（get, put）をO(1)のパフォーマンスで提供します。 コレクションビューを超えたイテレーションは、Hashmapインスタンスのキャパシティ+そのサイズ（key-value mappingsの数）に比例する必要があります。 そのため、もしイテレーションのパフォーマンスが重要なのであれば、初期キャパシティを高くしすぎない、（もしくはload factorを低くしすぎない）ことがとても重要です。

  • An instance of HashMap has two parameters that affect its

  • performance: initial capacity and load factor. The
  • capacity is the number of buckets in the hash table, and the initial
  • capacity is simply the capacity at the time the hash table is created. The
  • load factor is a measure of how full the hash table is allowed to
  • get before its capacity is automatically increased. When the number of
  • entries in the hash table exceeds the product of the load factor and the
  • current capacity, the hash table is rehashed (that is, internal data
  • structures are rebuilt) so that the hash table has approximately twice the
  • number of buckets.

HashMapのインスタンスはパフォーマンスに影響する2つのパラメーターを持っています。 初期キャパシティとload factorを低くしすぎない）ことがとても重要です。 キャパシティは、ハッシュテーブルのバケットの数で、初期キャパシティはハッシュテーブルが作られたタイミングのキャパシティのことです。 load factorはキャパシティが自動的に増加するまでにハッシュテーブルがどれくらいまで埋まるかを許容する閾値です。 ハッシュテーブル内のエントリーの数がload factorと現在のキャパシティを超えた時、ハッシュテーブルはリハッシュします。 リハッシュとは、内部のデータ構造の再構築のことです。 ハッシュテーブルはおよそバケットの数の２倍となります。

  • As a general rule, the default load factor (.75) offers a good

  • tradeoff between time and space costs. Higher values decrease the
  • space overhead but increase the lookup cost (reflected in most of
  • the operations of the HashMap class, including
  • get and put). The expected number of entries in
  • the map and its load factor should be taken into account when
  • setting its initial capacity, so as to minimize the number of
  • rehash operations. If the initial capacity is greater than the
  • maximum number of entries divided by the load factor, no rehash
  • operations will ever occur.

一般的なルールとして、デフォルトのload factorは時間と容量のコストの間で良いトレードオフを提供します。 高い値はスペースのオーバーヘッドを減らしますが、参照時のコストは増加します。（参照時のコストはget,putを含むHashMapのほとんどの操作に影響します）

  • 🍙 高すぎるとギチギチまで詰める感じになる？
  • 🍙 参照時のコストが上がる理由がよくわからない
    • 🍙 衝突が増えるのかな？

予期されるマップにおけるエントリの数とそのload factorは、リハッシュの操作回数を最小化するように初期キャパシティがセットされる時に考慮されるべきです。 もし初期キャパシティがload factorで割ったエントリの最大数よりも大きい場合、リハッシュ操作は起こりません。

  • 🍙 キャパシティ10でload factorが0.5の場合、要素数が5まではリハッシュされない

  • If many mappings are to be stored in a HashMap

  • instance, creating it with a sufficiently large capacity will allow
  • the mappings to be stored more efficiently than letting it perform
  • automatic rehashing as needed to grow the table. Note that using
  • many keys with the same {@code hashCode()} is a sure way to slow
  • down performance of any hash table. To ameliorate impact, when keys
  • are {@link Comparable}, this class may use comparison order among
  • keys to help break ties.

もしたくさんのマッピングがHashMapのインスタンスに保存されるなら、十分に大きなキャパシティを与えたインスタンスを作成することは、必要に応じて自動的なリハッシュによるテーブルの拡張操作をさせるよりも効率的にマッピングを保存させることができます。

多くのキーが同じキー（hashCode()の結果）を用いる場合、ハッシュテーブルのパフォーマンスは落ちます。 この影響を改善するため、キーがComparableな時はこのクラスは、同じキーに対する値の決定のため比較を利用します。

  • 🍙 比較の下りがかなり適当くさい
    • 🍙 衝突した時の検索にComparableを使うという話だろうなとは思う

  • Note that this implementation is not synchronized.

  • If multiple threads access a hash map concurrently, and at least one of
  • the threads modifies the map structurally, it must be
  • synchronized externally. (A structural modification is any operation
  • that adds or deletes one or more mappings; merely changing the value
  • associated with a key that an instance already contains is not a
  • structural modification.) This is typically accomplished by
  • synchronizing on some object that naturally encapsulates the map.

この実装は同期的ではありません。もし複数スレッドがハッシュマップに同時にアクセスすると、 少なくとも一つのスレッドがマップを構造的に更新する場合、外部から同期される必要があります。 （構造的な変更とは、マッピングの追加や削除のことであり、すでにマップに含まれるキーに紐づいたインスタンスの変更は構造的な変更ではありません。）

これは一般的に、自然にマップをカプセル化するオブジェクトの同期によって達成されます。

  • 🍙 同期するためのオブジェクトでラップして同期はそいつに任せるべき的な話？
  • 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によってラップされるべきです。これは同期的でないマップへの、意図しないアクセスを防ぐために、作成時に行うのがベストです。



    

  • The iterators returned by all of this class's "collection view methods"
    • 

  • are fail-fast: if the map is structurally modified at any time after
    • 

  • the iterator is created, in any way except through the iterator's own
    • 

  • remove method, the iterator will throw a
    • 

  • {@link ConcurrentModificationException}.  Thus, in the face of concurrent
    • 

  • modification, the iterator fails quickly and cleanly, rather than risking
    • 

  • arbitrary, non-deterministic behavior at an undetermined time in the
    • 

  • future.
    • 






このクラスの全てのコレクションビューメソッドによって返るイテレーターは、フェイルファストです。
もしイテレーターが作成された後でイテレーター自身以外によるremoveメソッド以外による構造的な変更があると、イテレーターはConcurrentModificationExceptionをスローします。



このように同時に更新があった場合に、イテレーターは任意のタイミングで決定的でない振る舞いが、未来における確定していないタイミングで起こるリスクを取らずに、素早く明確に失敗します。



    

  • Note that the fail-fast behavior of an iterator cannot be guaranteed
    • 

  • as it is, generally speaking, impossible to make any hard guarantees in the
    • 

  • presence of unsynchronized concurrent modification.  Fail-fast iterators
    • 

  • throw ConcurrentModificationException on a best-effort basis.
    • 

  • Therefore, it would be wrong to write a program that depended on this
    • 

  • exception for its correctness: the fail-fast behavior of iterators
    • 

  • should be used only to detect bugs.
    • 






このイテレーターにおけるフェイルファストな振る舞いは、一般的に非同期に並行に行われる変更においては明確に保障することは不可能なため、保証されません。
フェイルファストなイテレーターのスローするConcurrentModificationExceptionはベストエフォートです。
なので、この例外に依存するプログラムを書くのはよくないです。
イテレーターのフェイルファストな振る舞いは、バグの検知にのみ利用すべきです。