HashMap相关

hashCode.png

hash概念

hash：是一种信息摘要算法，它还叫做哈希，或者散列。我们平时使用的MD5中的公私钥验证都属于Hash算法，通过输入key进行Hash计算，就可以获取key的HashCode()，比如我们通过校验MD5来验证文件的完整性。

碰撞：好的Hash算法可以计算出几乎独一无二的hashCode，如果hashCode出现了重复的，就称作碰撞。

hashCode

• hashCode是object对象方法，一般对象都会重写该方法；
• hashMap允许key为null，但是只能存在一个null的key；
• hashMap什么时候会用到equals方法？

HashMap存储过程

HashMap是将数组和链表结合的一种结构，比较形象如下图：

HashMap.png

首先进行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

1. Hashtable线程安全，HashMap线程安全；
2. 建议使用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和双向链表进行结合来实现的

参考文章

1. https://blog.csdn.net/justloveyou_/article/details/62893086
2. http://www.importnew.com/21294.html