Java源码分析之HashMap

之前整理了单例模式的源码分析
接下来，整理一下HashMap的源码分析

首先理解概念：

1. 数组
数组存储区间是连续的，占用内存严重，故空间复杂的很大。
但数组的二分查找时间复杂度小，为O(1)；
数组的特点是：寻址容易，插入和删除困难；

2. 链表
链表存储区间离散，占用内存比较宽松，
故空间复杂度很小，但时间复杂度很大，达O（N）。
链表的特点是：寻址困难，插入和删除容易。

3. 哈希表
哈希表（(Hash table）既满足了数据的查找方便，
同时不占用太多的内容空间，使用也十分方便。
哈希表有多种不同的实现方法，最常用的一种方法—— 拉链法，我们可以理解为“链表的数组” 
哈希表是由 **数组+链表** 组成的

HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的

HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。

首先HashMap里面实现一个静态内部类Entry(1.8里面是是Node)，其重要的属性有 key , value, next
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        ......
    }
    // jdk1.8实现
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;   //链表的下一个node
    
        Node(int hash, K key, V value, Node<K,V> next) { ... }
        public final K getKey(){ ... }
        public final V getValue() { ... }
        public final String toString() { ... }
        public final int hashCode() { ... }
        public final V setValue(V newValue) { ... }
        public final boolean equals(Object o) { ... }
    }
    
    
说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。
    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table;

HashMap：
它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度。
HashMap最多只允许一条记录的键为null，允许多条记录的值为null。非线程安全。
如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap

Hashtable：
Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类。线程安全。并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。

LinkedHashMap：
LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

TreeMap：
TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。
在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

初始大小、增长

1. hashMap的大小始终是2的n次幂
2. 每扩充一次，HashMap 的容量就增大一倍。
3. hashMap的构造方法;
    * HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。 
    * HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。 
    * HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。


// 以指定初始化容量、负载因子创建 HashMap   
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    this.loadFactor = loadFactor;
    threshold = initialCapacity;
    init();
}
注意：此处用的java1.7源码，这里并没有在构造函数里面就把容量扩展到
比initialCapacity小的，最小的2的n次方值。
而是在put第一个元素的时候才执行这个操作,保证上述条件1
    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold); //扩容到最2的n方
        }
        ...
    }
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }
 
 
增长：
// 将 key、value 添加到 i 索引处  
addEntry(hash, key, value, i); 

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 如果大小超过临界值，容量翻倍
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

Put方法

当向 HashMap 中添加 key-value 对，由其 key 的 hashCode() 返回值决定该 key-value 对（就是 Entry 对象）的存储位置。
当两个 Entry 对象的 key 的 hashCode() 返回值相同时，
将由 key 通过 eqauls() 比较值决定是采用覆盖行为（返回 true），还是产生 Entry 链（返回 false）。 


public V put(K key, V value)   
{
    if (table == EMPTY_TABLE) { //第一次添加，把大小扩展到2的幂放
        inflateTable(threshold);
    }
    // 如果 key 为 null，调用 putForNullKey 方法进行处理  
    if (key == null)   
     return putForNullKey(value);    //null总是放在数组的第一个链表中
    // 根据 key 的 keyCode 计算 Hash 值  
    int hash = hash(key.hashCode());   
    // 搜索指定 hash 值在对应 table 中的索引  
     int i = indexFor(hash, table.length);  
    // //遍历链表 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素  
    for (Entry<K,V> e = table[i]; e != null; e = e.next)   
    {   
     Object k;   
     // 找到指定 key 与需要放入的 key 相等（hash 值相同  
     // 通过 equals 比较放回 true）  
     if (e.hash == hash && ((k = e.key) == key   
         || key.equals(k)))   
     {   
         V oldValue = e.value;   
         e.value = value;   
         e.recordAccess(this);   
         return oldValue;   
     }   
    }   
    // 如果 i 索引处的 Entry 为 null，表明此处还没有 Entry   
    modCount++;   
    // 将 key、value 添加到 i 索引处  
    addEntry(hash, key, value, i);   
    return null;   
}   


void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //参数e, 是Entry.next
    //如果size超过threshold(临界值)，则扩充table大小。再散列
    if (size++ >= threshold)
            resize(2 * table.length);
}

当哈希表的容量超过默认容量时，必须调整table的大小。
当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，
这时，需要创建一张新表，将原表的映射到新表中。

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                //重新计算index
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

Get方法

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    //先定位到数组元素，再遍历该元素处的链表
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

/*
按位取并，作用上相当于取模mod或者取余%。
这意味着数组下标相同，并不表示hashCode相同。
*/
static int indexFor(int h, int length) {
    return h & (length-1);
}

// null key总是存放在Entry[]数组的第一个元素。
private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

private V getForNullKey() {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

参考资料

Java 8系列之重新认识HashMap
HashMap实现原理分析
HashMap详解
红黑树深入剖析及Java实现