java编程

java的HashMap源码分析

字号+ 作者:风潇潇 来源:原创 2017-03-31 12:26 我要评论( )

今天边看资料,边看源码,将Hashmap源码看了一下,这个还是很不错的哦,现在来分享一下

   当然,我看源码没看很多,但看一两个关键性的代码基本就懂了,如果想知道HashMap,各位还得去看看数据结构Hash表
  先来看一下HashMap里面的Entry,因为这个是HashMap的内部封装的数据结构,理解这个,就很好理解其他一些操作
  static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;//Entry的key
        V value;//Entry的value
        Entry<K,V> next; //下一个引用
        int hash;//此节点的hash值

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
……///这里还有很多代码
}
HashMap的内部数据结构是Entry,将HashMap所需要的相关信息存入Entry中,比如当前的key,value,此节点的下一个引用,此节点的Hash值
下图可以看到这个HashMap实际上是用一个Entry类型的数组来实现的。还有一些其他属性,比如默认FACTOR ,HashMap的大小
还要注意的是,这里的transient修饰是指,这些值不需要序列化

下面来看看HashMap的get方法

 public V get(Object key) {//传递的参数是key,
            if (key == null)//如果key为空
                return getForNullKey();//返回nullkey的值
            Entry<K,V> entry = getEntry(key);//根据Key得到entry

            return null == entry ? null : entry.getValue();//返回找到的entry
        }

这段代码很明确的思路,下面看getForNullKey的具体细节

   private V getForNullKey() {//key为null,所以不需要传递key
        if (size == 0) {//当前大小为空
            return null;
        }
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {//key为null的默认就放在第一个
            if (e.key == null)
                return e.value;//如果key为null就返回当前value
        }
        return null;
    }


再看看getEntry这个方法
    final Entry<K,V> getEntry(Object key) {//传入key,从这里也可以看出
        //hashmap的存储位置和key相关
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key); //根据key计算得到hash值,这个方法里纯粹就是个计算Hash值得
        //下面这段代码就是,根据hash得到 当前key的table数组索引,顺着Entry的next一个个找
        //代码会调用== 和equals的方法以及两个的hashcode来判断key是否相当,就是必须内容相等
        //hash值也相等,才会认为两个相等
        for (Entry<K,V> e = table[indexFor(hash, table.length)];//根据表长度和Hash值计算出数组那个索引
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }


可以看图,java里面HashMap的数据结构应该是这样的

圆圈代码Entry数据。Entry里面有next的引用。
以下是HashMap的put方法,思路也比较简单

    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {//如果是空表
            inflateTable(threshold);//建表,初始化
        }
        if (key == null)
            return putForNullKey(value);//存放key为null的value
        int hash = hash(key);//计算hash值
        int i = indexFor(hash, table.length);//根据hash值和表长度来查找索引
        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);//如果找不到就会添加进map,满了就会重建hashmap
        return null;
    }

===========更新
addEntry()方法里面还可以调用下面的方法,这才是最终添加节点的方法。这里的代码有点艺术,不知道大家体会到没有
这段代码没有作复杂的链表操作,这里就是它设计有艺术的地方。每次从hashmap里面添加新的元素,如果之前是有的,就会替换,但如果没有的话,新元素就会放在table数组的链表的第一个位置。

 void createEntry(int hash, K key, V value, int bucketIndex) {
       //取出当前的节点数据。
        Entry<K,V> e = table[bucketIndex];
      //将当前节点,value 和 添加节点的key的hash码 和key 创建一个新的节点,添加进去,存放当前的table数组的bucketIndex位置
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

Ok,关于HashMap暂时说到这,这篇文章以后还会补充一些其他的源码分析,但Hashmap的原理,这篇文章已经说出来了



转载请注明出处。

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

相关文章
网友点评
评论列表(网友评论仅供网友表达个人看法,并不表明本站同意其观点或证实其描述)