Java HashMap深度剖析_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > Java HashMap深度剖析

Java HashMap深度剖析

 2012/2/14 10:22:31  alex.Lin  程序员俱乐部  我要评论(0)
  • 摘要:一、首先再简单重复一下Hash算法简单的说就是一种将任意内容的输入转换成相同长度输出(有个范围,假设10位的数字,用一个称之为HashTable的容器来存放)的加密方式------hash如(假设):“a”---?10位数1123---?10位数2…注意:任意内容的输入,范围是无穷无尽,肯定比相同长度输出(如10位数)要大很多,那么就会造成不同的输入,会得到相同的输出(值)----hash冲突HashMap当然也无法避免冲突问题二、HashMap源码片段publicHashMap(){this
  • 标签:has Map Hash Java
一、首先再简单重复一下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出来了

}


发表评论
用户名: 匿名