hash概念
hash：是一种信息摘要算法，它还叫做哈希，或者散列。我们平时使用的MD5中的公私钥验证都属于Hash算法，通过输入key进行Hash计算，就可以获取key的HashCode()，比如我们通过校验MD5来验证文件的完整性。
碰撞：好的Hash算法可以计算出几乎独一无二的hashCode，如果hashCode出现了重复的，就称作碰撞。
hashCode
- hashCode是object对象方法，一般对象都会重写该方法；
- hashMap允许key为null，但是只能存在一个null的key；
- hashMap什么时候会用到equals方法？
HashMap存储过程
HashMap是将数组和链表结合的一种结构，比较形象如下图：
首先进行put操作时，会先计算出该key的hash值，然后调用HashMap的hash方法，该方法在JDK 8中如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
主要思想是将key的高16位和低16进行与或操作，然后再通过下面与操作，计算出数key在数组中的索引位置，算法的目的主要是为了让数据尽可能的分布均匀：
h & (length-1)
后面再根据数组对应索引中是否有数据然后进行数据的添加，这其中判断key是否重复的依据是有key的equals方法来进行的，如果equals方法相同，则认为key重复，只会对value进行更新。
HashMap扩容
随着不断往HashMap存放数据，需要进行扩容操作，代码中主要通过如下：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认数组大小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），就会把这个链动态变成红黑二叉树，使查询最差复杂度由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实现原理就是通过LinkedHashMap来实现的
- LinkedHashMap原理是将HashMap和双向链表进行结合来实现的
