How java implements HashMap
4764 ワード
1. How java implements HashMap
HashMap Custom implementation in java - How HashMap works internally with diagrams and full program
http://www.javamadesoeasy.com/2015/02/hashmap-custom-implementation.html
2. HashMap interview question
17.Javaで、HashMapはどのように働いていますか.
HashMapは、Map.Entry静的内部クラスインプリメンテーションにkey-valueペアを格納する.HashMapはハッシュアルゴリズムを用い,putとget法ではhashCode()とequals()法を用いた.key−value対呼び出しputメソッドを渡すと,HashMapはKeyhashCode()とハッシュアルゴリズムを用いてkey−value対を格納するインデックスを探し出す.EntryはLinkedListに格納されているので、entryが存在する場合はequals()メソッドを使用して伝達されたkeyが存在するかどうかを確認し、存在する場合はvalueを上書きし、存在しない場合は新しいentryを作成して保存します.keyを渡してgetメソッドを呼び出すと、hashCode()を再使用して配列内のインデックスを見つけ、equals()メソッドを使用して正しいEntryを見つけ、その値を返します.以下の画像は詳細を説明しています.
HashMapに関する他の重要な問題は、容量、負荷係数、およびバルブ値の調整である.HashMapのデフォルトの初期容量は32で、負荷係数は0.75です.バルブ値は負荷係数に容量を乗じたもので、いつでもentryを追加しようとします.mapのサイズがバルブ値より大きい場合、HashMapはmapの内容を再ハッシュし、より大きな容量を使用します.容量は常に2のべき乗なので、データベースから引き出されたデータをキャッシュするなど、key-valueペアを大量に格納する必要があることを知っていれば、正しい容量と負荷係数を使用してHashMapを初期化するのは良い方法です.
18.hashCode()とequals()メソッドの重要性は何ですか.
HashMapはKeyオブジェクトのhashCode()とequals()メソッドを使用してkey-valueペアのインデックスを決定します.HashMapから値を取得しようとすると、これらの方法も使用されます.これらの方法が正しく実現されていない場合、2つの異なるKeyは同じhashCode()およびequals()出力を生成する可能性があり、HashMapはそれらが同じであると考え、異なる場所に格納するのではなく、それらを上書きする.同様に、重複データを格納できないすべての集合クラスはhashCode()とequals()を使用して重複を検索するので、それらを正しく実現することが重要です.equals()とhashCode()の実装は、次のルールに従う必要があります.
(1)o 1.equals(o 2)の場合、o 1.hashCode()==o 2.hashCode()は常にtrueである.
(2)o 1.hashCode()==o 2.hashCode()の場合、o 1.equals(o 2)がtrueになるとは限らない.
19.Mapのkeyとしてクラスを使用できますか?
どのクラスもMapのkeyとして使用できますが、それらを使用する前に、以下の点を考慮する必要があります.
(1)クラスがequals()メソッドを書き換えた場合,hashCode()メソッドも書き換えるべきである.
(2)クラスのすべてのインスタンスはequals()およびhashCode()に関連する規則に従う必要がある.前に述べたルールを参照してください.
(3)クラスがequals()を使用していない場合はhashCode()で使用するべきではありません.
(4)ユーザがkeyクラスをカスタマイズするベストプラクティスは,hashCode()値をキャッシュし,より良い性能をもたらすようにすることである.可変クラスはhashCode()とequals()が将来変わらないことを保証し、可変に関連する問題を解決することができます.
例えば、私はHashMapでそれを使用するクラスMyKeyを持っています.
それはなぜStringとIntegerがHashMapのkeyとして大量に使われているのかということです.
20.Mapインタフェースはどのような異なるコレクションビューを提供していますか?
Mapインタフェースには、3つのコレクションビューがあります.
(1)Set keyset():mapに含まれるすべてのkeyのSetビューを返します.集合はmapによってサポートされ,mapの変化は集合に反映され,逆も同様である.反復器がセットを巡回している場合、mapが変更されると(反復器自体の除去操作を除く)、反復器の結果は未定義になります.コレクションは、IteratorのRemove、Set.remove、removeAll、retainAll、clear操作による要素除去をサポートし、mapから対応するマッピングを除去します.addおよびaddAll操作はサポートされていません.
(2)Collection values():mapに含まれるすべてのvalueのCollectionビューを返します.このcollectionはmapによってサポートされており、mapの変化はcollectionに反映され、逆も同様である.反復器がcollectionを巡回している場合、mapが変更されると(反復器自体の除去操作を除く)、反復器の結果は未定義になります.コレクションは、IteratorのRemove、Set.remove、removeAll、retainAll、clear操作による要素除去をサポートし、mapから対応するマッピングを除去します.addおよびaddAll操作はサポートされていません.
(3)Set>entrySet():mapクロックに含まれるすべてのマッピングのセットビューを返します.この集合はmapによってサポートされ,mapの変化はcollectionに反映され,逆も同様である.反復器がセットを巡回している場合、mapが変更されると(反復器自体の除去操作と、反復器に返されるentryのsetValueを除く)、反復器の結果は未定義になります.コレクションは、IteratorのRemove、Set.remove、removeAll、retainAll、clear操作による要素除去をサポートし、mapから対応するマッピングを除去します.addおよびaddAll操作はサポートされていません.
21.HashMapとHashTableの違いは何ですか?
(1)HashMapはkeyとvalueがnullであることを許可し,HashTableは許可しない.
(2)HashTableは同期しているが,HashMapはそうではない.したがって,HashMapは単一スレッド環境,HashTableはマルチスレッド環境に適している.
(3)Java 1.4にLinkedHashMap,HashMapのサブクラスを導入し,順序を遍歴したい場合はHashMapからLinkedHashMapに移行しやすいが,HashTableはそうではなく,その順序は予知できない.
(4)HashMapはkeyのSetを巡回することを提供するのでfail-fastであるが,HashTableはkeyのEnumerationを巡回することを提供し,fail-fastをサポートしない.
(5)HashTableは残されたクラスと考えられており,反復時にMapの修正を求める場合はCocurrentHashMapを使用するべきである.
22.HashMapとTreeMapのどちらを選ぶか、どのように決めますか.
Mapに要素を挿入、削除、位置決めする操作には、HashMapが最適です.しかし、秩序あるkey集合を巡回する必要がある場合は、TreeMapがより良い選択です.あなたのcollectionのサイズに基づいて、HashMapに要素を追加すると、mapをTreeMapに変更して秩序keyの遍歴が速くなるかもしれません.
reference:
http://www.sanesee.com/article/40-java-collections-interview-questions-and-answers
転載先:https://www.cnblogs.com/hygeia/p/5150122.html
HashMap Custom implementation in java - How HashMap works internally with diagrams and full program
http://www.javamadesoeasy.com/2015/02/hashmap-custom-implementation.html
2. HashMap interview question
17.Javaで、HashMapはどのように働いていますか.
HashMapは、Map.Entry静的内部クラスインプリメンテーションにkey-valueペアを格納する.HashMapはハッシュアルゴリズムを用い,putとget法ではhashCode()とequals()法を用いた.key−value対呼び出しputメソッドを渡すと,HashMapはKeyhashCode()とハッシュアルゴリズムを用いてkey−value対を格納するインデックスを探し出す.EntryはLinkedListに格納されているので、entryが存在する場合はequals()メソッドを使用して伝達されたkeyが存在するかどうかを確認し、存在する場合はvalueを上書きし、存在しない場合は新しいentryを作成して保存します.keyを渡してgetメソッドを呼び出すと、hashCode()を再使用して配列内のインデックスを見つけ、equals()メソッドを使用して正しいEntryを見つけ、その値を返します.以下の画像は詳細を説明しています.
HashMapに関する他の重要な問題は、容量、負荷係数、およびバルブ値の調整である.HashMapのデフォルトの初期容量は32で、負荷係数は0.75です.バルブ値は負荷係数に容量を乗じたもので、いつでもentryを追加しようとします.mapのサイズがバルブ値より大きい場合、HashMapはmapの内容を再ハッシュし、より大きな容量を使用します.容量は常に2のべき乗なので、データベースから引き出されたデータをキャッシュするなど、key-valueペアを大量に格納する必要があることを知っていれば、正しい容量と負荷係数を使用してHashMapを初期化するのは良い方法です.
18.hashCode()とequals()メソッドの重要性は何ですか.
HashMapはKeyオブジェクトのhashCode()とequals()メソッドを使用してkey-valueペアのインデックスを決定します.HashMapから値を取得しようとすると、これらの方法も使用されます.これらの方法が正しく実現されていない場合、2つの異なるKeyは同じhashCode()およびequals()出力を生成する可能性があり、HashMapはそれらが同じであると考え、異なる場所に格納するのではなく、それらを上書きする.同様に、重複データを格納できないすべての集合クラスはhashCode()とequals()を使用して重複を検索するので、それらを正しく実現することが重要です.equals()とhashCode()の実装は、次のルールに従う必要があります.
(1)o 1.equals(o 2)の場合、o 1.hashCode()==o 2.hashCode()は常にtrueである.
(2)o 1.hashCode()==o 2.hashCode()の場合、o 1.equals(o 2)がtrueになるとは限らない.
19.Mapのkeyとしてクラスを使用できますか?
どのクラスもMapのkeyとして使用できますが、それらを使用する前に、以下の点を考慮する必要があります.
(1)クラスがequals()メソッドを書き換えた場合,hashCode()メソッドも書き換えるべきである.
(2)クラスのすべてのインスタンスはequals()およびhashCode()に関連する規則に従う必要がある.前に述べたルールを参照してください.
(3)クラスがequals()を使用していない場合はhashCode()で使用するべきではありません.
(4)ユーザがkeyクラスをカスタマイズするベストプラクティスは,hashCode()値をキャッシュし,より良い性能をもたらすようにすることである.可変クラスはhashCode()とequals()が将来変わらないことを保証し、可変に関連する問題を解決することができます.
例えば、私はHashMapでそれを使用するクラスMyKeyを持っています.
// MyKey name equals() hashCode()
MyKey key = new MyKey('Pankaj'); //assume hashCode=1234
myHashMap.put(key, 'Value');
// key hashCode() equals()
key.setName('Amit'); //assume new hashCode=7890
// null, HashMap key, key , , null
myHashMap.get(new MyKey('Pankaj'));
それはなぜStringとIntegerがHashMapのkeyとして大量に使われているのかということです.
20.Mapインタフェースはどのような異なるコレクションビューを提供していますか?
Mapインタフェースには、3つのコレクションビューがあります.
(1)Set keyset():mapに含まれるすべてのkeyのSetビューを返します.集合はmapによってサポートされ,mapの変化は集合に反映され,逆も同様である.反復器がセットを巡回している場合、mapが変更されると(反復器自体の除去操作を除く)、反復器の結果は未定義になります.コレクションは、IteratorのRemove、Set.remove、removeAll、retainAll、clear操作による要素除去をサポートし、mapから対応するマッピングを除去します.addおよびaddAll操作はサポートされていません.
(2)Collection values():mapに含まれるすべてのvalueのCollectionビューを返します.このcollectionはmapによってサポートされており、mapの変化はcollectionに反映され、逆も同様である.反復器がcollectionを巡回している場合、mapが変更されると(反復器自体の除去操作を除く)、反復器の結果は未定義になります.コレクションは、IteratorのRemove、Set.remove、removeAll、retainAll、clear操作による要素除去をサポートし、mapから対応するマッピングを除去します.addおよびaddAll操作はサポートされていません.
(3)Set>entrySet():mapクロックに含まれるすべてのマッピングのセットビューを返します.この集合はmapによってサポートされ,mapの変化はcollectionに反映され,逆も同様である.反復器がセットを巡回している場合、mapが変更されると(反復器自体の除去操作と、反復器に返されるentryのsetValueを除く)、反復器の結果は未定義になります.コレクションは、IteratorのRemove、Set.remove、removeAll、retainAll、clear操作による要素除去をサポートし、mapから対応するマッピングを除去します.addおよびaddAll操作はサポートされていません.
21.HashMapとHashTableの違いは何ですか?
(1)HashMapはkeyとvalueがnullであることを許可し,HashTableは許可しない.
(2)HashTableは同期しているが,HashMapはそうではない.したがって,HashMapは単一スレッド環境,HashTableはマルチスレッド環境に適している.
(3)Java 1.4にLinkedHashMap,HashMapのサブクラスを導入し,順序を遍歴したい場合はHashMapからLinkedHashMapに移行しやすいが,HashTableはそうではなく,その順序は予知できない.
(4)HashMapはkeyのSetを巡回することを提供するのでfail-fastであるが,HashTableはkeyのEnumerationを巡回することを提供し,fail-fastをサポートしない.
(5)HashTableは残されたクラスと考えられており,反復時にMapの修正を求める場合はCocurrentHashMapを使用するべきである.
22.HashMapとTreeMapのどちらを選ぶか、どのように決めますか.
Mapに要素を挿入、削除、位置決めする操作には、HashMapが最適です.しかし、秩序あるkey集合を巡回する必要がある場合は、TreeMapがより良い選択です.あなたのcollectionのサイズに基づいて、HashMapに要素を追加すると、mapをTreeMapに変更して秩序keyの遍歴が速くなるかもしれません.
reference:
http://www.sanesee.com/article/40-java-collections-interview-questions-and-answers
転載先:https://www.cnblogs.com/hygeia/p/5150122.html