Java源码学习:HashMap实现原理

AbstractMap

HashMap继承制AbstractMap，很多通用的方法，比如size()、isEmpty()，都已经在这里实现了。来看一个比较简单的方法，get方法：

public V get(Object key) {
    Iterator<Entry<K,V>> i = entrySet().iterator();
    if (key==null) {
        while (i.hasNext()) {
            Entry<K,V> e = i.next();
            if (e.getKey()==null)
                return e.getValue();
        }
    } else {
        while (i.hasNext()) {
            Entry<K,V> e = i.next();
            if (key.equals(e.getKey()))
                return e.getValue();
        }
    }
    return null;
}

单从这里看看不到Map的搜索策略，这里显示的仅仅就是遍历全部元素挨个测试是否匹配。

remove方法中先匹配到元素，然后利用迭代器Iterator的remove方法将元素从记录中删除。

    public V remove(Object key) {
        Iterator<Entry<K,V>> i = entrySet().iterator();
        Entry<K,V> correctEntry = null;
        if (key==null) {
            while (correctEntry==null && i.hasNext()) {
                Entry<K,V> e = i.next();
                if (e.getKey()==null)
                    correctEntry = e;
            }
        } else {
            while (correctEntry==null && i.hasNext()) {
                Entry<K,V> e = i.next();
                if (key.equals(e.getKey()))
                    correctEntry = e;
            }
        }

        V oldValue = null;
        if (correctEntry !=null) {
            oldValue = correctEntry.getValue();
            i.remove();
        }
        return oldValue;
    }

 transient和volatile

终于看到存储key和value的地方了，这里马上出现了两个Java关键字，transient和volatile：

    transient volatile Set<K>        keySet = null;
    transient volatile Collection<V> values = null;

transient关键字的意思是说改字段不会被持久化和反持久化，这个会在对象序列化到文件时用到。参考这里。

volatile就比较复杂一点儿了，一旦一个共享变量（类的成员变量、类的静态成员变量）被volatile修饰之后，那么就具备了两层语义：

　1）保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。

　2）禁止进行指令重排序。

参考：http://www.cnblogs.com/dolphin0520/p/3920373.html

有点儿线程安全的意思，就是说一个变量被另外一个线程修改了，其他在使用这个变量的线程也会知道。

文章中所举例子：

//线程1
boolean stop = false;
while(!stop){
    doSomething();
}
 
//线程2
stop = true

以上代码是有可能死循环的。

接下来初始化Entry时，如果用一个Map去初始化另外一个Map，那么这个Map的初始大小将为原先Map的2倍：

    public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        inflateTable(threshold);

        putAllForCreate(m);
    }

    private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }

    /**
     * Inflates the table.
     */
    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);
    }

Integer.highestOneBit(num) 

拿到原先Map的size之后初始化一个新的Entry数组，这个数组的的size增加到原先Map的2倍。方法Integer.highestOneBit(num)的作用是得到比num还大的但是是2的指数倍的数。这些数其实就是2,4,8,16,32,64,128,256,512

可以看出JDK源码中很多地方对于*2这种操作都不是直接乘以2，而是采用向左位移一位，比如：

(number - 1) << 1

HashMap数据结构

插入元素

1、key为null的Entry存放在数组Entry[]的第一位的Entry链表中，即Entry[0]，仔细看看，Map.put()方法其实是有返回值的，这个返回值就是被替换掉的Value（如果存在的话）。

2、key不为空，通过Hash散列之后存入数组不同位置的链表中。散列中用到了按位与（&）运算：

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

如何进行Hash散列

按位与运算规则如下：

0 & 0 = 1

0 & 1 = 0

1 & 0 = 0

1 & 1 = 1

也就是只有同时两个都为1时才等于1。这里要求数组的长度必须是2指数倍是有原因的。比如length = 256（2的8次方），那么它换算成二进制就是1后面8个0：

100000000

256 - 1 换算成二进制刚好是7个1：

1111111

用这个数与任意的数N进行按位与运算的效果是：保留N的后7位：

         1 1 1 1 1 1 1
&    1 0 1 0 0 1 0 1 0
-------------------------------
     0 0 1 0 0 1 0 1 0

 后面这7位就像亮着的几盏灯，亮几盏就能截取多少位。正是这样实现了数据的Hash散列。

从上面的代码可以看出，Hash散列时仅用到了了Object.hashCode()的后几位，如果n - 1 = 15即0x1111,那么发送Hash冲突的可能性会非常大，为了解决这个问题，可以理解为需要在原先的Object.hashClde()基础之上做一些混淆，即使整个原始HashCode都会影响最终的散列。

    final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // 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);
    }

这里通过高位与低位（向右位移的距离不一样）的异或运算进行“混淆”。

---

 总结

HashMap的实现原理?

通过元素的哈希码来做映射，将数据散列到一个数组中，如果发生了哈希冲突则将冲突的元素形成一个链表进行存储。Java8中进行了优化，冲突的元素多到一定程度时，将改链表为红黑树，这样有效提高了高冲突时的性能；

HashMap需要注意些什么?

注意两个参数：

容量（Capacity）：容器也可以叫做数组的初始大小，如果元素增加到一定程度（也就是负载因子），就会将容量翻倍。

负载因子（Load factor）：默认负载因子是0.75，也就是当元素超过四分之三的时候会增加数组的大小。

需要注意的是，如果你想要HashMap遍历得更快，应该把容量设计得小点儿、负载因子设计大点儿，这样其实是让HashMap的数组存储地更密集些，能提高遍历速度。