Java学习笔记-HashMap（1）

HashMap与Node JDK中为我们提供了HashMap这一数据结构，声明如下， public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable 它本质上是一个哈希表，且可以在常数时间内完成get和put操作。HashMap采用的是数组+链表的实现数组中的每个桶都存储了一个<Key, Value>键值对结点。这种结点Java 8以上被称作Node。每个Node结点都会保存自己的hash、key和value，源码如下：

/**
     * Basic hash bin node, used for most entries.
*/
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        ...
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        ...
    }

    public final boolean equals(Object o) {
        ...
    }
}

初始情况下，数组中的所有位置都为空。用put方法插入时，会用Key的hashCode方法计算其哈希值，作为哈希表中的index。如果index对应的「桶」（即数组位置）已经被占用了，且新插入的键值对的键与那个位置上的已有键都不同，就说明发生了冲突。遇到这种情况，就在已有节点上往下挂一个新节点，存储新的键值对。这样，就形成了链表结构。可以看到，Node类中还有一成员next，它就是指向同一桶内下一个键值对的引用。get方法查找时，找到Key对应的桶后，就从头遍历链表，找到相应的键值对结点，获得其Value并返回。键值对的加入扩容resize 扩容是动态数据结构常用的控制大小的方式。最著名的例子莫过于C++中的vector。一般来说，数据结构类会设定两个常数值和，功能分别是：是装载因子，当存储的数据项的数量超过当前容量的比例时，就将新建一个数组，但容量扩大一倍。然后，把原数组的内容重新哈希到经过扩容的新数组中去。注意，这里不能直接拷贝过去，因为index的计算是跟HashMap的大小相关的： index = hash(Key) & (Length - 1) 这个公式的设计是非常巧妙的。我们发现，键值对的新位置要么是在原位置，要么是在原位置的基础上再移动2次幂个的位置。这样，在扩充HashMap的时候，就不用真的把每个键值对的index都重新算一遍了，大幅提升了时间效率。一般设为的一半，称为数据量的下界。它表示数据项的数量低于当前容量的比例时，就把容量缩小为原先的一半。对于HashMap来说，初始的值是0.75。头插还是尾插一个需要注意的细节是，Java 8之前，插入新结点时，都是优先在头部插入，因为作者认为新插入的键值对更有可能被先访问到，因此头部插入的时间效率可能更高。但是，Java 8及之后，HashMap的实现就改成了从尾部插入。为何要做这样的改变呢？原因其实相当微妙。下面是Java 7的HashMap在扩容时调用的transfer方法，用于将原数组中的内容转移到扩容后的新数组中去。 `

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            // 头插法
            // 把自己的next置为新桶的头元素
            e.next = newTable[i];
            // 把新桶的头元素置为自己
            newTable[i] = e;
            // 继续遍历原桶中的下一个元素
            e = next;
        }
    }
}