zy19982004--容器学习一：HashMap源码分析

一.HashMap的存储结构

 

二.HashMap成员变量

//默认初始容量，总为2的次方值
static final int DEFAULT_INITIAL_CAPACITY = 16;

//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//Entry数组，每一个Entry是一个键值对实体
transient Entry[] table;

//实际存的Entry个数
transient int size;

//数组扩容的阀值，当size+1 > threshold时，扩充到以前容量的两倍
//threshold = table.length * loadFactor
int threshold;

//负载比率
final float loadFactor;

//Map结构一旦变化，如put remove clear等操作的时候，modCount随之变化
transient volatile int modCount;

 

三.Entry对象

//很简单的一个键值对实体而已
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;          //key
        V value;              //value
        Entry<K,V> next;  //next Entry
        final int hash;       //计算出key的hash值

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
        .....
}

 

四.构造函数

// 构造函数
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);

    // 将传入的initialCapacity值，转变成2的次方值capacity去实例化hashmap的属性
    // 比喻传入initialCapacity = 100，则算出来capacity = 2 << 7 = 128，
    // 最终threshold = 128 * 0.75 = 96，table = new Entry[128]
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;  //左移，相当于capacity*2

    this.loadFactor = loadFactor;
    threshold = (int) (capacity * loadFactor);
    table = new Entry[capacity];
    // 模板方法模式，子类想在init里面做点什么重写init就好了
    init();
}

 

五.hash算法和index算法

（帮助理解hash算法：http://692088846.iteye.com/admin/blogs/2075638）

/**
 * 让hashMap里面的元素尽量分布均需，方便查找
 * @param h entry中key的hash值
 * @return 打散后的hash值
 */
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

/**
 * 类似求模运算， 将hash值同length-1(必定是01111...1)相与，运算的结果处于1到length-1间，0刚好用来保存key为null和0的元素
 * @param h 打散后的hash值
 * @param length 数组的长度
 * @return 数组下标 1到lenght-1
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

 

六.取数据  

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        //key != null时
        //1.根据key计算出hash和index
        int hash = hash(key.hashCode());
        //2.从index处的链表头Entry e开始遍历链表，
        //如果e满足hash(key.hashCode()) == e.hash && (key == e.key || key.equals(e.key))，就是我们要找的entry
        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)))    //注释3里的逻辑更好理解
                return e.value;
        }
        return null;
    }

    //如果key为空，直接从table[0]链表里面遍历寻找value
    private V getForNullKey() {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

 

七.存数据，扩容

public V put(K key, V value) {
        //1.key为空时候，调用putForNullKey方法
        if (key == null)
            return putForNullKey(value);
        //2.key不为空
        //2-1.计算hash和index
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        //2-2.根据index得到当前链表头e=table[i]不为空
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //2-3.如果e满足hash(key.hashCode())=e.hash && key==e.key || key.equals(e.key)，value覆盖oldValue
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //2-4.table[i]为空，直接插入entry
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

    private V putForNullKey(V value) {
        //1.从0位置的链表头开始，遍历
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            //1-1.e.key==null时，直接替代value
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //2.头Entry不存在时，直接插入entry
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

    /**
     * @param hash 计算后key的hash值
     * @param key
     * @param value
     * @param bucketIndex 应该插入到Entry[]的哪个位置
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        //1.当前bucketIndex位置的头Entry e
        Entry<K,V> e = table[bucketIndex];
        //2.在bucketIndex位置新建一个Entry，新建Entry.next=原头Entry，也就是addEntry的Entry都被加到了链表头
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        //hashmap在每次addEntry完后检查是否扩容，而list是在每次加入之前检查：ensureCapacity(size + 1);elementData[size++] = e;
        if (size++ >= threshold)
            resize(2 * table.length);
    }

    //扩容，把hashmap的容量设置为新容量newCapacity
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        //每次扩到到原来的两倍，总有一个时候到MAXIMUM_CAPACITY
        if (oldCapacity == MAXIMUM_CAPACITY) {
            //到了MAXIMUM_CAPACITY设置threshold后直接return
            threshold = Integer.MAX_VALUE;
            return;
        }

        //1.新建newCapacity大小的Entry数组
        Entry[] newTable = new Entry[newCapacity];
        //2.把当前Entry的数据全部移到新Entry数组中
        transfer(newTable);
        //3.用已经就绪的新Entry数组重新给table赋值
        table = newTable;
        //4.设置新的threshold
        threshold = (int)(newCapacity * loadFactor);
    }

    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        //1.从0开始遍历原Entry数组
        for (int j = 0; j < src.length; j++) {
            //2.拿到下标为j的链表头Entry e
            Entry<K,V> e = src[j];
            //3.遍历链表
            if (e != null) {
                src[j] = null;
                do {
                    //3-1.e的下一个Entry，为了继续遍历做准备
                    Entry<K,V> next = e.next;
                    //3-2.计算e应该存放在新Entry数组的位置下标
                    int i = indexFor(e.hash, newCapacity);
                    //3-3.将e插入到新Entry[i]链表的表头
                    e.next = newTable[i];
                    //3-4.将Entry[i]表头的Entry重新定位为e，这样就完成了一个元素的重新hash
                    newTable[i] = e;
                    //3-5.继续链表的下一个Entry
                    e = next;
                } while (e != null);
            }
        }
    }

 

八.删数据

 

public V remove(Object key) {
        Entry<K, V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

    /**
     * Removes and returns the entry associated with the specified key in the
     * HashMap. Returns null if the HashMap contains no mapping for this key.
     */
    final Entry<K, V> removeEntryForKey(Object key) {
        // 1.计算hash和index
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry<K, V> prev = table[i];
        Entry<K, V> e = prev;
        // 2.遍历i位置的Entry链表
        while (e != null) {
            Entry<K, V> next = e.next;
            Object k;
            // 2-1.e满足hash(key.hashCode()) == e.hash && (key == e.key ||
            // key.equals(e.key))，找到了要移除的Entry
            if (e.hash == hash
                    && ((k = e.key) == key || (key != null && key.equals(k)))) {
                // 2-2.移除操作modCount++, size--
                modCount++;
                size--;
                // 2-3-1.如果prev和e相等，说明要删除的Entry是链表头，直接将table[i]位置的Entry设置为next，就删除了e
                if (prev == e)
                    table[i] = next;
                else
                    // 2-3-2.如果不相等e =
                    // prev.next，说明要删除的Entry是除链表头外的其他Entry，将prev.next设置为next，就删除了e
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            // 把prev和e到移到下一个
            prev = e;
            e = next;
        }

        return e;
    }

    /**
     * 还是将o的key拿到，然后和removeEntryForKey(Object key)一样了
     *
     * @param o
     *            must be Map.Entry
     * @return
     */
    final Entry<K, V> removeMapping(Object o) {
        if (!(o instanceof Map.Entry))
            return null;

        Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
        Object key = entry.getKey();
        ......
    }

 

九.对table[0]位置存放数据的理解

package com.zzy.collection2;

import java.util.Map;

public class TestHashMapEntry0 {
    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(null, 1);
        map.put(null, 2);

        map.put(0, 3);
        map.put(0, 4);
    }

}

 

1. put(null, value)其本质是addEntry(0, null, value, 0);
2. put(0, value)其本质是addEntry(0, 0, value, 0);
3. put(null, value1)后put(0, value2)都是向table[0]链表中处添加Entry，但 0 != null，所有value2不会覆盖value1。
4. put(null, value1)后再次put(null, value2)，value2覆盖value1。