青菜猫(孙宇博客),青菜猫(孙宇博客),青菜猫(孙宇博客)http://www.javasdc.cn/
posts - 29,  comments - 63,  trackbacks - 0

HashMap 是通过key_value当成一个整体进行处理,通过key的hashCoder反回一个int数,然后还会调用一个hash方法。来确定存储位置。
HashMap 存储java对像,其实并没有真正将 Java 对象放入 Set 集合中,而是多个引用变量所组成的集合,这些引用变量指向实际的 Java 对象。
HashMap 存储.以如下代码为例:
HashMap<String,String> ma = new HashMap<String,String>();
        ma.put("a", "aaa");
        ma.put("b", "bbb");
HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。
在上面代码中系统会调用a的hashCode方法来确定来决定该元素的存储位置。以下是部分源码
public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        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))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
 }

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);
 }
大家可以看下上面的Entry,我理解成其实就是一个key_value对。然后通过hash(key.hashCode())这样确定位置。系统这样才能存储在那里。
关键是int i = indexFor(hash, table.length);我理解是这个对找到相对应的索引块。加快速度。包括get的时候也会调用这个方法,确实索引块的位置.
来看看具体算法
 static int indexFor(int h, int length) {
        return h & (length-1);
 }
h是hash的一个值,length中这个table的长度。假设 h=5,length=16, 那么 h & length - 1 将得到 5,这个length为什么我会假设是16,大家可以看看源码
也就知道static final int DEFAULT_INITIAL_CAPACITY = 16; 初始化的时候就是16。这样目的在于计算得到的索引值总是位于 table 数组的索引之内
根据上面 put 方法的源代码可以看出,当程序试图将一个 key-value 对放入 HashMap 中时,
程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,
那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true,
新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value,但 key 不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false
,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }
大家看看这里就知道了, 就是把添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象,那新添加的 Entry 对象指向原有的 Entry 对象(产生一个 Entry 链),
如果 bucketIndex 索引处没有 Entry 对象,也会新放入的 Entry 对象指向 null,也就是没有产生 Entry 链。
 如果 Map 中的 key-value 对的数量超过了极限,就会度扩充到 2 倍。
HashMap的取值
public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        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是用equals判断当前键是否和表中的键相同。所以在这里要说明如果要用自己的类做为HashMap的键,必须同时重载wqual()和hashCode()









posted on 2010-09-01 11:39 青菜猫(孙宇) 阅读(2045) 评论(1)  编辑  收藏 所属分类: java


FeedBack:
# re: HashMap源码解析
2010-09-02 09:44 | 泷洲彼岸-Scelong
所以在这里要说明如果要用自己的类做为HashMap的键,必须同时重载wqual()和hashCode()

楼主,这里的“重载”是不是应该为重写或覆盖呢?  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航:
 
<2010年9月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

青菜猫(孙宇)结交天下朋友,在网上吸取知识..

常用链接

留言簿(16)

随笔分类

随笔档案

文章分类

搜索

  •  

最新评论

阅读排行榜

评论排行榜

青菜猫(孙宇博客),青菜猫(孙宇博客),青菜猫(孙宇博客)http://www.javasdc.cn/