ArrayList

?? ArrayList是一個(gè)動(dòng)態(tài)數(shù)組，初始長(zhǎng)度為10，ArrayList 允許空值和重復(fù)元素，通過(guò)add()方法添加元素，當(dāng)往 ArrayList 中添加的元素?cái)?shù)量大于其底層數(shù)組容量時(shí)，其會(huì)通過(guò)擴(kuò)容機(jī)制重新生成一個(gè)更大的數(shù)組。擴(kuò)容的數(shù)組是原來(lái)數(shù)組1.5倍，并把之前的數(shù)組元素copy進(jìn)來(lái)。

HashMap

??ArrayList通常用來(lái)遍歷一個(gè)數(shù)組，HashMap可以通過(guò)key查找某個(gè)元素，在jdk1.8之后使用的是buket數(shù)組+鏈表+紅黑樹(shù)結(jié)構(gòu)，Hashmap通過(guò)put(key,value)來(lái)存儲(chǔ)對(duì)象和get(key)方法獲取已經(jīng)存儲(chǔ)的對(duì)象。

在使用put（key,value）方法時(shí)，

??1、如果hashmap為空，則初始化buket數(shù)組容量大小 ，如果用戶沒(méi)有傳入initialCapacity即數(shù)組容量 和loadFactor即加載因子這兩個(gè)參數(shù)，會(huì)使用默認(rèn)值，initialCapacity默認(rèn)為16，loadFactory默認(rèn)為0.75。
??2、通過(guò)對(duì)Key的hashcode()方法得到key的哈希值，再通過(guò) 哈希值與（數(shù)組長(zhǎng)度-1）做異或運(yùn)算，得到在bucket數(shù)組中的位置。
??3、找到在bucket數(shù)組中的位置之后，如果當(dāng)前位置為空，把key和value包裝成一個(gè)Node對(duì)象后插入所在位置。若當(dāng)前位置不為空，調(diào)用key的equals()方法與當(dāng)前位置的鏈表或紅黑樹(shù)表的key作比較，若返回true，替換舊值。若返回false，有以下兩種情況：
??(1) 若是鏈表結(jié)構(gòu)，把key和value包裝成一個(gè)Node對(duì)象用尾插法進(jìn)行插入，插入之后判斷鏈表個(gè)數(shù)是否到達(dá)變成紅黑樹(shù)的闕值8，若達(dá)到閾值，轉(zhuǎn)化為紅黑樹(shù)結(jié)構(gòu)。
??(2) 若是紅黑樹(shù)結(jié)構(gòu)，則用樹(shù)的插入方法插入。
??4、最后判斷哈希桶閥值，當(dāng)數(shù)組的size即Node節(jié)點(diǎn)數(shù)量達(dá)到闕值時(shí)，即size > load factor * capacity 時(shí)，分配一個(gè)是原來(lái)數(shù)組二倍長(zhǎng)的數(shù)組，將原來(lái)hashmap的中Node重新計(jì)算并插入到數(shù)組中。

在使用get(key)方法時(shí)，

??通過(guò)對(duì)Key的hashcode()方法得到key的哈希值，再通過(guò) 哈希值與（數(shù)組長(zhǎng)度-1）做異或運(yùn)算，得到在bucket數(shù)組中的位置。找到bucket數(shù)組位置之后，會(huì)調(diào)用key.equals()方法去找到鏈表中正確的節(jié)點(diǎn)，最終找到要找的值對(duì)象。