一、什麼是HashMap
- Hash散列：将一個任意的長度通過某種（Hash算法）算法轉換成一個固定的值。
- Map：地圖 x，y存儲
- 總結：通過HASH出來的值，然後通過這個值 值定位到這個map，然後value存儲到這個map中
- 疑問
- 1.key可以為空嗎？
- Null當成一個key來存儲
- 2.如果hash key 重複了 value會覆寫嗎？
- 不會覆寫，而是将原來的值賦給oldValue，然後将新的值賦給value。原來的對象存放在entry對象的next裡面， 例如：
- 1.key可以為空嗎？
Map map = new HashMap();
map.put("name", "zhangsan");
//調用put方法時，若key沒有重複，傳回值為null；若重複，則為傳回之前存儲的值。
map.put("name","wanger"); //此處會傳回"zhangsan"
-
3.HashMap什麼時候擴容？
- 執行put()方法的時候，門檻值達到容量的3/4會進行擴容！
- 擴容為偶數依次為： 16 2x16=32 2x32=62 2x64 ……
- HashMap的table: 數組+連結清單 資料結構
二、源碼分析
1.初始化參數介紹
- int initCapacity (初始化數組大小，預設值為16)
- int maximum_capacity(數組最大容量)
static final int MAXIMUM_CAPACITY = << ;
- float loadFactor （負載因子，預設值為0.75f）
static final float DEFAULT_LOAD_FACTOR = f;
- table：初始化一個名為table的entry數組
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
2.put方法分析
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
//首先根據key值計算出HashCode值
int hash = hash(key.hashCode());
/*然後通過一個indexFor方法計算出此元素該存放于table數組的哪個位置，
再檢測此table的此坐标位置的entry鍊是否存在此key或此key值，若存在
則更新此元素的value值*/
int i = indexFor(hash, table.length);
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;
}
}
modCount++;
//添加目前的表項到i的位置
addEntry(hash, key, value, i);
return null;
}
3.get方法分析
public V get(Object key) {
//鍵為null的entry在table[0]
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == ) {
return null;
}
//先根據key擷取hash值，與put方法一緻。
int hash = (key == null) ? : hash(key);
// 同樣通過位與運算擷取Entry[] tables下标
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// 當比對到hash值相同，key相同的Entry元素時，傳回Entry對象的vlaue
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
4.擴容源碼分析
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//生成一個新的table數組（entry對象數組）
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
//根據新的Capacity和負載因子去生成新的臨界值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + );
}
/*
因為table數組的容量增加了，那麼相應的table的length也增加了，那麼之前存儲的元素的位置
也就不一樣了，比如之前的length是16，現在的length是32，那麼hashCode模16和HashCode
模32的結果很有可能會不一樣，是以就隻有重新去計算新的位置，方法是周遊數組，再周遊數組上
的entry鍊*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
5、總結
當負載因子較大時，去給table數組擴容的可能性就會少，是以相對占用記憶體較少（空間上較少），但是每條entry鍊上的元素會相對較多，查詢的時間也會增長（時間上較多）。反之就是，負載因子較少的時候，給table數組擴容的可能性就高，那麼記憶體空間占用就多，但是entry鍊上的元素就會相對較少，查出的時間也會減少。是以才有了負載因子是時間和空間上的一種折中的說法。是以設定負載因子的時候要考慮自己追求的是時間還是空間上的少。
注意：設定initCapacity的時候，盡量設定為2的幂，這樣會去掉計算比initCapactity大，且為2的幂的數的運算。
三、手寫實作
1.定義Map接口
public interface Map<K,V> {
public V put(K k,V v);
public V get(K k);
public int size();
//HashMap内部的Entry對象
public interface Entry<K,V>{
public K getKey();
public V getValue();
}
}
2.實作類HashMap
public class HashMap<K,V> implements Map<K, V> {
private static int defaultLength = ;
private static float defaultLoader = f;
private Entry<K,V>[] table = null;
private int size = ;
public HashMap(int length, float loader) {
defaultLength = length;
defaultLoader = loader;
table = new Entry[defaultLength];
}
public HashMap() {
this(defaultLength,defaultLoader);
}
public V put(K k, V v) {
size++;
int index = hash(k);
Entry<K,V> entry = table[index];
if(entry == null){
table[index] = newEntry(k,v,null);
}else{
table[index] = newEntry(k, v, entry);
}
return table[index].getValue();
}
public V get(K key) {
int index = hash(key);
if(table[index] == null){
return null;
}
return find(key,table[index]);
}
public int size() {
return size;
}
class Entry<K,V> implements Map.Entry<K, V>{
K k;
V v;
Entry<K,V> next;
public Entry(K k, V v, Entry<K,V> next) {
this.k = k;
this.v = v;
this.next = next;
}
public K getKey() {
return k;
}
public V getValue() {
return v;
}
}
//key->hash
public int hash(K k){
int m = defaultLength;
int i = k.hashCode() % m;
return i >= ? i : -i;
}
private Entry<K, V> newEntry(K k, V v, Entry<K,V> next) {
return new Entry<K,V>(k,v,next);
}
//根據key和table查找元素
private V find(K key, Entry<K,V> entry) {
if(key == entry.getKey() || key.equals(entry.getKey())){
if(entry.next != null){
System.out.println("oldValue:"+entry.next.getValue());
}
return entry.getValue();
}
else{
if(entry.next != null){
return find(key,entry.next);
}
}
return null;
}
}
四、不足之處（伸縮性角度）
1.伸縮性
每當hashmap擴容的時候需要重新去add entey對象 需要重新Hash，然後放入我們新的entry table數組裡面
當我們知道HashMap需要存多少值（或值特别大的時候），最好指定他們的擴容大小，防止在put的時候進行多次再擴容
2.時間複雜度
時間複雜度與key是否沖突有關（理想狀态為O(1)）, hash算法決定了效率
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)