HashMapの面接問題を知っておく必要があります
4735 ワード
1.HashMapの動作原理、get()メソッドの動作原理?
HashMapはhash原理に基づいて、
2.HashMapを同期できますか?
同期は
3.HashMapにおけるハッシュ衝突(ハッシュ衝突)および衝突解決方法について?
HashMapはkeyのhash値を計算することによって配列位置を決定し、異なるkeyは同じhash値を生成する可能性があるためhash衝突が発生し、HashMapではチェーンアドレス法を用いてhash衝突を解決し、衝突が発生した場合、同じhash値の要素をチェーンテーブルの次のノードに格納する.このほかにもオープンアドレス法,再ハッシュ法がある.キー:衝突の原因を生成し、良いhash関数で衝突を低減できます.
4.HashMapのサイズが負荷係数定義の容量を超えた場合はどうなりますか?
HashMapのデフォルトの負荷係数は0.75で、HashMapの配列要素の個数が負荷係数に配列の総容量を乗じた場合に拡張が発生し、配列を元の2倍に拡張し、元の配列の要素に対してhash演算を行い、新しい配列の位置を得る.キーポイント:拡張!!.
5.HashMapサイズの再調整に何か問題があるか知っていますか?
マルチスレッドの条件の下でHashMapに対して操作するのは确かに同期の问题が存在して、ネット上を见てHashMapの大きさを调整すると头に元素を添加して尾の循环を避けることができて、それから死んで循环します...実は私は理解していません!!!
6.なぜString、Intergerのようなwrapperクラスがキーとして適しているのか.
HashMapは、Stringが最も一般的なキーとして可変変数を使用することを推奨します.Stringは可変であり、finalでもあるため、keyのhash値を計算して配列内を検索します.keyが可変タイプであれば、挿入と取得時に返されるhashcodeが異なり、目的のオブジェクトを正しく取得できません.
7.カスタムオブジェクトをキーとして使用できますか?
はい、しかし、このオブジェクトが
8.Hashtableの代わりにCocurrentHashMapを使用できますか?
はい、
9.HashMap拡張の問題?
拡張は、HashMapの下位配列を新規作成し、
10.なぜHashMapはスレッドが安全ではないのですか?どのように安全ではないことを体現しますか?
複数のスレッドがHashMapに対してput操作を行う場合、putのkeyが同じ衝突を起こすと、HashMapは2つのkeyを配列の同じ位置に配置し、1つのスレッドのkeyが上書きされます.
複数のスレッドが配列の拡張が必要であることを検出すると、配列内の要素hash値の再計算とデータ複製が行われ、最後に1つのスレッドで作成された配列だけがtableに値を割り当てることに成功するに違いない.
11.HashMapにスレッドセキュリティを実現させるにはどうすればいいですか?スレッドセキュリティのHashTableを使用すると、1つのスレッドがHashTableの同期メソッドにアクセスすると、他のスレッドがブロックされます.すなわち,1つのスレッドがget操作を行うと,他のスレッドは何も操作できず,効率が低い. は は
12.HashMapのhash関数はどのように実現されますか?
hashはkey自身の
13.HashMapはhashcodeとequalsメソッドを書き換える必要があるのはいつですか?
key値がオブジェクトである場合、
HashMapはhash原理に基づいて、
put()
およびget()
の方法によって要素を格納および取得する.内部には配列+チェーンテーブルまたは赤黒ツリーの構造を用い,hash演算によりbucket位置を見つけてEnteyオブジェクトを格納し,equals()
法により正しいキー値ペアを見つけた.HashMapはチェーンアドレス法を使用してhash衝突の問題を解決し、衝突が発生するとオブジェクトがチェーンテーブルの次のノードに格納されます.get()
まずkeyのhash値を計算することによって配列中の下付き文字を見つけ、下付き文字が空であればnullを直接返し、そうでなければその下付き文字が検索する要素であるかどうかを判断し、直接返し、その要素ノードが赤黒ツリーノードであるかどうかを判断するのではなく、赤黒ツリーノードの検索を行い、そうでなければチェーンテーブルを遍歴して検索する.キー:HashMapは、bucketにキーオブジェクトと値オブジェクトをMap.Entry
として格納します.2.HashMapを同期できますか?
同期は
Map m = Collections.synchronizeMap(hashMap)
によって達成される.synchronizeMap
でHashMapのすべての動作にsynchronized
競合モニタロックを追加してスレッド同期を実現する.キー:synchronizeMap
またはConcurrentHashMap
.3.HashMapにおけるハッシュ衝突(ハッシュ衝突)および衝突解決方法について?
HashMapはkeyのhash値を計算することによって配列位置を決定し、異なるkeyは同じhash値を生成する可能性があるためhash衝突が発生し、HashMapではチェーンアドレス法を用いてhash衝突を解決し、衝突が発生した場合、同じhash値の要素をチェーンテーブルの次のノードに格納する.このほかにもオープンアドレス法,再ハッシュ法がある.キー:衝突の原因を生成し、良いhash関数で衝突を低減できます.
4.HashMapのサイズが負荷係数定義の容量を超えた場合はどうなりますか?
HashMapのデフォルトの負荷係数は0.75で、HashMapの配列要素の個数が負荷係数に配列の総容量を乗じた場合に拡張が発生し、配列を元の2倍に拡張し、元の配列の要素に対してhash演算を行い、新しい配列の位置を得る.キーポイント:拡張!!.
5.HashMapサイズの再調整に何か問題があるか知っていますか?
マルチスレッドの条件の下でHashMapに対して操作するのは确かに同期の问题が存在して、ネット上を见てHashMapの大きさを调整すると头に元素を添加して尾の循环を避けることができて、それから死んで循环します...実は私は理解していません!!!
6.なぜString、Intergerのようなwrapperクラスがキーとして適しているのか.
HashMapは、Stringが最も一般的なキーとして可変変数を使用することを推奨します.Stringは可変であり、finalでもあるため、keyのhash値を計算して配列内を検索します.keyが可変タイプであれば、挿入と取得時に返されるhashcodeが異なり、目的のオブジェクトを正しく取得できません.
7.カスタムオブジェクトをキーとして使用できますか?
はい、しかし、このオブジェクトが
hashCode()
およびequals()
メソッドを書き換え、そのオブジェクトがMapに挿入された後も変更されないことを確認するには、これらに従う限り、キーとして使用できます.8.Hashtableの代わりにCocurrentHashMapを使用できますか?
はい、
CocurrentHashMap
をお勧めします.HashTableはsynchronized
を用いて同期を実現し、その中のすべての方法にモニタロックを追加した.問題は、1つのスレッドがput操作を行う場合、他のスレッドはgetまたは他の操作を得ることができないが、CocurrentHashMap
はセグメントロック技術を採用し、HashTableよりも強いスレッドセキュリティを提供することである.9.HashMap拡張の問題?
拡張は、HashMapの下位配列を新規作成し、
transfer
メソッドを呼び出して、HashMapのすべての要素を新しいHashMapに追加します(新しい配列の要素のインデックス位置を再計算します).明らかに、拡張は、これらの要素の新しい配列における位置を再計算し、複製処理を行う必要があるため、かなり時間がかかる操作である.したがって、HashMapを使用する場合は、HashMapの要素の個数を事前に見積もることが望ましい.これにより、HashMapの性能を向上させるのに役立つ.10.なぜHashMapはスレッドが安全ではないのですか?どのように安全ではないことを体現しますか?
複数のスレッドがHashMapに対してput操作を行う場合、putのkeyが同じ衝突を起こすと、HashMapは2つのkeyを配列の同じ位置に配置し、1つのスレッドのkeyが上書きされます.
複数のスレッドが配列の拡張が必要であることを検出すると、配列内の要素hash値の再計算とデータ複製が行われ、最後に1つのスレッドで作成された配列だけがtableに値を割り当てることに成功するに違いない.
11.HashMapにスレッドセキュリティを実現させるにはどうすればいいですか?
Collections.synchronizeMap(hashMap)
を使用する.しかし、その効率も高くなく、ソースコードを見に行くのを信じず、見終わった後、HashTableと同じ問題があることに気づきます.CocurrentHashMap
を使用する.12.HashMapのhash関数はどのように実現されますか?
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hashはkey自身の
hashCode()
値を計算することによって、intを返し、衝突発生の確率を低減するために、得られたhashCode()
の低16ビットと高16ビットの右シフト16ビットが異なるか、または.13.HashMapはhashcodeとequalsメソッドを書き換える必要があるのはいつですか?
key値がオブジェクトである場合、
hashcode()
およびequals()
メソッドの書き換えが必要である.デフォルトのhashcode()
では、メモリ内の値のアドレスがその値のhash値として使用されているため、同じ意味を持つ2つのオブジェクトを比較すると、そのアドレスが異なるため、計算されたhash値も異なる.一方、書き換えequals()
は、2つのオブジェクトが同じ意味を持つ属性を有することを保証することができる.