HashMap的内部实现机制之篇一

        HashMap的内部实现是采用的是hash表这种数据结构。

 

   什么是hash表？

   答曰：hash表又叫散列表。hash表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做hash函数，存放记录的数组叫做hash表。

    简单的说：hash表就是一个数组与链表的集合。集成了数组遍历快和链表方便插入删除的优点。

   

     HashMap是如何内部实现的？

     大概说来，主要有以下几点：

1 底层是用一个Entry<k,v>数组实现的，每个Entry对象的内部又含有指向下一个Entry类型对象的引用。

 

看Entry类型，内部拥有加入Map中的K,V，hash值，和自身的一个引用

  static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next; ///Entry类型内部有一个自己类型的引用，指向下一个Entry
        
        final int hash; 
     ………………………………………………………………}

 
实例化数组（默认大小为16）后，通过hash()函数得到在数组中的存储位置index，笔者把这一步就理解为散列。

    且看源代码：

  

//源码中一个不带参数的构造方法，new了一个Entry数组
  public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }

 注：默认的default_init_capicity为16。

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        ...........
}

     注意此处与hashTable的对比，hashTable是直接用key.hashCoe()当hash值的，因此少了hash（）函数，散列分布没那么均匀，这也是hashMap代替HashTable的一定优化。

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

  暂且不看key值为空的情况。当它不为空时，通过一个hash（）函数得到hash值，函数参数为key.hashCode()(暂且知道hashCode是一种散列码，在此我们可先理解为对象的内存地址，具体请看下篇)，然后再调用一个indexFor（）函数来得到数组中的存储位置。

   内部实现毕竟要精益求精一些。为什么在这里要绕两个函数hash（）函数和indexFor()函数才得到真正需要的index?

  其实这样做是为了让散列更加均匀，减少冲突的概率。当每个数组上都有值时，链表中需存放的元素就少了，因此只是尽可能的求得一种时间和空间上的平衡。然而这两个函数为什么是这样，笔者真心不知。再次还请看官不吝赐教！！！！

 

  

    附录：此处还有key为空的情况，key值重复的情况。当key值重复时，我们自己测试易发现是用新的value值代替了旧的value值，对此有兴趣的看官不妨深究下把。

 

 

2 解决冲突：因为即使键key不同，通过hash函数得到的index值也可能相同（当然，也正是存在这种冲突，才存在hash表结构，不然就直接是数组存储了）。这时我们可以把得到相同index值的元素连接到数组中对应index值位置的后面，即把该位置作为链表的头结点，在后面添加节点。

 

3 数组扩容。通过api可以发现，hashMap的构造方法可以有两个参数，一个为初始容量initCapicity,另外一个为装载因子loadFactor.初始容量很好理解，即为数组的初始大小；那何谓装载因子。据api注解：。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。 据笔者本人的理解：不管什么加载因子等书面名词，它只是对可以放进hash表的数目的一个限制，当超过这个限制时就需扩大数组容量，重新散列所有元素。我们也可以自定义一个阀值来代替这个加载因子，例如：当数组中的元素元素过少，而后面跟的链表过长，那么整体就偏向于链表存储而缺失了数组存储的优点了，因此我们可以设定一个阀值为500，即当某个链表长度超过500，则需要扩大数组容量，进行rehash操作。

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

 注：此处threshold也可以理解为阀值。此处的resize（）扩容方法和后面的rehash，源码为transfer()方法就需大家一起探究了。笔者有点力不从心啊。

 

4 rehash():在数组扩容之后执行该操作。即把原来已经散列过的元素取出重新散列一遍，因为数组长度扩大了，这得到的散列位置可能和原来不同。因为要全部取出原来已经散列过的元素，因此这步操作是非常耗时的。因此我们在预定数组初始长度时，最好选取一个合适的长度和加载因子，尽量避免rehash（）出现。

 

 至此，hashMap的内部实现机制大体框架就是这样了。 

 

评论

3 楼 Mr_lee_2012 2012-03-12  

精辟，同为大三，深表惭愧！

2 楼 微Smile 2012-03-09  

coolxing 写道

不错
楼主的叙述虽然有很多不清晰的地方, 但至少给对HashMap内部实现比较感兴趣的同学一个切入点

恩 谢谢 我会继续努力的！

1 楼 coolxing 2012-03-09  

不错
楼主的叙述虽然有很多不清晰的地方, 但至少给对HashMap内部实现比较感兴趣的同学一个切入点