posts - 167,  comments - 30,  trackbacks - 0

基础很重要哦...

1.       HashMap工作原理:

HashMap是基于Hash表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null作为键和值。无序。

 

2.       HashMap数据结构:

HashMap实际上是一个“链表散列”的数据结构,即是数组和链表的结合体。HashMap底层就是个数组结构,数组的每一项是一个链表。当新建一个HashMap时,就会新创建一个数组。

Java代码:

/**

  * 长度扩容必须是2的倍数

  */

transient Entry[] table;

 

static class Entry<K,V> implements Map.Entry<K,V> {

        final K key;

        V value;

        Entry<K,V> next;

        final int hash;

… …

public HashMap() {

        this.loadFactor = DEFAULT_LOAD_FACTOR;

        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);

        table = new Entry[DEFAULT_INITIAL_CAPACITY];

        init();

}

可以看到,每个Entry就是一个键值对,本身对象持有下一个对象的引用,这样就构成了链表。

为了元素在HashMap中均匀分布,通常想到的是把hashCode对数组长度取模运算,但是取模运算的消耗比较大,那么HashMap做法是根据key算的的hashCode跟数组-1进行“与”运算(&)

将初始大小设置为16的原因(当扩容是必须是2的整数次幂):主要为了使HashMap的访问的性能最高,减少keybucket中存取时的碰撞几率。

 3.       HashMapresize

HashMap的元素越来越多时,碰撞的几率就越来越高,因为数组的长度初始时是固定的,所以为了提高查询的效率,就要对HashMap的数组进行扩容,在HashMap数组扩容后最消耗性能点是:原数组中的元素必须重新计算在新数组中的位置,然后存放进去。

 什么时候扩容?

HashMap中的元素个数超过数组大小*负载因子的时,会进行数组扩容,默认的loadFactor0.75(意思是当一个Map填满了75%bucket的时),也就是当为1216*0.75),就会把数组扩容原来大小的两倍:16*2=32。然后重新计算每个元素在数组中的位置(此时比较消耗性能了)。 这个过程也叫做rehashing(因为它调用了hash方法找到新bucket的位置)。

建议当我们已预知了数组的元素个数,可根据具体需求自行设置数组初始容量以便提高查询性能。但是要记得考虑“&”的问题。这样也解决了resize的问题。

 

4. HashMap的存取实现:

put方法分析:

如果传入keynull值,则将其放倒数组的第一个位置。如果key不为空,首先对key调用hashCode方法,对返回的hashCode值做hash,通过计算hash值可以找到bucket(这个bucket就是指Entry数组)位置(下标)来存储Entry对象。

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;

}

 

 

虽然发生碰撞的几率较小,但是如果发生碰撞,则会将新添加的元素放倒链表头部,早先加入的元素放倒链表尾部(我们可以将发生碰撞的这个链表理解为LinkedList,这个LinkedList中存储了键值对形式的Map.Entry对象)。

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

}

 get方法:

调用get方法时,首先会根据传入的key调用hashCode方法,计算hash值找到bucket位置,然后遍历链表(即上面所说的linkedList<Entry<K,V>>),判断hashkeyequals方法查找到对应的Entry对象。

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;

}

 最佳实践方式:

使用不可变的、声明作final的对象,并且采用合适的equals()hashCode()方法的话,将会减少碰撞的发生,提高效率。不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度,使用StringInterger这样的wrapper类作为键是非常好的选择。

 参考:http://www.importnew.com/7099.html

posted on 2013-11-18 18:01 David1228 阅读(2872) 评论(4)  编辑  收藏 所属分类: JAVA

FeedBack:
# re: 源代码分析之HashMap
2013-11-19 10:08 | 鹏达锁业
支持博主分享  回复  更多评论
  
# re: 源代码分析之HashMap[未登录]
2013-11-19 11:29 | David
常来^^, 多谢支持O(∩_∩)O哈~ @鹏达锁业
  回复  更多评论
  
# re: 源代码分析之HashMap
2013-12-15 00:01 | 左岸
写的挺详细,谢谢分享  回复  更多评论
  
# re: 源代码分析之HashMap
2014-01-08 15:54 | Alex_Woo
今天断点调试,进入到.put方法时候,Key 和value都无法查看结果 modCount++;比如这一行,可以看到modCount的值,不晓得什么原因。想看Entry的值,也看不到.....什么原因呀?因为是泛型的原因吗??  回复  更多评论
  

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


网站导航:
 

<2013年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

新闻分类

新闻档案

相册

收藏夹

Java

Linux知识相关

Spring相关

云计算/Linux/虚拟化技术/

友情博客

多线程并发编程

开源技术

持久层技术相关

搜索

  •  

积分与排名

  • 积分 - 353899
  • 排名 - 155

最新评论

阅读排行榜

评论排行榜