深入理解Java中的Map集合技术頭條網

HashMap

int capacity = 1;

while(capacity < initialCapacity)

capacity <<= 1;

capacity才是創建的Entry對象數組的大小，new HashMap(5,0.6)，則設loadFactor為0.6，並創建一個大小為8的Entry對象數組，threshold則為4( 8 * 0.6 = 4 )
put(key, value)
key為null,獲取第一個Entry對象，並基於Entry的next遍歷
找到key為null，更新value，返回
未找到，增加Entry。
增加時獲取數組首個Entry：e，並創建Entry對象，key為null，value為傳入對象，next為e。
若數組len >= threshold，擴容為2倍，擴容前對所有元素重新hash，並填充數組，最後重設置threshold。
key不為null，獲取key的hashCode，然後再對此hashCode作hash操作，hash完成後，將hash值與對象數組len按位與，得到key要存儲的數組位置。
hash衝突：不同key找到相同存儲位置，通過調用Entry對象next遍歷鏈表的方式。
get(Object key)
與put一樣，根據key是否為null分別處理
key為null –> 首個Entry –> next遍歷
key非null –> hash和按位與 –> 找到位置 –> 找到Entry –> next遍歷
remove(Object key)
類似get，找到key,當前元素更新為next元素
未找到，遍歷鏈表
containsKey(key)
調用getEntry，與get基本相同，返回是否為null
keySet()
用來遍歷Map對象，返回KeySet對象實例
調用iterator返回keyIterator，遍歷中有增刪會拋異常

HashMap要點

TreeMap

實現
支持排序的Map實現，不同於HashMap
TreeMap()
將comparator屬性為null，若希望控制存儲順序，使用帶Comparator參數的構造器
put(key, value)
判斷root是否為null
是，建新Entry，並賦給root
否，判斷有無實現Comparator
有，紅黑樹遍歷key，相等替換，不等找到null為止
未找到相同的key，創建新的Entry，將其parent設置成上面所尋找到的元素並根據和parent key比較的情況來設置parent的left或right屬性
無，判斷key是否為null
是，1.拋NullPointerException，2.並將key造型為Comparable，進行與上面相同過程
否，執行2

基於紅黑樹實現，一定要有key比較，要麼傳入Comparator實現，要麼key對象實現Comparable接口