javaデータ構造のソースコードの解読
26802 ワード
HashMapは面接で聞いた最も多いデータ構造かもしれません.性能が良いので、多くのプログラマーに愛されています.
hashMapに聞いても、配列とチェーンは知っていますが、実際には?ソースを解読しましょう.
まず、その種類の構造を見ます.
ですから、まずMapインターフェースの中の方法を見てみます.この中の基本的な定義は注釈の形で提供します.
もう一つのインターフェースEntryはキーのペアを保存します.
そしてAbstractMapです.面白いのはこの抽象類がMapインターフェースを実現したということです.つまり、一部(全部ではない)Mapメソッドを実現しました.
好奇心を持って観察してみましょう.
この中のput方法は操作がサポートされていません.そしてcontain/get方法は線形検索entrySetです.そして、entrySetを取得する方法はまたバーチャルな方法です.
だから、抽象的なmapと呼ばないと、はっきり言ってもあなた自身が来なければなりません.線形検索もhashmapとは合いません.でしょう
ですから、次は本物のHashMap類に目を向けます.
まずいくつかの定数値を観測した.
しかし、この中には一つの空間の大きさの哲学問題が含まれています.私たちはrehashの時に、二つの超大型の行列が同時に存在しています.だから、境界を越えないために.
最大の容量は2^30で、2^31ではありません!!
まず、コンストラクタを確認します.
初期化容量を任意に設定することはできないようです.最大で最大値に達することができますが、装填因子は0以下の値でなければ大丈夫です.
実際には、装填因子が1.0より大きいのは非常に悪い数字です.
データを保存するには、チェーンテーブルの配列が必要です.オブジェクト変数を見てみます.
添削して調べる順番によって、まずputの方面の方法を見ます.
1、存在しないキーのペアを挿入したらmodCountを修正します.
2、キーパッドの値ペアだけを更新したら(k=v 1がk=v 2)、古い値v 1に戻ります.そうしないとnullに戻ります.
3、ツリー化閾値を超えるとツリーになります.
4、ノードkey検査をしないので、nullでもいいです.valueもそうです.
5、挿入ノードは、最後の挿し方を採用して、hash/keyの同じノードを探して更新しやすいです.
6、挿入プロセスはnがいつも2のx乗であるため、hash%nの代わりに(n-1)&hashを使用する.
第四点を説明するために、小さな実験をしました.
しかし
まず、彼の拡大規則を観察します.最初のifから分かります.最初のテーブル配列はnullで、何もありません.
最初の要素を置くと、新規作成が開始されます.
それでは、そのレシオ関数を見てみます.
1、パラメータnewがないhashMap初期化容量は16で、閾値12.
2、毎回新容量は元の2倍です.
3、容量がもう拡大できない場合、閾値を直接最大正の整数に設定する.
4、rehashプロセスは最高位の1分割のアルゴリズムを採用しています.具体的なプロセスは以下の通りです.
capacityはいつも2の倍数なので、最高位は1、他のビットは0です.1…n個の0を仮定してもいいです.
その後、拡張された新しい配列は1…n＋1個の0であり、この位置のチェーンノードのhashには1があり、対応するビットは0があり、次いで元の配列のj番目のノードである.
元の挿入位置を考慮してhash%n、新しい位置はhash%(2*n)です.じゃhash=b*n+j (jは挿入位置ですので)
だからhash%(2 n)は二つの結果しかないです!それはn＋jとjです.なぜですか?bが偶数の場合はhash%(2 n)=0+jとなり、bが奇数の場合は1*n＋jとなり、2つの新しいチェーンの挿入位置を完全に決定することができるからです.(お母さんや書庫のプログラマーはすごいです)
そして、奇数は1で終わる(2進数)、偶数は0で終わるので、capの最高位1は「&」である限り、bは奇数か偶数かが分かります.このようにして、もっと時間を節約する方法でrehashはチェーンテーブルについて(直接addのようなプロセスを使うと、毎回新しいチェーンをスキャンするのに時間がかかります).
今は木化(addの時のtreefify)とrehashの過程のsplitを見てみます.
前に見たブログでは、チェーンノードを直接に一連の措置(例えば元の場所で回転するなど)で赤と黒の木になると思っていました.
しかし、実際:
ツリー化プロセスは、まずprevとnextポインタでツリーの前駆と後続を指し、ツリー化の変換を行う.
さて、treeify関数は本当にツリーノードをツリーに変換するべきです.どのような過程なのかを見てみます.
一連の挿入を経て、ツリーのルートは必ずしも配列の頭ではないので、moveRoot ToFrontはルートノードを配列溝の位置に変えます.
私達は好奇心を禁じ得ません.中順を使って再帰するべきではないですか?
でも忘れましたか?prevとnextの指針がありますよ.だから:
チェーンのように分割する方法(1分割アルゴリズム)だけでいいです.
その後、分割が完了しても、ツリー化閾値より大きいと、依然としてツリーに変換される.
分割が完了したら、逆ツリー化閾値より小さい場合は、チェーンで挿入します.
これでもう一つのキーがどのように挿入されるかが終了しました.
便宜上、次はget方法を見てみると、スーパー実用的なキーでvalueを探します.
まず、hashの対応する位置を計算します.この位置が現在ツリー構造であれば、ツリーのlogN方法で検索します.そうでなければ、チェーンの線形検索です.
上記と同じプロセスでcontainsKeyのコードを得ることができます.
もう一つのcontainValue方法がありますか?
また、
keySetとvalueSetについては、初期化(怠惰なローディング)を行わず、その後、ローズマリーによって巡回を完了します.つまり、Setを新たに作ったのではなく、ローズマリーを生成しました.
それから「削除」の方法を見てみて、削除は中のremoveです.
そしてクリア:
そして簡単には交換できません.
これで面接の「高周波」が一段落しました.
hashMapに聞いても、配列とチェーンは知っていますが、実際には?ソースを解読しましょう.
まず、その種類の構造を見ます.
public class HashMap extends AbstractMap
implements Map, Cloneable, Serializable {
//...
} ですから、まずMapインターフェースの中の方法を見てみます.この中の基本的な定義は注釈の形で提供します.
int size();//
boolean isEmpty();//
boolean containsKey(Object key);//
boolean containsValue(Object value);//
V get(Object key);//
V put(K key, V value);//
V remove(Object key);//
void putAll(Map extends K, ? extends V> m);// Map
void clear();//
Set keySet();//
Collection values();//
Set> entrySet();//
もう一つのインターフェースEntryはキーのペアを保存します.
interface Entry {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
public static , V> Comparator> comparingByKey() {
return (Comparator> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
public static > Comparator> comparingByValue() {
return (Comparator> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
public static Comparator> comparingByKey(Comparator super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
public static Comparator> comparingByValue(Comparator super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
} そしてAbstractMapです.面白いのはこの抽象類がMapインターフェースを実現したということです.つまり、一部(全部ではない)Mapメソッドを実現しました.
好奇心を持って観察してみましょう.
public abstract Set> entrySet();
public V put(K key, V value) {
throw new UnsupportedOperationException();
}
public V get(Object key) {
Iterator> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry e = i.next();
if (e.getKey()==null)
return e.getValue();
}
} else {
while (i.hasNext()) {
Entry e = i.next();
if (key.equals(e.getKey()))
return e.getValue();
}
}
return null;
}
public boolean containsValue(Object value) {
Iterator> i = entrySet().iterator();
if (value==null) {
while (i.hasNext()) {
Entry e = i.next();
if (e.getValue()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry e = i.next();
if (value.equals(e.getValue()))
return true;
}
}
return false;
}
public boolean containsKey(Object key) {
Iterator> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry e = i.next();
if (e.getKey()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry e = i.next();
if (key.equals(e.getKey()))
return true;
}
}
return false;
} この中のput方法は操作がサポートされていません.そしてcontain/get方法は線形検索entrySetです.そして、entrySetを取得する方法はまたバーチャルな方法です.
だから、抽象的なmapと呼ばないと、はっきり言ってもあなた自身が来なければなりません.線形検索もhashmapとは合いません.でしょう
ですから、次は本物のHashMap類に目を向けます.
まずいくつかの定数値を観測した.
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;// 16
static final int MAXIMUM_CAPACITY = 1 << 30;// 2^30
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 0.75 3/4
static final int TREEIFY_THRESHOLD = 8;// ， 8，
static final int UNTREEIFY_THRESHOLD = 6;//
static final int MIN_TREEIFY_CAPACITY = 64;// しかし、この中には一つの空間の大きさの哲学問題が含まれています.私たちはrehashの時に、二つの超大型の行列が同時に存在しています.だから、境界を越えないために.
最大の容量は2^30で、2^31ではありません!!
まず、コンストラクタを確認します.
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}初期化容量を任意に設定することはできないようです.最大で最大値に達することができますが、装填因子は0以下の値でなければ大丈夫です.
実際には、装填因子が1.0より大きいのは非常に悪い数字です.
データを保存するには、チェーンテーブルの配列が必要です.オブジェクト変数を見てみます.
transient Node[] table;
transient Set> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor; 添削して調べる順番によって、まずputの方面の方法を見ます.
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab;
Node p;
int n, i;
// ，tab table
// if hashmap
// clear tab
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;// tab （ table）， n
if ((p = tab[i = (n - 1) & hash]) == null)// ，
// （n-1）&hash， hash
// 2 ，（n-1）&hash == hash%n
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;// key null 、hash ，
else if (p instanceof TreeNode)
// ，
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {//binCount
if ((e = p.next) == null) {
// ，
// binCount ，
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// hash/key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
// ，
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);// LinkedHashMap
return oldValue;
}
}
++modCount;// value ，
if (++size > threshold)
resize();// ，
afterNodeInsertion(evict);// LinkedHashMap ，
return null;// null
} 1、存在しないキーのペアを挿入したらmodCountを修正します.
2、キーパッドの値ペアだけを更新したら(k=v 1がk=v 2)、古い値v 1に戻ります.そうしないとnullに戻ります.
3、ツリー化閾値を超えるとツリーになります.
4、ノードkey検査をしないので、nullでもいいです.valueもそうです.
5、挿入ノードは、最後の挿し方を採用して、hash/keyの同じノードを探して更新しやすいです.
6、挿入プロセスはnがいつも2のx乗であるため、hash%nの代わりに(n-1)&hashを使用する.
第四点を説明するために、小さな実験をしました.
public static void main(String[] args){
HashMap hashMap=new HashMap<>();
hashMap.put(null,"value1");
hashMap.put(2,null);
System.out.println(hashMap);//{null=value1, 2=null}
hashMap.put(null,null);
System.out.println(hashMap);//{null=null, 2=null}
} しかし
public static void main(String[] args){
Hashtable hashtable=new Hashtable<>();
hashtable.put(null,1);//NullPointerException
hashtable.put(2,null);//NullPointerException
System.out.println(hashtable);
} まず、彼の拡大規則を観察します.最初のifから分かります.最初のテーブル配列はnullで、何もありません.
最初の要素を置くと、新規作成が開始されます.
それでは、そのレシオ関数を見てみます.
final Node[] resize() {//capacity*lordfactor=threshold
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//
int oldThr = threshold;//
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// ，
// rehash ， table
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// cap 2* ， （16）， 2
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0)
// oldCap==0 threshold
newCap = oldThr;
else {
//new HashMap<>() ， 16 12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 0 ，
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;//
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];//
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;// ， GC
if (e.next == null)// ，
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// ， ( )
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {//rehash
next = e.next;
if ((e.hash & oldCap) == 0) {
// cap 0b10...0 ，
// hash 1
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {//
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
} 1、パラメータnewがないhashMap初期化容量は16で、閾値12.
2、毎回新容量は元の2倍です.
3、容量がもう拡大できない場合、閾値を直接最大正の整数に設定する.
4、rehashプロセスは最高位の1分割のアルゴリズムを採用しています.具体的なプロセスは以下の通りです.
capacityはいつも2の倍数なので、最高位は1、他のビットは0です.1…n個の0を仮定してもいいです.
その後、拡張された新しい配列は1…n＋1個の0であり、この位置のチェーンノードのhashには1があり、対応するビットは0があり、次いで元の配列のj番目のノードである.
元の挿入位置を考慮してhash%n、新しい位置はhash%(2*n)です.じゃhash=b*n+j (jは挿入位置ですので)
だからhash%(2 n)は二つの結果しかないです!それはn＋jとjです.なぜですか?bが偶数の場合はhash%(2 n)=0+jとなり、bが奇数の場合は1*n＋jとなり、2つの新しいチェーンの挿入位置を完全に決定することができるからです.(お母さんや書庫のプログラマーはすごいです)
そして、奇数は1で終わる(2進数)、偶数は0で終わるので、capの最高位1は「&」である限り、bは奇数か偶数かが分かります.このようにして、もっと時間を節約する方法でrehashはチェーンテーブルについて(直接addのようなプロセスを使うと、毎回新しいチェーンをスキャンするのに時間がかかります).
今は木化(addの時のtreefify)とrehashの過程のsplitを見てみます.
final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
//e
TreeNode hd = null, tl = null;
do {
TreeNode p = replacementTreeNode(e, null);//
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);// （ ）
if ((tab[index] = hd) != null)
hd.treeify(tab);// ， hd
}
}
TreeNode replacementTreeNode(Node p, Node next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
//
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
} 前に見たブログでは、チェーンノードを直接に一連の措置(例えば元の場所で回転するなど)で赤と黒の木になると思っていました.
しかし、実際:
ツリー化プロセスは、まずprevとnextポインタでツリーの前駆と後続を指し、ツリー化の変換を行う.
さて、treeify関数は本当にツリーノードをツリーに変換するべきです.どのような過程なのかを見てみます.
final void treeify(Node[] tab) {
// treeify TreeNode
TreeNode root = null;
for (TreeNode x = this, next; x != null; x = next) {
next = (TreeNode)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class> kc = null;
for (TreeNode p = root;;) {
int dir, ph;
K pk = p.key;
// ：
// hash key
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode xp = p;
// ，
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);//
break;
}
}
}
}
moveRootToFront(tab, root);//
} 一連の挿入を経て、ツリーのルートは必ずしも配列の頭ではないので、moveRoot ToFrontはルートノードを配列溝の位置に変えます.
final void split(HashMap map, Node[] tab, int index, int bit) {
TreeNode b = this;
// Relink into lo and hi lists, preserving order
TreeNode loHead = null, loTail = null;
TreeNode hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode e = b, next; e != null; e = next) {
next = (TreeNode)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
} 私達は好奇心を禁じ得ません.中順を使って再帰するべきではないですか?
でも忘れましたか?prevとnextの指針がありますよ.だから:
チェーンのように分割する方法(1分割アルゴリズム)だけでいいです.
その後、分割が完了しても、ツリー化閾値より大きいと、依然としてツリーに変換される.
分割が完了したら、逆ツリー化閾値より小さい場合は、チェーンで挿入します.
これでもう一つのキーがどのように挿入されるかが終了しました.
便宜上、次はget方法を見てみると、スーパー実用的なキーでvalueを探します.
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {//
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;// key
if ((e = first.next) != null) {
if (first instanceof TreeNode)
// ，
return ((TreeNode)first).getTreeNode(hash, key);
do {// ，
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;// null null
}
final TreeNode getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
final TreeNode find(int h, Object k, Class> kc) {//
TreeNode p = this;
do {
int ph, dir; K pk;
TreeNode pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
まず、hashの対応する位置を計算します.この位置が現在ツリー構造であれば、ツリーのlogN方法で検索します.そうでなければ、チェーンの線形検索です.
上記と同じプロセスでcontainsKeyのコードを得ることができます.
もう一つのcontainValue方法がありますか?
public boolean containsValue(Object value) {
Node[] tab; V v;
if ((tab = table) != null && size > 0) {
for (Node e : tab) {
for (; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
} また、
keySetとvalueSetについては、初期化(怠惰なローディング)を行わず、その後、ローズマリーによって巡回を完了します.つまり、Setを新たに作ったのではなく、ローズマリーを生成しました.
それから「削除」の方法を見てみて、削除は中のremoveです.
public V remove(Object key) {
Node e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node[] tab; Node p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)//
node = ((TreeNode)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}//
p = e;
} while ((e = e.next) != null);
}
}
// ， ，
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
} そしてクリア:
public void clear() {
Node[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
} そして簡単には交換できません.
public boolean replace(K key, V oldValue, V newValue) {
Node e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
@Override
public V replace(K key, V value) {
Node e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
} これで面接の「高周波」が一段落しました.