HashMap 是什么？

在我们的印象里，HashMap是一个存储一对一关系的数据结构，
采用hash算法，所以读取和存储效率较高。

问题

1. hash算法是如何实现的？

源码

注释

从类的注释我们可以得到以下内容

1. HashMap是实现了Map接口的Hash Table
2. HashMap几乎和HashTable一样，除了非线程安全和允许null key/value
3. HashMap不保证数据顺序保持不变
4. 常规操作保证稳定的效率（如get put）
5. 遍历效率取决于Hash Table的大小和数据的大小
6. HashMap的效率取决于初始容量和加载因数（加载因数表示数据量达到Hash Table容量的多少时，需要扩容）
7. 扩容时，会重新排列数据（rehash）
8. 初始加载因数是0.75，初始容量请根据实际需要设置（避免过多的扩容或者浪费空间）
9. HashMap非线程安全，修改map的结构时，遍历会抛出异常

可以看到注释基本写的很全，会把我们关心的东西说清楚

实现

总结来说如下

1. 通过自定义的Node存储Key和Value，记录一个对应关系
2. 通过Node数组存储所有对应关系，数组的下标由key的hashcode和数组大小计算得出
3. 如果数组下标相同，通过单链表将相同下标的Node保存起来
4. 如果单链表的Node个数超过一定阈值，改为红黑树存储
5. 如果Node的总个数超过一定阈值，扩容，重新排列Node

简单来看下get和put的实现

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 可以看到 下标的计算是 数组大小&hash
            // 如果对应下标处为null，就直接存储
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p; // 对应下标第一个Node就是要修改的Node
            else if (p instanceof TreeNode)
                // 如果是以红黑树的形式存储，在树中找到插入或者修改的Node
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 如果是单链表，循环查找
                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))))
                        // 找到要修改的Node
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                // 修改找到的Node
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // modCount表示数据修改了
        ++modCount;
        if (++size > threshold)
            // 个数超出阈值，扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }


    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                // 判断数组中此下标存的第一个是不是要找的Node
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    // 红黑树保存，则从树中查找
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 单链表存储，则变量查找
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

总结

对于开发使用来说，需要有以下几点注意

1. 非线程安全， 应该用封装HashMap的数据结构实现线程安全，或者使用Map m = Collections.synchronizedMap(new HashMap(...));创建线程安全的Map
2. 初始大小根据具体使用情况决定，避免过多性能消耗，也不能设置的太大浪费空间
3. HashMap遍历的顺序是不稳定的，可能根据数据的增多而变化

备注

此文中源码来源于 Android-28 SDK