Java HashMap深度剖析

一、首先再简单重复一下Hash算法 
简单的说就是一种将任意内容的输入转换成相同长度输出（有个范围，假设10位的数字，用一个称之为HashTable的容器来存放）的加密方式------hash 
如（假设）： 
“a”---10位数1 
123---10位数2 
… 
注意：任意内容的输入，范围是无穷无尽，肯定比相同长度输出（如10位数）要大很多，那么就会造成不同的输入，会得到相同的输出（值）----hash冲突 
HashMap当然也无法避免冲突问题 

二、HashMap源码片段 
public HashMap() { 
        this.loadFactor = DEFAULT_LOAD_FACTOR;//负载因子，默认0.75 
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); 
        table = new Entry[DEFAULT_INITIAL_CAPACITY]; 
//使用的是Entry数组 
        init(); 
} 

public V put(K key, V value) { 
        if (key == null)//空的情况，允许存空 
            return putForNullKey(value); 
        int hash = hash(key.hashCode());//根据key的hashCode再来计算一个hash值----根据hash冲突可以知道不同的key对应的hashCode可能一样（如果不被重写的话，Object的hashCode()生成的hashCode存放在java底层的一个大的HashTable上，不过我想JDK应该已经做过冲突处理，不会使用这么简单的hash算法，除非自己重写hashCode(),否则应该不会有冲突，真的发生冲突估计要内存溢出了） 
//就算hashCode不同，通过hash()出来的hash值也可能冲突(后面会讲到) 
        int i = indexFor(hash, table.length); 
        for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
            Object k; 
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//该位置已经有了，且key也完全是同一个，就覆盖，否则也是走下面的新开(后面会有例子) 
                V oldValue = e.value; 
                e.value = value; 
                e.recordAccess(this); 
                return oldValue; 
            } 
        }//已经存在的情况 
//以下是新增的情况 
        modCount++; 
        addEntry(hash, key, value, i); 
        return null; 
    } 

/** 
为给定的hashCode增加一个hash方法，用于抵消低质量的hash函数。这是很关键的，因为HashMap使用power-of-two长度的hash表，否则遇到冲突的hashCode无法区分     
     */ 
    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); 
    } 

//根据hashCode及table的长度计算index 
static int indexFor(int h, int length) { 
        return h & (length-1); 
    } 

void addEntry(int hash, K key, V value, int bucketIndex) { 
    Entry<K,V> e = table[bucketIndex];//先取原有的元素作为next，index冲突的时候用，形成一个“链条” 
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
        if (size++ >= threshold) 
            resize(2 * table.length); 
    } 

static class Entry<K,V> implements Map.Entry<K,V> { 
        final K key; 
        V value; 
        Entry<K,V> next;//存放自己的下一个 
        final int hash; 
... 
} 

//------再看一下get方法 
public V get(Object key) { 
        if (key == null) 
            return getForNullKey(); 
        int hash = hash(key.hashCode()); 
//根据key的hashCode计算出“链条”在table中的index，再到“链条”中查找符合自己key的对象 
        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; 
  } 


三、用个简单的例子详细解读HashMap的运作 
public static void main(String[] args) { 
HashMap map = new HashMap(); 
//map里包含一个Entry数组table（默认长度16） 

//测试1：测试hashMap的存储 put(K,V) 
//--------存放第1个对象---------- 
String s1 = "123";
map.put(s1, "123"); 
//s1的hashCode = 48690 
//hash(hashCode) = 46246 ---HashMap的再次hash() 
//indexFor(hash, table.length)=6 得出存放在数组中的位置为6+1（从0开始） 
//虽然存放的是第一个元素，但却不是放在第一位，不是顺序存放， 
//我们看table的结果为：[null, null, null, null, null, null, 123=123, null, null, null, null, null, null, null, null, null] 
//读取的时候不需要按顺序对比KEY，只需通过hashCode计算出其位置就可以快速读取。 

//--------存放第2个对象---------- 
String s2 = "123"; 
//s1和s2使用编译常量区，指向同一个常量 
System.out.println((s1==s2) +" s1.hashCode="+s1.hashCode());//肯定是true 
map.put(s2, "124");//s2和s1指向同一个对象，无疑是覆盖 

//--------存放第3个对象----------
         String s3 = new String("123"); 
//String已经重写hashCode,相同内容的字符串hashCode一定是固定相同的。 
System.out.println((s1==s3) +" s3.hashCode="+s3.hashCode());//此时就是false了 
//s3指向了“堆”区里的一个新建对象，但其值和s1一样，故hashCode也是一样的 
map.put(s3, "125");//虽然s3和s1不是一个对象，但hashCode一样，map里只比较hashCode，故认为是同一个 

System.out.println(map.size());//size只有一个 


//测试2：hashMap冲突解决
//-----再存11个，正好达到threshold 
for(int i=0;i<11;i++){ 
map.put("i"+i, i); 
//有趣的事情来了 
//当存到i9的时候，"i9"的hashCode=3312，hash(hashCode)=3110，----跟s3明显不同 
//indexFor(hash, table.length)=6，也就是说存放在table的位置和之前的s3重了，咋办？？？ 
//继续执行，判断key的hash和值发现不是同一个，所以还是执行addEntry方法， 
//addEntry也毫不客气的把位置让给"i9", } 
//--此时的table为： 
//[i0=0, null, null, null, i10=10, null, i9=9, null, 
// i8=8, i7=7, i6=6, i5=5, i4=4, i3=3, i2=2, i1=1] 
//此时的table中已经看不到s3（123=125）的存在了，那么s3哪去了呢？ 
//查看上面的源码段，原来每个Entry除了自己的信息外，还包含了个next（自己的下一个Entry，【可以理解为纵向的Entry，而不是table中的下一个】， 
//该next是不存在table中【如果再重复，还可能再包含更深一级的next，这就跟“链”一样】） 
//也就是说此时s1含在了i9中了，2个共用table的第7个位置 
//我们取map元素的时候会取table中的Entry+逐级递归取每个Entry的next，这样就不会丢失了 


//测试3：测试HashMap的空间扩展
                  //负载因子0.75，threshold（阀，table存储边界） = table容量*负载因子  = 16*0.75 = 12 
//当map的实际长度超过threshold，则新建一个size*2的table，把原有的小table数据都放进来 
//再存第13个，超过12，将会执行resize并transfer-data 
map.put("a", "a"); 
//resize table----即定义一个新的2倍size大小的Entry[]数组，没什么好讲 
//transfer data---将旧数组数据存放到新数组 
//1、读取全部oldTable的数据【注意：是全部，含next】 
//2、并不是简单的存放，将每一个Entry在新的数组中重新计算位置,再来一个indexFor(hash, table.length)，这时本来2个一样的index此时很可能就不一样了，当然也不排除本来不一样变成一样的。 
//HashMap代码段： 
/*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);*/ 

//就本例解析如下： 
//取到“i9”的时候，新的indexFor算出来也是6（巧合吧），放到了newTable[6] 
//取“i9”的next（s3），计算s3的indexFor也正好是6（又是巧合吧，如果不是6那他们就可以撇开关系各自存储了），但是此时的newTable[6]换成了s3,而i9只能作为s3的next来存储了 

//--最后table如下 
//[null, null, null, null, null, null, 123=125, a=a, 
//null, null, null, null, null, null, null, null, i0=0, 
// null, null, null, i10=10, null, null, null, i8=8, 
//i7=7, i6=6, i5=5, i4=4, i3=3, i2=2, i1=1] 
//---i9不见了，s3出来了
}