hash概念
hash：是一種信息摘要算法泵琳，它還叫做哈希，或者散列舔涎。我們平時(shí)使用的MD5中的公私鑰驗(yàn)證都屬于Hash算法笼踩，通過輸入key進(jìn)行Hash計(jì)算，就可以獲取key的HashCode()亡嫌，比如我們通過校驗(yàn)MD5來驗(yàn)證文件的完整性嚎于。
碰撞：好的Hash算法可以計(jì)算出幾乎獨(dú)一無二的hashCode，如果hashCode出現(xiàn)了重復(fù)的挟冠，就稱作碰撞于购。
hashCode
- hashCode是object對象方法，一般對象都會(huì)重寫該方法圃郊；
- hashMap允許key為null价涝，但是只能存在一個(gè)null的key；
- hashMap什么時(shí)候會(huì)用到equals方法持舆？
HashMap存儲(chǔ)過程
HashMap是將數(shù)組和鏈表結(jié)合的一種結(jié)構(gòu)色瘩，比較形象如下圖：
首先進(jìn)行put操作時(shí)，會(huì)先計(jì)算出該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進(jìn)行與或操作，然后再通過下面與操作竹伸，計(jì)算出數(shù)key在數(shù)組中的索引位置泥栖，算法的目的主要是為了讓數(shù)據(jù)盡可能的分布均勻：
h & (length-1)
后面再根據(jù)數(shù)組對應(yīng)索引中是否有數(shù)據(jù)然后進(jìn)行數(shù)據(jù)的添加簇宽，這其中判斷key是否重復(fù)的依據(jù)是有key的equals方法來進(jìn)行的，如果equals方法相同吧享，則認(rèn)為key重復(fù)魏割，只會(huì)對value進(jìn)行更新。
HashMap擴(kuò)容
隨著不斷往HashMap存放數(shù)據(jù)钢颂，需要進(jìn)行擴(kuò)容操作钞它，代碼中主要通過如下：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默認(rèn)數(shù)組大小16，當(dāng)超過16 * 0.75時(shí)會(huì)進(jìn)行resize擴(kuò)容操作殊鞭，這個(gè)過程會(huì)重寫進(jìn)行hash計(jì)算遭垛，性能消耗比較大，因此選擇一個(gè)好的初始容量非常重要操灿。
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的新特性
如果某個(gè)桶中的鏈表記錄過大的話（當(dāng)前是TREEIFY_THRESHOLD = 8）庶喜，就會(huì)把這個(gè)鏈動(dòng)態(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實(shí)現(xiàn)原理就是通過LinkedHashMap來實(shí)現(xiàn)的
- LinkedHashMap原理是將HashMap和雙向鏈表進(jìn)行結(jié)合來實(shí)現(xiàn)的
