注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

0与1构筑世界,程序员创造时代

软件架构设计 Java编程

 
 
 

日志

 
 

JDK HashMap源码分析 | HashMap Source Code Analysis  

2014-08-14 20:09:19|  分类: Java |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

JDK提供了非常多的集合类,不仅使用简单,而且功能丰富,可以满足你绝大部分的需求。但在使用的时候如果不了解其实现的原理,有可能会碰到性能方面的问题,或者在一起场景下会导致系统故障。
前段时间Review代码,发现有同学在使用HashMap时存在一些问题:
1、在并发场景下使用HashMap。
2、数据量较大时,使用默认的容量。

下面主要讲解HashMap的存储结构、查询数据和插入数据的实现。

数据存储结构

采用双表结构:数组+单向链表。

JDK HashMap源码分析 - 傲风 - 0与1构筑世界,程序员创造时代
 
代码示例:
// 用于存储元素的数组
transient Entry[] table;

// Entry的构造方法中有指向下一个Entry的指针,用于构造单向链表
Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

插入数据(put方法)

put方法的代码非常清晰简单:

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    // 1、对key的hash值进行二次hash运算。
    int hash = hash(key.hashCode());

    // 2、将二次hash值与数组长度进行位与运算,得到存储的索引编号。
    int i = indexFor(hash, table.length);

    // 3、如果索引编号的位置已经有数据,历遍链表,如果有相同的key存在,用新数据覆盖并返回旧数据。
    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++;
    // 4、如果key不存在当前索引位置的链表中,在单向链表中增加新数据。
    addEntry(hash, key, value, i);
    return null;
}

生成单向链表

再来看看新增数据时(addEntry方法)是如何实现的:
PS:新增的数据始终位于链表的头部

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 1、首先根据索引编号找到当前位置的Entry。
    Entry<K,V> e = table[bucketIndex];

    // 2、用key和value生成一个新的Entry,并且将新Entry指向下一个数据的指针指向原来存储在索引编号位置的Entry。将新的Entry存储在索引编号的位置。
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

扩容

1、在插入数据时,如果存储的数据量大于或等于阈值(threshold)时,就会执行扩容(resize)操作。

  • 阈值=容量 x 阈值系数。
  • 容量默认值为16。
  • 阈值系数默认值为0.75。

2、如何扩容:按新容量创建一个数据,将旧数据中的无素一个一个地重新计算索引位置并写入(见transfer方法)。

  • 新容量=旧容量 x 2。
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            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);
        }
    }
}

获取数据(get方法)

get方法比put方法的代码更简单:

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    // 1、对key的hash值进行二次hash运算。
    int hash = hash(key.hashCode());

    // 2、将二次hash值与数组长度进行位与运算,得到存储的索引编号。历遍索引编号所在位置的单向链表,根据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;
}

注意事项

1、如果可以预估数据量,在创建HashMap实例时,设置合适的初始容量,可以减少扩容操作,提升性能。
2、将容量设置为2的n次方性能最好,如:16,32。原因:和HashMap的indexFor方法实现有关。
3、用作Key的对象须实现equals和hashCode方法。如果用String对象作Key,就不用自己实现equals和hashCode方法,因为String对象已经实现。
4、HashMap是非线程安全的,在多线程并发操作时会出现死循环原因:执行扩容操作时,将旧表中的数据插入新表时有可能导致单向链表形成闭环。


<正文结束>

文章声明


作者:傲风(aofengblog@163.com)       编写时间:2013年08月14日

网址:http://aofengblog.blog.163.com

作者保留所有权利,转载请保留文章全部内容或者说明原作者和转载地址!

  评论这张
 
阅读(1181)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017