hash概念
hash：是一種信息摘要算法，它還叫做哈希，或者散列。我們平時使用的MD5中的公私鑰驗證都屬于Hash算法，通過輸入key進行Hash計算，就可以獲取key的HashCode()，比如我們通過校驗MD5來驗證文件的完整性。
碰撞：好的Hash算法可以計算出幾乎獨一無二的hashCode，如果hashCode出現(xiàn)了重復(fù)的，就稱作碰撞。
hashCode
- hashCode是object對象方法，一般對象都會重寫該方法；
- hashMap允許key為null，但是只能存在一個null的key；
- hashMap什么時候會用到equals方法？
HashMap存儲過程
HashMap是將數(shù)組和鏈表結(jié)合的一種結(jié)構(gòu)，比較形象如下圖：
首先進行put操作時，會先計算出該key的hash值，然后調(diào)用HashMap的hash方法，該方法在JDK 8中如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
主要思想是將key的高16位和低16進行與或操作，然后再通過下面與操作，計算出數(shù)key在數(shù)組中的索引位置，算法的目的主要是為了讓數(shù)據(jù)盡可能的分布均勻：
h & (length-1)
后面再根據(jù)數(shù)組對應(yīng)索引中是否有數(shù)據(jù)然后進行數(shù)據(jù)的添加，這其中判斷key是否重復(fù)的依據(jù)是有key的equals方法來進行的，如果equals方法相同，則認為key重復(fù)，只會對value進行更新。
HashMap擴容
隨著不斷往HashMap存放數(shù)據(jù)，需要進行擴容操作，代碼中主要通過如下：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默認數(shù)組大小16，當超過16 * 0.75時會進行resize擴容操作，這個過程會重寫進行hash計算，性能消耗比較大，因此選擇一個好的初始容量非常重要。
HashMap遍歷
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
HashTable和HashMap
- Hashtable線程安全，HashMap線程安全；
- 建議使用ConcurrentHashMap；
JDK8中HashMap的新特性
如果某個桶中的鏈表記錄過大的話（當前是TREEIFY_THRESHOLD = 8），就會把這個鏈動態(tài)變成紅黑二叉樹，使查詢最差復(fù)雜度由O(N)變成了O(logN)。
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
Set List Map
Collection
----set
--------ArrayList / LinkedList / Vector
----List
--------HashSet / TreeSet
Map
----HashMap
--------LinkedHashMap
----HashTable
----TreeMap
其他問題
- 在Android中使用SparseArray代替HashMap
- Android中LruCache實現(xiàn)原理就是通過LinkedHashMap來實現(xiàn)的
- LinkedHashMap原理是將HashMap和雙向鏈表進行結(jié)合來實現(xiàn)的
