ソースコードの観点からHashtableとHashMapの違いを分析する
6000 ワード
引用する
面接では「HashtableとHashMapの違いを教えてください」とよく聞かれます.検索エンジンを通じて、私たちは簡単に多くの答えを見つけることができます.これらの答えは両者の違いを詳しく比較した.しかし、「それを知る」段階にとどまりがちで、文字だけで両者の違いを列挙しています.そのため、数日後にこの問題を振り返ると、すべてがゼロに戻ったようです(少なくとも記憶の悪い私にとってはそうです).今日は、ソースコードの観点から違いを分析し、「それを知る」だけでなく、もっと知っているからそうです」.興味があれば、私と一緒に、HashtableとHashMapの世界がどんなものか見てみましょう.
注意:次のソースコードはOracle JDK 1.8から来ています.Android SdKでソースコードを確認して、ここに記載されているソースコードと一致しないことが判明した場合は、慌てないでください.android SDKでJDKソースコードはApacheのオープンソースプロジェクトHarmonyを使用しているためです.
データ構造
比較を容易にするために、まず、HashtableとHashMapをそれぞれインスタンス化します.
loadFactor:ファクタをロードします.両方のデータ構造にこの変数があり、デフォルトは0.75 fです.
threshold:バルブ値.Hashtable拡張の場合、現在の長さがこのthreshold値を超えているかどうかを判断して拡張の有無を決定することから、Hashtableオブジェクトを作成する際にloadFactor、table長さ11、バルブ値11*0.75=8(整列)を初期化するHashMap拡張時にもバルブ値がありますか?答えは肯定的ですが、初期化はここではありません.以下で紹介します.
もちろん、オブジェクトを作成するときに、ロード係数やバルブ値を指定することもできます.
table:HashMapとHashtableには配列tableがあり、HashMapではtableタイプがNode汎用である.HashtableではtableタイプがEntry汎用である.名前は異なるが同じデータ構造を有し、内部には4つの属性があり、それぞれhash,key,value,next:
putメソッド
putメソッドの違いを見てみましょう.
HashMapのputメソッド
まずHashMapのputメソッドを解析します
次にputValメソッドに入ります.コードは次のとおりです.
5行目のコードから分かるように、putValメソッドは、tableがnullであるか長さが0であるかを先に判断し、構造関数を使用してHashMapオブジェクトを作成した場合、tableは初期化されていないので、tableは空であり、条件成立(すなわち、最初にputメソッドを呼び出す)はresize()メソッドに入る.
1.初期化
2.2倍拡張
この実装プロセスをよく見てみましょう.
-putメソッドが最初に呼び出されたとき、tableはnullであり、対応するoldtabはnullである.5行目のコードからoldCap=0を得る.すると、コードは20行目に入り、newCapとnewThrを初期化する:DEFAULT_INITIAL_CAPACITY=16;バルブ値newThrは16*0.75=12-tableが空でない場合、9行目のコード実行に入り、table配列長が上限値に達したかどうかを判断する.到着した場合、元のtableを返し、つまり今回のputのデータは集合に追加されません.拡張条件を満たしている場合は、newCap=oldCap<<1を拡張します.つまり、拡張を元の2倍にします.対応するバルブ値も元の2倍に拡張します.newThr=oldThr<<1
Hashtableのputメソッド:
Hashtableのputメソッドはsynchronizedによって修飾されていることが明らかになった.つまりスレッドが安全である.これはおそらくHashMapのputメソッドと最大の違いである.
forループでhash値に基づいてキーが元のセットにすでに存在するかどうかを検索し、存在する場合はvalue値を置き換えます.存在しない場合はaddEntry()メソッドを使用して新しいキー値ペアを追加します.
新しい値を挿入する前に、まず長さ検査を行い、長さがオーバーフローしているかどうかを判断します(バルブ値より大きい).オーバーフローしている場合は、拡張を行い、拡張メカニズム:int newCapacity=(oldCapacity<<1)+1.
まとめオブジェクトを作成する場合、Hashtableはロードファクタ(0.75 f)、配列長(11)、バルブ値を初期化するが、HashMapはロードファクタ(0.75 f)のみを初期化し、最初のputで配列長(16) を初期化する. HashMap内部のストレージ構造はNodeであり、Hashtable内部のストレージ構造Entryである.名称は異なるが、同じデータ構造を有している.また、いずれもMap.Entryインタフェースを実現している. Hashtableのputメソッドはスレッドが安全であるが、HashMapのputメソッドはそうではない. 拡張時のHashtable長さは元の2倍+1となり、HashMap長さは元の2倍となり、 となる. putメソッドを使用する場合、tableのvalue値はnullではなく、Mapではありません.
面接では「HashtableとHashMapの違いを教えてください」とよく聞かれます.検索エンジンを通じて、私たちは簡単に多くの答えを見つけることができます.これらの答えは両者の違いを詳しく比較した.しかし、「それを知る」段階にとどまりがちで、文字だけで両者の違いを列挙しています.そのため、数日後にこの問題を振り返ると、すべてがゼロに戻ったようです(少なくとも記憶の悪い私にとってはそうです).今日は、ソースコードの観点から違いを分析し、「それを知る」だけでなく、もっと知っているからそうです」.興味があれば、私と一緒に、HashtableとHashMapの世界がどんなものか見てみましょう.
注意:次のソースコードはOracle JDK 1.8から来ています.Android SdKでソースコードを確認して、ここに記載されているソースコードと一致しないことが判明した場合は、慌てないでください.android SDKでJDKソースコードはApacheのオープンソースプロジェクトHarmonyを使用しているためです.
データ構造
比較を容易にするために、まず、HashtableとHashMapをそれぞれインスタンス化します.
HashMap hashMap = new HashMap();
Hashtable hashtable = new Hashtable();
次に、それらの構造方法に入って、中に何があるか見てみましょう.//hashMap
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//DEFAULT_LOAD_FACTOR
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//hashmap table
transient Node[] table;
//hashtable
public Hashtable() {
this(11, 0.75f);
}
// this
public Hashtable(int initialCapacity, float loadFactor) {
// ...
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
ここではいくつかの変数を説明します.loadFactor:ファクタをロードします.両方のデータ構造にこの変数があり、デフォルトは0.75 fです.
threshold:バルブ値.Hashtable拡張の場合、現在の長さがこのthreshold値を超えているかどうかを判断して拡張の有無を決定することから、Hashtableオブジェクトを作成する際にloadFactor、table長さ11、バルブ値11*0.75=8(整列)を初期化するHashMap拡張時にもバルブ値がありますか?答えは肯定的ですが、初期化はここではありません.以下で紹介します.
もちろん、オブジェクトを作成するときに、ロード係数やバルブ値を指定することもできます.
Hashtable table = new Hashtable(20,0.8f);
HashMap map = new HashMap(20,0.8f);
table:HashMapとHashtableには配列tableがあり、HashMapではtableタイプがNode汎用である.HashtableではtableタイプがEntry汎用である.名前は異なるが同じデータ構造を有し、内部には4つの属性があり、それぞれhash,key,value,next:
//HashMap-Node
final int hash; // key
final K key; // key
V value; // value
Node next; //
から分かるように、ノードはHashMapの最も基本的なデータ構造であり、EntryはHashtableの最も基本的なデータ構造である.putメソッドを呼び出すときに追加したキー値ペアはtable配列に存在する.putメソッド
putメソッドの違いを見てみましょう.
HashMapのputメソッド
まずHashMapのputメソッドを解析します
//HashMap put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
次にputValメソッドに入ります.コードは次のとおりです.
//HashMap
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//...
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
5行目のコードから分かるように、putValメソッドは、tableがnullであるか長さが0であるかを先に判断し、構造関数を使用してHashMapオブジェクトを作成した場合、tableは初期化されていないので、tableは空であり、条件成立(すなわち、最初にputメソッドを呼び出す)はresize()メソッドに入る.
//HashMap resize()
//resize :Initializes or doubles table size.
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//...
threshold = newThr;
//.fangfa..
return newTab;
}
説明から、resizeメソッドは2つの機能を担う情報を得た.1.初期化
2.2倍拡張
この実装プロセスをよく見てみましょう.
-putメソッドが最初に呼び出されたとき、tableはnullであり、対応するoldtabはnullである.5行目のコードからoldCap=0を得る.すると、コードは20行目に入り、newCapとnewThrを初期化する:DEFAULT_INITIAL_CAPACITY=16;バルブ値newThrは16*0.75=12-tableが空でない場合、9行目のコード実行に入り、table配列長が上限値に達したかどうかを判断する.到着した場合、元のtableを返し、つまり今回のputのデータは集合に追加されません.拡張条件を満たしている場合は、newCap=oldCap<<1を拡張します.つまり、拡張を元の2倍にします.対応するバルブ値も元の2倍に拡張します.newThr=oldThr<<1
Hashtableのputメソッド:
public synchronized V put(K key, V value) {
// table value null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry entry = (Entry)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
Hashtableのputメソッドはsynchronizedによって修飾されていることが明らかになった.つまりスレッドが安全である.これはおそらくHashMapのputメソッドと最大の違いである.
forループでhash値に基づいてキーが元のセットにすでに存在するかどうかを検索し、存在する場合はvalue値を置き換えます.存在しない場合はaddEntry()メソッドを使用して新しいキー値ペアを追加します.
新しい値を挿入する前に、まず長さ検査を行い、長さがオーバーフローしているかどうかを判断します(バルブ値より大きい).オーバーフローしている場合は、拡張を行い、拡張メカニズム:int newCapacity=(oldCapacity<<1)+1.
まとめ