轉(zhuǎn)載 請(qǐng)注明原文地址：http://www.cnblogs.com/ygj0930/p/6538779.html?

??? Java中常用的Map實(shí)現(xiàn)類主要有：HashMap、HashTable、TreeMap、LinkedHashMap。

??? 一：HashMap

??? HashMap的底層其實(shí)是“鏈表的數(shù)組”，即：每個(gè)元素其實(shí)存放著一個(gè)鏈表，鏈表存放著哈希值相同的對(duì)象們。

???

??? 1：新建HashMap，其實(shí)是新建了一個(gè)數(shù)組

public HashMap(int initialCapacity, float loadFactor) {// initialCapacity代表初始化HashMap的容量，它的最大容量是MAXIMUM_CAPACITY = 1 << 30。if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;// loadFactor代表它的負(fù)載因子，默認(rèn)是是DEFAULT_LOAD_FACTOR=0.75，用來計(jì)算threshold臨界值的。if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);// Find a power of 2 >= initialCapacityint capacity = 1;while (capacity < initialCapacity)capacity <<= 1;this.loadFactor = loadFactor;threshold = (int)(capacity * loadFactor);table = new Entry[capacity];//創(chuàng)建數(shù)組init();}

??? 2：插入元素

public V put(K key, V value) {// HashMap允許存放null鍵和null值。// 當(dāng)key為null時(shí)，調(diào)用putForNullKey方法，將value放置在數(shù)組第一個(gè)位置。if (key == null)return putForNullKey(value);// 根據(jù)key的hashCode重新計(jì)算hash值。int hash = hash(key.hashCode());// 搜索指定hash值所對(duì)應(yīng)table中的索引。int i = indexFor(hash, table.length);// 如果 i 索引處的 Entry 不為 null，通過循環(huán)不斷遍歷 e 元素的下一個(gè)元素。for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}// 如果i索引處的Entry為null，表明此處還沒有Entry。// modCount記錄HashMap中修改結(jié)構(gòu)的次數(shù)modCount++;// 將key、value添加到i索引處。 addEntry(hash, key, value, i);return null; } void addEntry(int hash, K key, V value, int bucketIndex) {// 獲取指定 bucketIndex 索引處的 Entry Entry<K,V> e = table[bucketIndex];// 將新創(chuàng)建的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entrytable[bucketIndex] = new Entry<K,V>(hash, key, value, e);// 如果 Map 中的 key-value 對(duì)的數(shù)量超過了極限if (size++ >= threshold)// 把 table 對(duì)象的長度擴(kuò)充到原來的2倍。resize(2 * table.length); } static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) {return h & (length-1); }
//它通過?h & (table.length -1)?來得到該對(duì)象的保存位，而HashMap底層數(shù)組的長度總是?2?的n?次方，這是HashMap在速度上的優(yōu)化。
//當(dāng)length總是?2?的n次方時(shí)，h& (length-1)運(yùn)算等價(jià)于對(duì)length取模，也就是h%length，但是&比%具有更高的效率。

? ? ?? 1）HashMap不是簡單的用key的hashcode()值作為元素的存放下標(biāo)的，而是通過二次哈希——把key的hashcode()傳進(jìn)HashMap自定義的hash(h)方法中計(jì)算位置（有可能大于數(shù)組長度了，所以還要對(duì)數(shù)組長取余），然后通過indexFor(h，len)方法計(jì)算出具體的數(shù)組下標(biāo)（用 按位與 取代 取余 加快效率），盡量讓key盡可能均勻的分配到數(shù)組上去，避免造成Hash堆積（某一下標(biāo)處存放的鏈表過長）。

???????? 2）HashMap的沖突解決：如果有兩個(gè)key的hashcode相同，那么經(jīng)過hash(h)二次哈希后得到的數(shù)組索引是一樣的，此時(shí)就要判斷這兩個(gè)key是否是同一對(duì)象：如果兩個(gè)key的equals方法返回true，則說明兩個(gè)key是同一對(duì)象，則此時(shí)把新值覆蓋掉舊值；如果equals返回false，則說明是兩個(gè)不同的key但分配到了同一數(shù)組索引位存放，則此時(shí)把新增的value添加到該索引位的鏈表尾。

??? 3：讀取元素

public V get(Object key) {if (key == null)return getForNullKey();int hash = hash(key.hashCode());for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k)))return e.value;}return null; }

?

?????? 在插入元素時(shí)我們看到，不同對(duì)象也有可能會(huì)有相同的哈希值，所以存放的時(shí)候數(shù)組索引是一樣的。所以，我們通過key去獲取value時(shí)不能只靠數(shù)組索引，還需在數(shù)組索引找到對(duì)應(yīng)鏈表頭的基礎(chǔ)上，從頭到尾遍歷鏈表，把鏈表每個(gè)元素(Entry)的key與所查詢的key通過equals方法進(jìn)行比對(duì)，找到相等的結(jié)點(diǎn)來獲取值。

??? 也就是說：插入元素時(shí)，通過key的hashcode()以及hash算法決定索引，通過equals()決定是插入鏈表還是覆蓋原有值；

????????????????? 讀取元素時(shí)，通過key的hashcode()以及hash算法找到索引，通過equals()遍歷鏈表找到相對(duì)應(yīng)的結(jié)點(diǎn)值；

? ? ? ? ? ? ? ? ? （注：Map存儲(chǔ)的是 鍵值對(duì) ，不是單指用 key 來索引 value。而是用key 來索引 Entry！Entry就是我們說的 鍵值對(duì)！因此，get()時(shí)確定槽位后，在遍歷Entry鏈表時(shí)才可以把查找的key與鏈表結(jié)點(diǎn)的key進(jìn)行比較。）

???? 4：數(shù)組擴(kuò)容

????? 我們?cè)谇懊娌迦朐貢r(shí)就看到，當(dāng)HashMap底層所用的數(shù)組使用量大于等于? 數(shù)組最大容量*負(fù)債因子? 時(shí)，就會(huì)觸發(fā)數(shù)組擴(kuò)容。?

//HashMap數(shù)組擴(kuò)容void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;//如果當(dāng)前的數(shù)組長度已經(jīng)達(dá)到最大值，則不在進(jìn)行調(diào)整if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}//根據(jù)傳入?yún)?shù)的長度定義新的數(shù)組Entry[] newTable = new Entry[newCapacity];//按照新的規(guī)則，將舊數(shù)組中的元素轉(zhuǎn)移到新數(shù)組中 transfer(newTable);table = newTable;//更新臨界值threshold = (int)(newCapacity * loadFactor);}//舊數(shù)組中元素往新數(shù)組中遷移void transfer(Entry[] newTable) {//舊數(shù)組Entry[] src = table;//新數(shù)組長度int newCapacity = newTable.length;//遍歷舊數(shù)組for (int j = 0; j < src.length; j++) {Entry<K,V> e = src[j];if (e != null) {src[j] = null;do {Entry<K,V> next = e.next;int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;} while (e != null);}}}

???? 5：HashMap線程不安全

???? HashMap線程不安全的原因從上面的代碼可以看出端倪——沖突的解決以及數(shù)組擴(kuò)容? 在多線程下容易發(fā)生競態(tài)條件（結(jié)果取決于執(zhí)行的順序）。

???? 沖突造成不安全：當(dāng)多個(gè)線程共同操作一個(gè)HashMap對(duì)象時(shí)，某一時(shí)刻都向map的key擁有相同的hashcode，若key是相同的對(duì)象，則最終的value值取決于哪個(gè)線程是最終執(zhí)行的，覆蓋掉前面的值；如果key是不同的對(duì)象，我們知道此時(shí)把值插入鏈表，而鏈表當(dāng)前結(jié)點(diǎn)只有一個(gè)next指針，那么多個(gè)線程中都已緩存了這個(gè)指針，都認(rèn)為這個(gè)指針是可用的，并令它指向了當(dāng)前插入的新結(jié)點(diǎn)。那么最后同步回主內(nèi)存時(shí)就會(huì)出問題了：指針只有一個(gè)。不能同時(shí)指向多個(gè)結(jié)點(diǎn)。

???? 擴(kuò)容造成的不安全：當(dāng)多個(gè)線程共同操作一個(gè)HashMap對(duì)象時(shí)，某一時(shí)刻同時(shí)觸發(fā)了數(shù)組擴(kuò)容，那么線程輪換執(zhí)行時(shí)都對(duì)這個(gè)數(shù)組進(jìn)行擴(kuò)容會(huì)覆蓋掉前面線程的擴(kuò)容結(jié)果。

?

??? 二：HashTable

??? HashTable底層也是一個(gè)“鏈表數(shù)組”，其插入元素和查詢?cè)氐牟呗耘cHashMap幾乎一樣。不同的是：很多線程敏感的方法用syncrhoized關(guān)鍵字進(jìn)行修飾。所以，我們說：HashTable是線程安全的。（類似于Vector對(duì)ArrayList線程敏感的方法進(jìn)行限定）

package java.util;2 import java.io.*;3 4 public class Hashtable<K,V>5 extends Dictionary<K,V>6 implements Map<K,V>, Cloneable, java.io.Serializable {7 8 // Hashtable保存key-value的數(shù)組。9 // Hashtable是采用拉鏈法實(shí)現(xiàn)的，每一個(gè)Entry本質(zhì)上是一個(gè)單向鏈表10 private transient Entry[] table;11 12 // Hashtable中元素的實(shí)際數(shù)量13 private transient int count;14 15 // 閾值，用于判斷是否需要調(diào)整Hashtable的容量（threshold = 容量*加載因子）16 private int threshold;17 18 // 加載因子19 private float loadFactor;20 21 // Hashtable被改變的次數(shù)22 private transient int modCount = 0;23 24 // 序列版本號(hào)25 private static final long serialVersionUID = 1421746759512286392L;26 27 // 指定“容量大小”和“加載因子”的構(gòu)造函數(shù)28 public Hashtable(int initialCapacity, float loadFactor) {29 if (initialCapacity < 0)30 throw new IllegalArgumentException("Illegal Capacity: "+31 initialCapacity);32 if (loadFactor <= 0 || Float.isNaN(loadFactor))33 throw new IllegalArgumentException("Illegal Load: "+loadFactor);34 35 if (initialCapacity==0)36 initialCapacity = 1;37 this.loadFactor = loadFactor;38 table = new Entry[initialCapacity];39 threshold = (int)(initialCapacity * loadFactor);40 }41 42 // 指定“容量大小”的構(gòu)造函數(shù)43 public Hashtable(int initialCapacity) {44 this(initialCapacity, 0.75f);45 }46 47 // 默認(rèn)構(gòu)造函數(shù)。48 public Hashtable() {49 // 默認(rèn)構(gòu)造函數(shù)，指定的容量大小是11；加載因子是0.7550 this(11, 0.75f);51 }52 53 // 包含“子Map”的構(gòu)造函數(shù)54 public Hashtable(Map<? extends K, ? extends V> t) {55 this(Math.max(2*t.size(), 11), 0.75f);56 // 將“子Map”的全部元素都添加到Hashtable中57 putAll(t);58 }59 60 public synchronized int size() {61 return count;62 }63 64 public synchronized boolean isEmpty() {65 return count == 0;66 }67 68 // 返回“所有key”的枚舉對(duì)象69 public synchronized Enumeration<K> keys() {70 return this.<K>getEnumeration(KEYS);71 }72 73 // 返回“所有value”的枚舉對(duì)象74 public synchronized Enumeration<V> elements() {75 return this.<V>getEnumeration(VALUES);76 }77 78 // 判斷Hashtable是否包含“值(value)”79 public synchronized boolean contains(Object value) {80 // Hashtable中“鍵值對(duì)”的value不能是null，81 // 若是null的話，拋出異常!82 if (value == null) {83 throw new NullPointerException();84 }85 86 // 從后向前遍歷table數(shù)組中的元素(Entry)87 // 對(duì)于每個(gè)Entry(單向鏈表)，逐個(gè)遍歷，判斷節(jié)點(diǎn)的值是否等于value88 Entry tab[] = table;89 for (int i = tab.length ; i-- > 0 ;) {90 for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {91 if (e.value.equals(value)) {92 return true;93 }94 }95 }96 return false;97 }98 99 public boolean containsValue(Object value) { 100 return contains(value); 101 } 102 103 // 判斷Hashtable是否包含key 104 public synchronized boolean containsKey(Object key) { 105 Entry tab[] = table; 106 int hash = key.hashCode(); 107 // 計(jì)算索引值， 108 // % tab.length 的目的是防止數(shù)據(jù)越界 109 int index = (hash & 0x7FFFFFFF) % tab.length; 110 // 找到“key對(duì)應(yīng)的Entry(鏈表)”，然后在鏈表中找出“哈希值”和“鍵值”與key都相等的元素 111 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 112 if ((e.hash == hash) && e.key.equals(key)) { 113 return true; 114 } 115 } 116 return false; 117 } 118 119 // 返回key對(duì)應(yīng)的value，沒有的話返回null 120 public synchronized V get(Object key) { 121 Entry tab[] = table; 122 int hash = key.hashCode(); 123 // 計(jì)算索引值， 124 int index = (hash & 0x7FFFFFFF) % tab.length; 125 // 找到“key對(duì)應(yīng)的Entry(鏈表)”，然后在鏈表中找出“哈希值”和“鍵值”與key都相等的元素 126 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 127 if ((e.hash == hash) && e.key.equals(key)) { 128 return e.value; 129 } 130 } 131 return null; 132 } 133 134 // 調(diào)整Hashtable的長度，將長度變成原來的(2倍+1) 135 // (01) 將“舊的Entry數(shù)組”賦值給一個(gè)臨時(shí)變量。 136 // (02) 創(chuàng)建一個(gè)“新的Entry數(shù)組”，并賦值給“舊的Entry數(shù)組” 137 // (03) 將“Hashtable”中的全部元素依次添加到“新的Entry數(shù)組”中 138 protected void rehash() { 139 int oldCapacity = table.length; 140 Entry[] oldMap = table; 141 142 int newCapacity = oldCapacity * 2 + 1; 143 Entry[] newMap = new Entry[newCapacity]; 144 145 modCount++; 146 threshold = (int)(newCapacity * loadFactor); 147 table = newMap; 148 149 for (int i = oldCapacity ; i-- > 0 ;) { 150 for (Entry<K,V> old = oldMap[i] ; old != null ; ) { 151 Entry<K,V> e = old; 152 old = old.next; 153 154 int index = (e.hash & 0x7FFFFFFF) % newCapacity; 155 e.next = newMap[index]; 156 newMap[index] = e; 157 } 158 } 159 } 160 161 // 將“key-value”添加到Hashtable中 162 public synchronized V put(K key, V value) { 163 // Hashtable中不能插入value為null的元素！！！ 164 if (value == null) { 165 throw new NullPointerException(); 166 } 167 168 // 若“Hashtable中已存在鍵為key的鍵值對(duì)”， 169 // 則用“新的value”替換“舊的value” 170 Entry tab[] = table; 171 int hash = key.hashCode(); 172 int index = (hash & 0x7FFFFFFF) % tab.length; 173 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 174 if ((e.hash == hash) && e.key.equals(key)) { 175 V old = e.value; 176 e.value = value; 177 return old; 178 } 179 } 180 181 // 若“Hashtable中不存在鍵為key的鍵值對(duì)”， 182 // (01) 將“修改統(tǒng)計(jì)數(shù)”+1 183 modCount++; 184 // (02) 若“Hashtable實(shí)際容量” > “閾值”(閾值=總的容量 * 加載因子) 185 // 則調(diào)整Hashtable的大小 186 if (count >= threshold) { 187 // Rehash the table if the threshold is exceeded 188 rehash(); 189 190 tab = table; 191 index = (hash & 0x7FFFFFFF) % tab.length; 192 } 193 194 // (03) 將“Hashtable中index”位置的Entry(鏈表)保存到e中 195 Entry<K,V> e = tab[index]; 196 // (04) 創(chuàng)建“新的Entry節(jié)點(diǎn)”，并將“新的Entry”插入“Hashtable的index位置”，并設(shè)置e為“新的Entry”的下一個(gè)元素(即“新Entry”為鏈表表頭)。 197 tab[index] = new Entry<K,V>(hash, key, value, e); 198 // (05) 將“Hashtable的實(shí)際容量”+1 199 count++; 200 return null; 201 } 202 203 // 刪除Hashtable中鍵為key的元素 204 public synchronized V remove(Object key) { 205 Entry tab[] = table; 206 int hash = key.hashCode(); 207 int index = (hash & 0x7FFFFFFF) % tab.length; 208 // 找到“key對(duì)應(yīng)的Entry(鏈表)” 209 // 然后在鏈表中找出要?jiǎng)h除的節(jié)點(diǎn)，并刪除該節(jié)點(diǎn)。 210 for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) { 211 if ((e.hash == hash) && e.key.equals(key)) { 212 modCount++; 213 if (prev != null) { 214 prev.next = e.next; 215 } else { 216 tab[index] = e.next; 217 } 218 count--; 219 V oldValue = e.value; 220 e.value = null; 221 return oldValue; 222 } 223 } 224 return null; 225 } 226 227 // 將“Map(t)”的中全部元素逐一添加到Hashtable中 228 public synchronized void putAll(Map<? extends K, ? extends V> t) { 229 for (Map.Entry<? extends K, ? extends V> e : t.entrySet()) 230 put(e.getKey(), e.getValue()); 231 } 232 233 // 清空Hashtable 234 // 將Hashtable的table數(shù)組的值全部設(shè)為null 235 public synchronized void clear() { 236 Entry tab[] = table; 237 modCount++; 238 for (int index = tab.length; --index >= 0; ) 239 tab[index] = null; 240 count = 0; 241 } 242 243 // 克隆一個(gè)Hashtable，并以O(shè)bject的形式返回。 244 public synchronized Object clone() { 245 try { 246 Hashtable<K,V> t = (Hashtable<K,V>) super.clone(); 247 t.table = new Entry[table.length]; 248 for (int i = table.length ; i-- > 0 ; ) { 249 t.table[i] = (table[i] != null) 250 ? (Entry<K,V>) table[i].clone() : null; 251 } 252 t.keySet = null; 253 t.entrySet = null; 254 t.values = null; 255 t.modCount = 0; 256 return t; 257 } catch (CloneNotSupportedException e) { 258 // this shouldn't happen, since we are Cloneable 259 throw new InternalError(); 260 } 261 } 262 263 public synchronized String toString() { 264 int max = size() - 1; 265 if (max == -1) 266 return "{}"; 267 268 StringBuilder sb = new StringBuilder(); 269 Iterator<Map.Entry<K,V>> it = entrySet().iterator(); 270 271 sb.append('{'); 272 for (int i = 0; ; i++) { 273 Map.Entry<K,V> e = it.next(); 274 K key = e.getKey(); 275 V value = e.getValue(); 276 sb.append(key == this ? "(this Map)" : key.toString()); 277 sb.append('='); 278 sb.append(value == this ? "(this Map)" : value.toString()); 279 280 if (i == max) 281 return sb.append('}').toString(); 282 sb.append(", "); 283 } 284 } 285 286 // 獲取Hashtable的枚舉類對(duì)象 287 // 若Hashtable的實(shí)際大小為0,則返回“空枚舉類”對(duì)象； 288 // 否則，返回正常的Enumerator的對(duì)象。(Enumerator實(shí)現(xiàn)了迭代器和枚舉兩個(gè)接口) 289 private <T> Enumeration<T> getEnumeration(int type) { 290 if (count == 0) { 291 return (Enumeration<T>)emptyEnumerator; 292 } else { 293 return new Enumerator<T>(type, false); 294 } 295 } 296 297 // 獲取Hashtable的迭代器 298 // 若Hashtable的實(shí)際大小為0,則返回“空迭代器”對(duì)象； 299 // 否則，返回正常的Enumerator的對(duì)象。(Enumerator實(shí)現(xiàn)了迭代器和枚舉兩個(gè)接口) 300 private <T> Iterator<T> getIterator(int type) { 301 if (count == 0) { 302 return (Iterator<T>) emptyIterator; 303 } else { 304 return new Enumerator<T>(type, true); 305 } 306 } 307 308 // Hashtable的“key的集合”。它是一個(gè)Set，意味著沒有重復(fù)元素 309 private transient volatile Set<K> keySet = null; 310 // Hashtable的“key-value的集合”。它是一個(gè)Set，意味著沒有重復(fù)元素 311 private transient volatile Set<Map.Entry<K,V>> entrySet = null; 312 // Hashtable的“key-value的集合”。它是一個(gè)Collection，意味著可以有重復(fù)元素 313 private transient volatile Collection<V> values = null; 314 315 // 返回一個(gè)被synchronizedSet封裝后的KeySet對(duì)象 316 // synchronizedSet封裝的目的是對(duì)KeySet的所有方法都添加synchronized，實(shí)現(xiàn)多線程同步 317 public Set<K> keySet() { 318 if (keySet == null) 319 keySet = Collections.synchronizedSet(new KeySet(), this); 320 return keySet; 321 } 322 323 // Hashtable的Key的Set集合。 324 // KeySet繼承于AbstractSet，所以，KeySet中的元素沒有重復(fù)的。 325 private class KeySet extends AbstractSet<K> { 326 public Iterator<K> iterator() { 327 return getIterator(KEYS); 328 } 329 public int size() { 330 return count; 331 } 332 public boolean contains(Object o) { 333 return containsKey(o); 334 } 335 public boolean remove(Object o) { 336 return Hashtable.this.remove(o) != null; 337 } 338 public void clear() { 339 Hashtable.this.clear(); 340 } 341 } 342 343 // 返回一個(gè)被synchronizedSet封裝后的EntrySet對(duì)象 344 // synchronizedSet封裝的目的是對(duì)EntrySet的所有方法都添加synchronized，實(shí)現(xiàn)多線程同步 345 public Set<Map.Entry<K,V>> entrySet() { 346 if (entrySet==null) 347 entrySet = Collections.synchronizedSet(new EntrySet(), this); 348 return entrySet; 349 } 350 351 // Hashtable的Entry的Set集合。 352 // EntrySet繼承于AbstractSet，所以，EntrySet中的元素沒有重復(fù)的。 353 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 354 public Iterator<Map.Entry<K,V>> iterator() { 355 return getIterator(ENTRIES); 356 } 357 358 public boolean add(Map.Entry<K,V> o) { 359 return super.add(o); 360 } 361 362 // 查找EntrySet中是否包含Object(0) 363 // 首先，在table中找到o對(duì)應(yīng)的Entry(Entry是一個(gè)單向鏈表) 364 // 然后，查找Entry鏈表中是否存在Object 365 public boolean contains(Object o) { 366 if (!(o instanceof Map.Entry)) 367 return false; 368 Map.Entry entry = (Map.Entry)o; 369 Object key = entry.getKey(); 370 Entry[] tab = table; 371 int hash = key.hashCode(); 372 int index = (hash & 0x7FFFFFFF) % tab.length; 373 374 for (Entry e = tab[index]; e != null; e = e.next) 375 if (e.hash==hash && e.equals(entry)) 376 return true; 377 return false; 378 } 379 380 // 刪除元素Object(0) 381 // 首先，在table中找到o對(duì)應(yīng)的Entry(Entry是一個(gè)單向鏈表) 382 // 然后，刪除鏈表中的元素Object 383 public boolean remove(Object o) { 384 if (!(o instanceof Map.Entry)) 385 return false; 386 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 387 K key = entry.getKey(); 388 Entry[] tab = table; 389 int hash = key.hashCode(); 390 int index = (hash & 0x7FFFFFFF) % tab.length; 391 392 for (Entry<K,V> e = tab[index], prev = null; e != null; 393 prev = e, e = e.next) { 394 if (e.hash==hash && e.equals(entry)) { 395 modCount++; 396 if (prev != null) 397 prev.next = e.next; 398 else 399 tab[index] = e.next; 400 401 count--; 402 e.value = null; 403 return true; 404 } 405 } 406 return false; 407 } 408 409 public int size() { 410 return count; 411 } 412 413 public void clear() { 414 Hashtable.this.clear(); 415 } 416 } 417 418 // 返回一個(gè)被synchronizedCollection封裝后的ValueCollection對(duì)象 419 // synchronizedCollection封裝的目的是對(duì)ValueCollection的所有方法都添加synchronized，實(shí)現(xiàn)多線程同步 420 public Collection<V> values() { 421 if (values==null) 422 values = Collections.synchronizedCollection(new ValueCollection(), 423 this); 424 return values; 425 } 426 427 // Hashtable的value的Collection集合。 428 // ValueCollection繼承于AbstractCollection，所以，ValueCollection中的元素可以重復(fù)的。 429 private class ValueCollection extends AbstractCollection<V> { 430 public Iterator<V> iterator() { 431 return getIterator(VALUES); 432 } 433 public int size() { 434 return count; 435 } 436 public boolean contains(Object o) { 437 return containsValue(o); 438 } 439 public void clear() { 440 Hashtable.this.clear(); 441 } 442 } 443 444 // 重新equals()函數(shù) 445 // 若兩個(gè)Hashtable的所有key-value鍵值對(duì)都相等，則判斷它們兩個(gè)相等 446 public synchronized boolean equals(Object o) { 447 if (o == this) 448 return true; 449 450 if (!(o instanceof Map)) 451 return false; 452 Map<K,V> t = (Map<K,V>) o; 453 if (t.size() != size()) 454 return false; 455 456 try { 457 // 通過迭代器依次取出當(dāng)前Hashtable的key-value鍵值對(duì) 458 // 并判斷該鍵值對(duì)，存在于Hashtable(o)中。 459 // 若不存在，則立即返回false；否則，遍歷完“當(dāng)前Hashtable”并返回true。 460 Iterator<Map.Entry<K,V>> i = entrySet().iterator(); 461 while (i.hasNext()) { 462 Map.Entry<K,V> e = i.next(); 463 K key = e.getKey(); 464 V value = e.getValue(); 465 if (value == null) { 466 if (!(t.get(key)==null && t.containsKey(key))) 467 return false; 468 } else { 469 if (!value.equals(t.get(key))) 470 return false; 471 } 472 } 473 } catch (ClassCastException unused) { 474 return false; 475 } catch (NullPointerException unused) { 476 return false; 477 } 478 479 return true; 480 } 481 482 // 計(jì)算Hashtable的哈希值 483 // 若 Hashtable的實(shí)際大小為0 或者 加載因子<0，則返回0。 484 // 否則，返回“Hashtable中的每個(gè)Entry的key和value的異或值 的總和”。 485 public synchronized int hashCode() { 486 int h = 0; 487 if (count == 0 || loadFactor < 0) 488 return h; // Returns zero 489 490 loadFactor = -loadFactor; // Mark hashCode computation in progress 491 Entry[] tab = table; 492 for (int i = 0; i < tab.length; i++) 493 for (Entry e = tab[i]; e != null; e = e.next) 494 h += e.key.hashCode() ^ e.value.hashCode(); 495 loadFactor = -loadFactor; // Mark hashCode computation complete 496 497 return h; 498 } 499 500 // java.io.Serializable的寫入函數(shù) 501 // 將Hashtable的“總的容量，實(shí)際容量，所有的Entry”都寫入到輸出流中 502 private synchronized void writeObject(java.io.ObjectOutputStream s) 503 throws IOException 504 { 505 // Write out the length, threshold, loadfactor 506 s.defaultWriteObject(); 507 508 // Write out length, count of elements and then the key/value objects 509 s.writeInt(table.length); 510 s.writeInt(count); 511 for (int index = table.length-1; index >= 0; index--) { 512 Entry entry = table[index]; 513 514 while (entry != null) { 515 s.writeObject(entry.key); 516 s.writeObject(entry.value); 517 entry = entry.next; 518 } 519 } 520 } 521 522 // java.io.Serializable的讀取函數(shù)：根據(jù)寫入方式讀出 523 // 將Hashtable的“總的容量，實(shí)際容量，所有的Entry”依次讀出 524 private void readObject(java.io.ObjectInputStream s) 525 throws IOException, ClassNotFoundException 526 { 527 // Read in the length, threshold, and loadfactor 528 s.defaultReadObject(); 529 530 // Read the original length of the array and number of elements 531 int origlength = s.readInt(); 532 int elements = s.readInt(); 533 534 // Compute new size with a bit of room 5% to grow but 535 // no larger than the original size. Make the length 536 // odd if it's large enough, this helps distribute the entries. 537 // Guard against the length ending up zero, that's not valid. 538 int length = (int)(elements * loadFactor) + (elements / 20) + 3; 539 if (length > elements && (length & 1) == 0) 540 length--; 541 if (origlength > 0 && length > origlength) 542 length = origlength; 543 544 Entry[] table = new Entry[length]; 545 count = 0; 546 547 // Read the number of elements and then all the key/value objects 548 for (; elements > 0; elements--) { 549 K key = (K)s.readObject(); 550 V value = (V)s.readObject(); 551 // synch could be eliminated for performance 552 reconstitutionPut(table, key, value); 553 } 554 this.table = table; 555 } 556 557 private void reconstitutionPut(Entry[] tab, K key, V value) 558 throws StreamCorruptedException 559 { 560 if (value == null) { 561 throw new java.io.StreamCorruptedException(); 562 } 563 // Makes sure the key is not already in the hashtable. 564 // This should not happen in deserialized version. 565 int hash = key.hashCode(); 566 int index = (hash & 0x7FFFFFFF) % tab.length; 567 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 568 if ((e.hash == hash) && e.key.equals(key)) { 569 throw new java.io.StreamCorruptedException(); 570 } 571 } 572 // Creates the new entry. 573 Entry<K,V> e = tab[index]; 574 tab[index] = new Entry<K,V>(hash, key, value, e); 575 count++; 576 } 577 578 // Hashtable的Entry節(jié)點(diǎn)，它本質(zhì)上是一個(gè)單向鏈表。 579 // 也因此，我們才能推斷出Hashtable是由拉鏈法實(shí)現(xiàn)的散列表 580 private static class Entry<K,V> implements Map.Entry<K,V> { 581 // 哈希值 582 int hash; 583 K key; 584 V value; 585 // 指向的下一個(gè)Entry，即鏈表的下一個(gè)節(jié)點(diǎn) 586 Entry<K,V> next; 587 588 // 構(gòu)造函數(shù) 589 protected Entry(int hash, K key, V value, Entry<K,V> next) { 590 this.hash = hash; 591 this.key = key; 592 this.value = value; 593 this.next = next; 594 } 595 596 protected Object clone() { 597 return new Entry<K,V>(hash, key, value, 598 (next==null ? null : (Entry<K,V>) next.clone())); 599 } 600 601 public K getKey() { 602 return key; 603 } 604 605 public V getValue() { 606 return value; 607 } 608 609 // 設(shè)置value。若value是null，則拋出異常。 610 public V setValue(V value) { 611 if (value == null) 612 throw new NullPointerException(); 613 614 V oldValue = this.value; 615 this.value = value; 616 return oldValue; 617 } 618 619 // 覆蓋equals()方法，判斷兩個(gè)Entry是否相等。 620 // 若兩個(gè)Entry的key和value都相等，則認(rèn)為它們相等。 621 public boolean equals(Object o) { 622 if (!(o instanceof Map.Entry)) 623 return false; 624 Map.Entry e = (Map.Entry)o; 625 626 return (key==null ? e.getKey()==null : key.equals(e.getKey())) && 627 (value==null ? e.getValue()==null : value.equals(e.getValue())); 628 } 629 630 public int hashCode() { 631 return hash ^ (value==null ? 0 : value.hashCode()); 632 } 633 634 public String toString() { 635 return key.toString()+"="+value.toString(); 636 } 637 } 638 639 private static final int KEYS = 0; 640 private static final int VALUES = 1; 641 private static final int ENTRIES = 2; 642 643 // Enumerator的作用是提供了“通過elements()遍歷Hashtable的接口” 和 “通過entrySet()遍歷Hashtable的接口”。因?yàn)?#xff0c;它同時(shí)實(shí)現(xiàn)了 “Enumerator接口”和“Iterator接口”。 644 private class Enumerator<T> implements Enumeration<T>, Iterator<T> { 645 // 指向Hashtable的table 646 Entry[] table = Hashtable.this.table; 647 // Hashtable的總的大小 648 int index = table.length; 649 Entry<K,V> entry = null; 650 Entry<K,V> lastReturned = null; 651 int type; 652 653 // Enumerator是 “迭代器(Iterator)” 還是 “枚舉類(Enumeration)”的標(biāo)志 654 // iterator為true，表示它是迭代器；否則，是枚舉類。 655 boolean iterator; 656 657 // 在將Enumerator當(dāng)作迭代器使用時(shí)會(huì)用到，用來實(shí)現(xiàn)fail-fast機(jī)制。 658 protected int expectedModCount = modCount; 659 660 Enumerator(int type, boolean iterator) { 661 this.type = type; 662 this.iterator = iterator; 663 } 664 665 // 從遍歷table的數(shù)組的末尾向前查找，直到找到不為null的Entry。 666 public boolean hasMoreElements() { 667 Entry<K,V> e = entry; 668 int i = index; 669 Entry[] t = table; 670 /* Use locals for faster loop iteration */ 671 while (e == null && i > 0) { 672 e = t[--i]; 673 } 674 entry = e; 675 index = i; 676 return e != null; 677 } 678 679 // 獲取下一個(gè)元素 680 // 注意：從hasMoreElements() 和nextElement() 可以看出“Hashtable的elements()遍歷方式” 681 // 首先，從后向前的遍歷table數(shù)組。table數(shù)組的每個(gè)節(jié)點(diǎn)都是一個(gè)單向鏈表(Entry)。 682 // 然后，依次向后遍歷單向鏈表Entry。 683 public T nextElement() { 684 Entry<K,V> et = entry; 685 int i = index; 686 Entry[] t = table; 687 /* Use locals for faster loop iteration */ 688 while (et == null && i > 0) { 689 et = t[--i]; 690 } 691 entry = et; 692 index = i; 693 if (et != null) { 694 Entry<K,V> e = lastReturned = entry; 695 entry = e.next; 696 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e); 697 } 698 throw new NoSuchElementException("Hashtable Enumerator"); 699 } 700 701 // 迭代器Iterator的判斷是否存在下一個(gè)元素 702 // 實(shí)際上，它是調(diào)用的hasMoreElements() 703 public boolean hasNext() { 704 return hasMoreElements(); 705 } 706 707 // 迭代器獲取下一個(gè)元素 708 // 實(shí)際上，它是調(diào)用的nextElement() 709 public T next() { 710 if (modCount != expectedModCount) 711 throw new ConcurrentModificationException(); 712 return nextElement(); 713 } 714 715 // 迭代器的remove()接口。 716 // 首先，它在table數(shù)組中找出要?jiǎng)h除元素所在的Entry， 717 // 然后，刪除單向鏈表Entry中的元素。 718 public void remove() { 719 if (!iterator) 720 throw new UnsupportedOperationException(); 721 if (lastReturned == null) 722 throw new IllegalStateException("Hashtable Enumerator"); 723 if (modCount != expectedModCount) 724 throw new ConcurrentModificationException(); 725 726 synchronized(Hashtable.this) { 727 Entry[] tab = Hashtable.this.table; 728 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; 729 730 for (Entry<K,V> e = tab[index], prev = null; e != null; 731 prev = e, e = e.next) { 732 if (e == lastReturned) { 733 modCount++; 734 expectedModCount++; 735 if (prev == null) 736 tab[index] = e.next; 737 else 738 prev.next = e.next; 739 count--; 740 lastReturned = null; 741 return; 742 } 743 } 744 throw new ConcurrentModificationException(); 745 } 746 } 747 } 748 749 750 private static Enumeration emptyEnumerator = new EmptyEnumerator(); 751 private static Iterator emptyIterator = new EmptyIterator(); 752 753 // 空枚舉類 754 // 當(dāng)Hashtable的實(shí)際大小為0；此時(shí)，又要通過Enumeration遍歷Hashtable時(shí)，返回的是“空枚舉類”的對(duì)象。 755 private static class EmptyEnumerator implements Enumeration<Object> { 756 757 EmptyEnumerator() { 758 } 759 760 // 空枚舉類的hasMoreElements() 始終返回false 761 public boolean hasMoreElements() { 762 return false; 763 } 764 765 // 空枚舉類的nextElement() 拋出異常 766 public Object nextElement() { 767 throw new NoSuchElementException("Hashtable Enumerator"); 768 } 769 } 770 771 772 // 空迭代器 773 // 當(dāng)Hashtable的實(shí)際大小為0；此時(shí)，又要通過迭代器遍歷Hashtable時(shí)，返回的是“空迭代器”的對(duì)象。 774 private static class EmptyIterator implements Iterator<Object> { 775 776 EmptyIterator() { 777 } 778 779 public boolean hasNext() { 780 return false; 781 } 782 783 public Object next() { 784 throw new NoSuchElementException("Hashtable Iterator"); 785 } 786 787 public void remove() { 788 throw new IllegalStateException("Hashtable Iterator"); 789 } 790 791 } 792 }

?

???? 三：TreeMap

???? 與前面的兩個(gè)map實(shí)現(xiàn)類不同，TreeMap是通過紅黑樹來實(shí)現(xiàn)的。所以針對(duì)TreeMap的插入元素、查找元素、刪除元素等都是對(duì)紅黑樹的操作。

??? 1：插入元素

??? 紅黑樹插入結(jié)點(diǎn)分兩步：一是插入到排序二叉樹的合適位置，二是對(duì)二叉樹進(jìn)行平衡（左右旋、重新著色）

public V put(K key, V value) { //用t表示二叉樹的當(dāng)前節(jié)點(diǎn) Entry<K,V> t = root; //t為null表示一個(gè)空樹，即TreeMap中沒有任何元素，直接插入 if (t == null) { //比較key值，個(gè)人覺得這句代碼沒有任何意義，空樹還需要比較、排序？ compare(key, key); // type (and possibly null) check //將新的key-value鍵值對(duì)創(chuàng)建為一個(gè)Entry節(jié)點(diǎn)，并將該節(jié)點(diǎn)賦予給root root = new Entry<>(key, value, null); //容器的size = 1，表示TreeMap集合中存在一個(gè)元素 size = 1; //修改次數(shù) + 1 modCount++; return null; } int cmp; //cmp表示key排序的返回結(jié)果 Entry<K,V> parent; //父節(jié)點(diǎn) // split comparator and comparable paths Comparator<? super K> cpr = comparator; //指定的排序算法 //如果cpr不為空，則采用既定的排序算法進(jìn)行創(chuàng)建TreeMap集合 if (cpr != null) { do { parent = t; //parent指向上次循環(huán)后的t //比較新增節(jié)點(diǎn)的key和當(dāng)前節(jié)點(diǎn)key的大小 cmp = cpr.compare(key, t.key); //cmp返回值小于0，表示新增節(jié)點(diǎn)的key小于當(dāng)前節(jié)點(diǎn)的key，則以當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn) if (cmp < 0) t = t.left; //cmp返回值大于0，表示新增節(jié)點(diǎn)的key大于當(dāng)前節(jié)點(diǎn)的key，則以當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn) else if (cmp > 0) t = t.right; //cmp返回值等于0，表示兩個(gè)key值相等，則新值覆蓋舊值，并返回新值 else return t.setValue(value); } while (t != null); } //如果cpr為空，則采用默認(rèn)的排序算法進(jìn)行創(chuàng)建TreeMap集合 else { if (key == null) //key值為空拋出異常 throw new NullPointerException(); /* 下面處理過程和上面一樣 */ Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } //將新增節(jié)點(diǎn)當(dāng)做parent的子節(jié)點(diǎn) Entry<K,V> e = new Entry<>(key, value, parent); //如果新增節(jié)點(diǎn)的key小于parent的key，則當(dāng)做左子節(jié)點(diǎn) if (cmp < 0) parent.left = e; //如果新增節(jié)點(diǎn)的key大于parent的key，則當(dāng)做右子節(jié)點(diǎn) else parent.right = e; /* * 上面已經(jīng)完成了排序二叉樹的的構(gòu)建，將新增節(jié)點(diǎn)插入該樹中的合適位置 * 下面fixAfterInsertion()方法就是對(duì)這棵樹進(jìn)行調(diào)整、平衡，具體過程參考上面的五種情況 */ fixAfterInsertion(e); //TreeMap元素?cái)?shù)量 + 1 size++; //TreeMap容器修改次數(shù) + 1 modCount++; return null; } /** * 新增節(jié)點(diǎn)后的修復(fù)操作 * x 表示新增節(jié)點(diǎn) */ private void fixAfterInsertion(Entry<K,V> x) { x.color = RED; //新增節(jié)點(diǎn)的顏色為紅色 //循環(huán) 直到 x不是根節(jié)點(diǎn)，且x的父節(jié)點(diǎn)不為紅色 while (x != null && x != root && x.parent.color == RED) { //如果X的父節(jié)點(diǎn)（P）是其父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）的左節(jié)點(diǎn) if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //獲取X的叔節(jié)點(diǎn)(U) Entry<K,V> y = rightOf(parentOf(parentOf(x))); //如果X的叔節(jié)點(diǎn)（U） 為紅色（情況三） if (colorOf(y) == RED) { //將X的父節(jié)點(diǎn)（P）設(shè)置為黑色 setColor(parentOf(x), BLACK); //將X的叔節(jié)點(diǎn)（U）設(shè)置為黑色 setColor(y, BLACK); //將X的父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）設(shè)置紅色 setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } //如果X的叔節(jié)點(diǎn)（U為黑色）；這里會(huì)存在兩種情況（情況四、情況五） else { //如果X節(jié)點(diǎn)為其父節(jié)點(diǎn)（P）的右子樹，則進(jìn)行左旋轉(zhuǎn)（情況四） if (x == rightOf(parentOf(x))) { //將X的父節(jié)點(diǎn)作為X x = parentOf(x); //右旋轉(zhuǎn) rotateLeft(x); } //（情況五） //將X的父節(jié)點(diǎn)（P）設(shè)置為黑色 setColor(parentOf(x), BLACK); //將X的父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）設(shè)置紅色 setColor(parentOf(parentOf(x)), RED); //以X的父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）為中心右旋轉(zhuǎn) rotateRight(parentOf(parentOf(x))); } } //如果X的父節(jié)點(diǎn)（P）是其父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）的右節(jié)點(diǎn) else { //獲取X的叔節(jié)點(diǎn)（U） Entry<K,V> y = leftOf(parentOf(parentOf(x))); //如果X的叔節(jié)點(diǎn)（U） 為紅色（情況三） if (colorOf(y) == RED) { //將X的父節(jié)點(diǎn)（P）設(shè)置為黑色 setColor(parentOf(x), BLACK); //將X的叔節(jié)點(diǎn)（U）設(shè)置為黑色 setColor(y, BLACK); //將X的父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）設(shè)置紅色 setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } //如果X的叔節(jié)點(diǎn)（U為黑色）；這里會(huì)存在兩種情況（情況四、情況五） else { //如果X節(jié)點(diǎn)為其父節(jié)點(diǎn)（P）的右子樹，則進(jìn)行左旋轉(zhuǎn)（情況四） if (x == leftOf(parentOf(x))) { //將X的父節(jié)點(diǎn)作為X x = parentOf(x); //右旋轉(zhuǎn) rotateRight(x); } //（情況五） //將X的父節(jié)點(diǎn)（P）設(shè)置為黑色 setColor(parentOf(x), BLACK); //將X的父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）設(shè)置紅色 setColor(parentOf(parentOf(x)), RED); //以X的父節(jié)點(diǎn)的父節(jié)點(diǎn)（G）為中心右旋轉(zhuǎn) rotateLeft(parentOf(parentOf(x))); } } } //將根節(jié)點(diǎn)G強(qiáng)制設(shè)置為黑色 root.color = BLACK; } private void rotateLeft(Entry<K,V> p) { if (p != null) { //獲取P的右子節(jié)點(diǎn)，其實(shí)這里就相當(dāng)于新增節(jié)點(diǎn)N（情況四而言） Entry<K,V> r = p.right; //將R的左子樹設(shè)置為P的右子樹 p.right = r.left; //若R的左子樹不為空，則將P設(shè)置為R左子樹的父親 if (r.left != null) r.left.parent = p; //將P的父親設(shè)置R的父親 r.parent = p.parent; //如果P的父親為空，則將R設(shè)置為跟節(jié)點(diǎn) if (p.parent == null) root = r; //如果P為其父節(jié)點(diǎn)（G）的左子樹，則將R設(shè)置為P父節(jié)點(diǎn)(G)左子樹 else if (p.parent.left == p) p.parent.left = r; //否則R設(shè)置為P的父節(jié)點(diǎn)（G）的右子樹 else p.parent.right = r; //將P設(shè)置為R的左子樹 r.left = p; //將R設(shè)置為P的父節(jié)點(diǎn) p.parent = r; } } private void rotateRight(Entry<K,V> p) { if (p != null) { //將L設(shè)置為P的左子樹 Entry<K,V> l = p.left; //將L的右子樹設(shè)置為P的左子樹 p.left = l.right; //若L的右子樹不為空，則將P設(shè)置L的右子樹的父節(jié)點(diǎn) if (l.right != null) l.right.parent = p; //將P的父節(jié)點(diǎn)設(shè)置為L的父節(jié)點(diǎn) l.parent = p.parent; //如果P的父節(jié)點(diǎn)為空，則將L設(shè)置根節(jié)點(diǎn) if (p.parent == null) root = l; //若P為其父節(jié)點(diǎn)的右子樹，則將L設(shè)置為P的父節(jié)點(diǎn)的右子樹 else if (p.parent.right == p) p.parent.right = l; //否則將L設(shè)置為P的父節(jié)點(diǎn)的左子樹 else p.parent.left = l; //將P設(shè)置為L的右子樹 l.right = p; //將L設(shè)置為P的父節(jié)點(diǎn) p.parent = l; } }

?????? 2：刪除元素

?????? TreeMap刪除元素，就是在紅黑樹中刪除一個(gè)結(jié)點(diǎn)。紅黑樹刪除結(jié)點(diǎn)D：取D右分支最左邊，或者 左分支最右邊的子結(jié)點(diǎn)取代D，然后把子節(jié)點(diǎn)刪除，之后再對(duì)紅黑樹進(jìn)行平衡。

???

private void deleteEntry(Entry<K,V> p) { modCount++; //修改次數(shù) +1 size--; //元素個(gè)數(shù) -1 /* * 被刪除節(jié)點(diǎn)的左子樹和右子樹都不為空，那么就用 p節(jié)點(diǎn)的中序后繼節(jié)點(diǎn)代替 p 節(jié)點(diǎn) * successor(P)方法為尋找P的替代節(jié)點(diǎn)。規(guī)則是右分支最左邊，或者 左分支最右邊的節(jié)點(diǎn) * ---------------------（1） */ if (p.left != null && p.right != null) { Entry<K,V> s = successor(p); p.key = s.key; p.value = s.value; p = s; } //replacement為替代節(jié)點(diǎn)，如果P的左子樹存在那么就用左子樹替代，否則用右子樹替代 Entry<K,V> replacement = (p.left != null ? p.left : p.right); /* * 刪除節(jié)點(diǎn)，分為上面提到的三種情況 * -----------------------（2） */ //如果替代節(jié)點(diǎn)不為空 if (replacement != null) { replacement.parent = p.parent; /* *replacement來替代P節(jié)點(diǎn) */ //若P沒有父節(jié)點(diǎn)，則跟節(jié)點(diǎn)直接變成replacement if (p.parent == null) root = replacement; //如果P為左節(jié)點(diǎn)，則用replacement來替代為左節(jié)點(diǎn) else if (p == p.parent.left) p.parent.left = replacement; //如果P為右節(jié)點(diǎn)，則用replacement來替代為右節(jié)點(diǎn) else p.parent.right = replacement; //同時(shí)將P節(jié)點(diǎn)從這棵樹中剔除掉 p.left = p.right = p.parent = null; /* * 若P為紅色直接刪除，紅黑樹保持平衡 * 但是若P為黑色，則需要調(diào)整紅黑樹使其保持平衡 */ if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { //p沒有父節(jié)點(diǎn)，表示為P根節(jié)點(diǎn)，直接刪除即可 root = null; } else { //P節(jié)點(diǎn)不存在子節(jié)點(diǎn)，直接刪除即可 if (p.color == BLACK) //如果P節(jié)點(diǎn)的顏色為黑色，對(duì)紅黑樹進(jìn)行調(diào)整 fixAfterDeletion(p); //刪除P節(jié)點(diǎn) if (p.parent != null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; } } } static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { if (t == null) return null; /* * 尋找右子樹的最左子樹 */ else if (t.right != null) { Entry<K,V> p = t.right; while (p.left != null) p = p.left; return p; } /* * 選擇左子樹的最右子樹 */ else { Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } } private void fixAfterDeletion(Entry<K,V> x) { // 刪除節(jié)點(diǎn)需要一直迭代，知道 直到 x 不是根節(jié)點(diǎn)，且 x 的顏色是黑色 while (x != root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { //若X節(jié)點(diǎn)為左節(jié)點(diǎn) //獲取其兄弟節(jié)點(diǎn) Entry<K,V> sib = rightOf(parentOf(x)); /* * 如果兄弟節(jié)點(diǎn)為紅色----（情況3.1） * 策略：改變W、P的顏色，然后進(jìn)行一次左旋轉(zhuǎn) */ if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateLeft(parentOf(x)); sib = rightOf(parentOf(x)); } /* * 若兄弟節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都為黑色----（情況3.2） * 策略：將兄弟節(jié)點(diǎn)編程紅色 */ if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { /* * 如果兄弟節(jié)點(diǎn)只有右子樹為黑色----（情況3.3） * 策略：將兄弟節(jié)點(diǎn)與其左子樹進(jìn)行顏色互換然后進(jìn)行右轉(zhuǎn) * 這時(shí)情況會(huì)轉(zhuǎn)變?yōu)?.4 */ if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } /* *----情況3.4 *策略：交換兄弟節(jié)點(diǎn)和父節(jié)點(diǎn)的顏色， *同時(shí)將兄弟節(jié)點(diǎn)右子樹設(shè)置為黑色，最后左旋轉(zhuǎn) */ setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; } } /** * X節(jié)點(diǎn)為右節(jié)點(diǎn)與其為做節(jié)點(diǎn)處理過程差不多，這里就不在累述了 */ else { Entry<K,V> sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK); }

?

? ?四：LinkedHashMap

? ?HashMap對(duì)鍵值對(duì)的組織是無順序的。遍歷順序不一定是按照插入順序，所以如果想按照插入順序來遍歷結(jié)果的話用HashMap是不行的。為此，我們可以使用LinkedHashMap。

? ?與LinkedHashSet類似，LinkedHashMap也是維護(hù)了一個(gè)雙向鏈表，記錄元素的插入順序，然后再根據(jù)元素值，采用hashcode()、equals()方法來存儲(chǔ)元素值并實(shí)現(xiàn)元素的唯一性。雙向鏈表將所有put到LinkedHashmap的節(jié)點(diǎn)一一串成了一個(gè)雙向循環(huán)鏈表，因此它保留了節(jié)點(diǎn)插入的順序，可以使節(jié)點(diǎn)的輸出順序與輸入順序相同。

??? 參考資料：http://blog.csdn.net/chenssy/article/details/26668941

?

?

?

???

總結(jié)

以上是生活随笔為你收集整理的Java中的Map的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。