课程咨询 :186 8716 1620      qq:2066486918

昆明Java培训 > 达内新闻 > Java --HashMap源码解析
  • Java --HashMap源码解析

    发布:昆明Java培训      来源:达内新闻      时间:2016-09-30

  • 本文昆明Java培训班的老师大概分析HashMap的put(),get(),resize()三个方法。

    首先让我们来看看put()方法。

    public V put(K key, V value) {

    return putVal(hash(key), key, value, false, true);

    }

    /**

    * Implements Map.put and related methods

    *

    * @param hash hash for key

    * @param key the key

    * @param value the value to put

    * @param onlyIfAbsent if true, don't change existing value

    * @param evict if false, the table is in creation mode.

    * @return previous value, or null if none

    */

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

    boolean evict) {

    Node<K,V>[] tab; Node<K,V> p; int n, i;

    if ((tab = table) == null || (n = tab.length) == 0)

    n = (tab = resize()).length;

    if ((p = tab[i = (n - 1) & hash]) == null)

    tab[i] = newNode(hash, key, value, ull);

    else {

    Node<K,V> e; K k;

    if (p.hash == hash &&

    ((k = p.key) == key || (key != ull && key.equals(k))))

    e = p;

    else if (p instanceof TreeNode)

    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

    else {

    for (int binCount = 0; ; ++binCount) {

    if ((e = p.next) == null) {

    p.next = newNode(hash, key, value, null);

    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

    treeifyBin(tab, hash);

    break;

    }

    if (e.hash == hash &&

    ((k = e.key) == key || (key != null && key.equals(k))))

    break;

    p = e;

    }

    }

    if (e != null) { // existing mapping for key

    V oldValue = e.value;

    if (!onlyIfAbsent || oldValue == null)

    e.value = value;

    afterNodeAccess(e);

    return oldValue;

    }

    }

    ++modCount;

    if (++size > threshold)

    resize();

    afterNodeInsertion(evict);

    return null;

    }

    1.首先通过hash(key)计算key的hash值

    putVal(hash(key), key, value, false, true)

    2.由于hashMap实际存储数据的就是table数组,那么首先需要判断table数组是否已经被初始化了,如果没有初始化,那么调用resize()方法对table进行初始化

    if ((tab = table) == null || (n = tab.length) == 0)

    n = (tab = resize()).length;

    3.通过hash与(n-1)进行与运算得出数组的索引,根table[索引]判断是否为null,如果为null那么直接存入该位置。

    if ((p = tab[i = (n - 1) & hash]) == null)

    tab[i] = newNode(hash, key, value, ull);

    4.如果table[索引]不为null,那么说明位置发生了碰撞,需要继续进行判断

    5.如果判断table[索引]位置p上的p.key=key&&p.hash=hash,那么就会对value进行替换,也就是保证key唯一。

    6.如果不满足5的条件,那么会判断table[索引]位置p是二叉树,那么会调用TreeNode.putTreeVal()去进行对二叉树节点的插入。

    else if (p instanceof TreeNode)

    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

    7.如果不满足5,6的条件,那么会使用链表来插入该节点:循环寻找p.next直到找到一个位置为null那么进行插入。

    for (int binCount = 0; ; ++binCount) {

    if ((e = p.next) == null) {

    p.next = newNode(hash, key, value, null);

    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

    treeifyBin(tab, hash);

    break;

    }

    if (e.hash == hash &&

    ((k = e.key) == key || (key != null && key.equals(k))))

    break;

    p = e;

    }

    8.上述5,6,7三步中,只要发现了p.key=key&&p.hash=hash,那么就会进行value替换,将oldValue替换为newValue。

    if (e != null) { // existing mapping for key

    V oldValue = e.value;

    if (!onlyIfAbsent || oldValue == null)

    e.value = value;

    afterNodeAccess(e);

    return oldValue;

    }

    9.进行计数+1,并且判断当前已存数量是否大于table[]的2/3,如果大于那么使用resize()对table进行扩充。

    10.至此整个put()完成。

    再来让我们看看get()方法。

    public V get(Object key) {

    Node<K,V> e;

    return (e = getNode(hash(key), key)) == ull ? null : e.value;

    }

    /**

    * Implements Map.get and related methods

    *

    * @param hash hash for key

    * @param key the key

    * @return the node, or null if none

    */

    final Node<K,V> getNode(int hash, Object key) {

    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

    if ((tab = table) != null && (n = tab.length) > 0 &&

    (first = tab[(n - 1) & hash]) != null) {

    if (first.hash == hash && // always check first node

    ((k = first.key) == key || (key != null && key.equals(k))))

    return first;

    if ((e = first.next) != null) {

    if (first instanceof TreeNode)

    return ((TreeNode<K,V>)first).getTreeNode(hash, key);

    do {

    if (e.hash == hash &&

    ((k = e.key) == key || (key != null && key.equals(k))))

    return e;

    } while ((e = e.next) != null);

    }

    }

    return null;

    }

    1.首先判断table[]是否为空,通过hash计算索引判断table[索引]是否为空,如果任意一项为空那么直接return null。

    2.判断table[索引]的hash与key是否都与查找的相同,如果hash与key都相同,那么直接返回table[索引]。

    if (first.hash == hash && // always check first node

    ((k = first.key) == key || (key != null && key.equals(k))))

    return first;

    3.如果不满足条件2,那么判断table[索引]的next是否为空,如果为空则return ull。

    4.如果table[索引]的next不为空,那么判断是否为二叉树,如果是二叉树直接使用getTreeNode()方法查找。

    if (first instanceof TreeNode)

    return ((TreeNode<K,V>)first).getTreeNode(hash, key);

    5.如果不是二叉树,那么直接使用链表的方式查找。

    do {

    if (e.hash == hash &&

    ((k = e.key) == key || (key != null && key.equals(k))))

    return e;

    } while ((e = e.next) != null);

    6.至此完成整个get()方法。

    学Java开发就到昆明达内Java培训班!了解详情请登陆昆明达内Java培训官网(km.Java.tedu.cn)!

    推荐文章

上一篇:java程序员:解析Java泛型

下一篇:JAVA邮件发送

最新开班日期  |  更多

Java--零基础全日制班

Java--零基础全日制班

开班日期:12/29

Java--零基础业余班

Java--零基础业余班

开班日期:12/29

Java--周末提升班

Java--周末提升班

开班日期:12/29

Java--零基础周末班

Java--零基础周末班

开班日期:12/29

  • 网址:http://km .java.tedu.cn      地址:昆明市官渡区春城路62号证券大厦附楼6楼
  • 课程培训电话:186 8716 1620      qq:2066486918    全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56