HashMap 源码解读

HashMap是我们在日常写代码时最常用到的一个数据结构，它为我们提供key-value形式的数据存储。同时，它的查询，插入效率都非常高。

在之前的排序算法总结里面里，我大致学习了HashMap的实现原理，并制作了一个简化版本的HashMap。 今天，趁着项目的间歇期，我又仔细阅读了Java中的HashMap的实现。

HashMap的初始化：
Java代码
public HashMap(int initialCapacity, float loadFactor)  
 
public HashMap(int initialCapacity)  
 
public HashMap()  
 
public HashMap(Map<? extends K, ? extends V> m) 

    public HashMap(int initialCapacity, float loadFactor)

    public HashMap(int initialCapacity)
   
    public HashMap()

    public HashMap(Map<? extends K, ? extends V> m)


initialCapacity表示了HashMap中初始的大小，loadFactor则表示每次当HashMap中的空间不够时，按什么样的比例来扩展空间。

我们来看下HashMap是怎样扩展空间的：
Java代码
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 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);
    }

可以看到这个方法并不是public的，因此用户无法手动去调用这个方法。

变量threshod维持着HashMap下一次增长将要到达的长度。而MAXIMUM_CAPACITY则包含了最大可能长度：1 << 30。

注意，这个长度是2的倍数，我们在后面会经常看到2的幂数，事实上，HashMap规定了它的table长度只能是2的幂数，因此，即使你设置了loadFactor， 它也未必按照你的想法来增长。这点，从构造器方法里面可以看出：
Java代码
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);  
 
    // Find a power of 2 >= initialCapacity  
    int capacity = 1;  
    while (capacity < initialCapacity)   
        capacity <<= 1;  
 
    this.loadFactor = loadFactor;  
    threshold = (int)(capacity * loadFactor);  
    table = new Entry[capacity];  
    init();  
} 

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

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
   
        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
    }


可以看见capacity的构建方法，先是设置为1，然后不停的左移直到大于等于initialCapacity。

trasfer方法的实现需要好好看一下：
Java代码
private transient int contentionFlag = 0;  
 
void transfer(Entry[] newTable) {  
    onEntry();  
    try {  
        transfer0(newTable);  
    } finally {  
        onExit();  
    }  
}  
 
   private synchronized void onEntry() {  
   switch(contentionFlag) {  
       case(0):    contentionFlag=1;       /* Free -> Busy */ 
                   break;  
       case(1):    contentionFlag=2;       /* Busy -> Contended */ 
                                           //FALLTHRU  
       case(2):    throw new ConcurrentModificationException(  
                       "concurrent access to HashMap attempted by " + Thread.currentThread());  
       default:    throw new RuntimeException(  
                       "Unexpected contentionFlag " + contentionFlag);  
    }  
}  
 
   private synchronized void onExit() {  
          int oldContentionFlag=contentionFlag;  
    contentionFlag=0;  
    switch(oldContentionFlag) {  
        case(1):    break;                                     /* Busy -> Free */ 
        case(2):    throw new ConcurrentModificationException( /* Contended -> Free */ 
                         "concurrent access to HashMap attempted by " + Thread.currentThread());  
        default:    throw new RuntimeException(  
                        "Unexpected contentionFlag " + oldContentionFlag);  
    }  
}  
 
private void transfer0(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;  
                int i = indexFor(e.hash, newCapacity);    
                e.next = newTable[i];  
                newTable[i] = e;  
                e = next;  
            } while (e != null);  
        }  
    }  
} 

    private transient int contentionFlag = 0;

    void transfer(Entry[] newTable) {
        onEntry();
        try {
            transfer0(newTable);
        } finally {
            onExit();
        }
    }

       private synchronized void onEntry() {
       switch(contentionFlag) {
           case(0):    contentionFlag=1;       /* Free -> Busy */
                       break;
           case(1):    contentionFlag=2;       /* Busy -> Contended */
                                               //FALLTHRU
           case(2):    throw new ConcurrentModificationException(
                           "concurrent access to HashMap attempted by " + Thread.currentThread());
           default:    throw new RuntimeException(
                           "Unexpected contentionFlag " + contentionFlag);
        }
    }

       private synchronized void onExit() {
              int oldContentionFlag=contentionFlag;
        contentionFlag=0;
        switch(oldContentionFlag) {
            case(1):    break;                                     /* Busy -> Free */
            case(2):    throw new ConcurrentModificationException( /* Contended -> Free */
                             "concurrent access to HashMap attempted by " + Thread.currentThread());
            default:    throw new RuntimeException(
                            "Unexpected contentionFlag " + oldContentionFlag);
        }
    }

    private void transfer0(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;
                    int i = indexFor(e.hash, newCapacity); 
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }


首先是onentry方法， 这个方法先判断是否有其它的线程在操作该HashMap进行resize，如果没有，将contentionFlag 设为1， 如果已经有了，就设为2，表示已经有冲突了。如果已经有冲突存在了，直接抛exception。

无怪网上都说HashMap是非线程安全的，而HashTable才是线程安全的。从这个角度理解，确实是这样的。

而当onexit时，如果contentionFlag为1，则直接结束，如果为2，表示在onentry时已经有冲突，那么直接抛出excpetion。

这一部分内容非常有意思，可以在别的地方借鉴这种用法。想起来之前有人问我关于线程同步的问题，我想这个应该是个很好的解决办法，等回头看看HashTable这个号称可以支持多线程的结构之后，在综合分析一下这块内容。 而在最新版本的JDK6b17中，似乎已经去掉了该部分的代码。

而对于transfer0这个方法名，实在是太难听了。

这个方法主要是创建了一个新数组，并把旧数组里面的数据放到新数组里。这里有两个很重要的内容，我们一个一个看。

a. 链表的结构
我们已经知道了hashmap中对于相同hashcode的值，是通过链表的形式挂在数组位上面的，但当我们在做resize的时候，整个链表的顺序其实是被颠倒了。 因为是private代码，所以其实并没有对此有太多的解释。我所奇怪的是，如果不把链表的顺序颠倒的话，这段代码会很容易写，性能也会高很多，可是为什么要特意去做这件事情呢？
我曾经怀疑java中是个环状的链表，可是看代码似乎又不是。。。奇怪的东西。

b. indexFor方法
这里要先看看源码
Java代码
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);  
}  
 
/** 
* Returns index for hash code h. 
*/ 
static int indexFor(int h, int length) {  
return h & (length-1);  
} 

  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);
  }
 
  /**
  * Returns index for hash code h.
  */
  static int indexFor(int h, int length) {
  return h & (length-1);
  }


indexFor的代码里面，通过h和length-1做并操作，因为length的值永远是2的幂数（参见排序算法），因此这个方法就是对h进行取模，h % 2^p， 返回的将是h的p个最低位组成的数字。这样做究竟有什么好处呢？

最大的好处就是，对于hashcode值大于table长度的，可以将之映射到table长度以内的值。其它的，我还真没看出有什么好处。

再看hash方法，事实上，java中的HashMap并不是直接去的object的hashcode值，而是先对他进行了一个简单的调整，也就是hash这个方法。

看对于该方法的介绍，该方法保证了load因子为8，即使该hashcode使用的是将每位的值乘以一个常数。

我们知道我们常常设计hashcode的方法是，比如一个string，就把每一位取出来，乘以一个常数，通常是质数，然后相加，这样得到的hashcode，会在这里得到更好的调整。

算法导论里面是这么说的：

假设机器的字长是w，那么我们就可以选择A的值为 s/2^w, s为0到2^w之间的整数，这样s=A× 2^w 用k 乘以s，取低位，再从低位中取p位，这几位就形成了k的hash值。官方建议A可以取黄金分割0.618。

这块内容是在是太复杂了，现在我也只能深入到这一步，再继续下去也看不太懂了。 JDK的作者建议去看看程序设计艺术第三卷，可惜我连第一卷都没看完。看来是要等将来解决这个问题了。

不过有一点要提的是，这种方法只在最新版本的HashMap中才有，老版本的都是直接用了key对象的hashcode。

HashMap中的其它方法都比较常规，这里就不赘述了。值得一提的是，put方法，如果key已经存在的话，会用新的value替代旧的value，并将旧value返回，否则返回空。

最后，有一个从来没用过的关键字吸引了我：
transient volatile int modCount;

查了下书，volatile是用来处理线程同步的，这里就直接转southking的一篇博文：


我们知道，在Java中设置变量值的操作，除了long和double类型的变量外都是原子操作，也就是说，对于变量值的简单读写操作没有必要进行同步。

这在JVM 1.2之前，Java的内存模型实现总是从主存读取变量，是不需要进行特别的注意的。而随着JVM的成熟和优化，现在在多线程环境下volatile关键字的使用变得非常重要。

在当前的Java内存模型下，线程可以把变量保存在本地内存（比如机器的寄存器）中，而不是直接在主存中进行读写。这就可能造成一个线程在主存中修改了一个变量的值，而另外一个线程还继续使用它在寄存器中的变量值的拷贝，造成数据的不一致。

要解决这个问题，只需要像在本程序中的这样，把该变量声明为volatile（不稳定的）即可，这就指示JVM，这个变量是不稳定的，每次使用它都到主存中进行读取。一般说来，多任务环境下各任务间共享的标志都应该加volatile修饰。

Volatile修饰的成员变量在每次被线程访问时，都强迫从共享内存中重读该成员变量的值。而且，当成员变量发生变化时，强迫线程将变化值回写到共享内存。这样在任何时刻，两个不同的线程总是看到某个成员变量的同一个值。

Java语言规范中指出：为了获得最佳速度，允许线程保存共享成员变量的私有拷贝，而且只当线程进入或者离开同步代码块时才与共享成员变量的原始值对比。

这样当多个线程同时与某个对象交互时，就必须要注意到要让线程及时的得到共享成员变量的变化。

而volatile关键字就是提示VM：对于这个成员变量不能保存它的私有拷贝，而应直接与共享成员变量交互。

使用建议：在两个或者更多的线程访问的成员变量上使用volatile。当要访问的变量已在synchronized代码块中，或者为常量时，不必使用。

由于使用volatile屏蔽掉了VM中必要的代码优化，所以在效率上比较低，因此一定在必要时才使用此关键字。







本想单独为HashTable写一篇博文的，但是等学习完之后，觉得大部分跟HashMap是一样的，我所期待的线程同步居然仅仅是通过synchronized 来实现的。 想想还是算了，就在这里列出HashTable与HashMap的几个区别：

1. 数组的长度不必是2的倍数，而是可以为任意数值。
2. 求index的办法也便简单了：(hash & 0x7FFFFFFF) % array.length
3. 对于hash值不再做特殊处理，直接使用。

即使我对HashMap的实现方法还有疑惑，但是毫无疑虑，那些算法可以提高效率。 而在Hashtable中，这些提高效率的算法都没有了，同时，过多的sychronized定义，必然会降低performance。