专栏首页人生得意须尽欢测试HashMap继承的类与实现的接口
原创

测试HashMap继承的类与实现的接口

/** 
 * The table, resized as necessary. Length MUST Always be a power of two. 
 */  
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;  
    ……  
}  

  可以看出,Entry就是数组中的元素,每个 Map.Entry 其实就是一个key-value对,它持有一个指向下一个元素的引用,这就构成了链表。

public V put(K key, V value) {  
    // HashMap允许存放null键和null值。  
    // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。  
    if (key == null)  
        return putForNullKey(value);  
    // 根据key的keyCode重新计算hash值。  
    int hash = hash(key.hashCode());  
    // 搜索指定hash值在对应table中的索引。  
    int i = indexFor(hash, table.length);  
    // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。  
    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;  
        }  
    }  
    // 如果i索引处的Entry为null,表明此处还没有Entry。  
    // modCount记录HashMap中修改结构的次数
    modCount++;  
    // 将key、value添加到i索引处。  
    addEntry(hash, key, value, i);  
    return null;  
} 

  从上面的源代码中可以看出:当我们往HashMap中put元素的时候,先根据key的hashCode重新计算hash值,根据hash值得到这个元素在数组中的位置(即下标),如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,刚刚加入的Entry在链头,最先加入的在链尾(这一点从addEntry(hash, key, value, i)函数可以看出来,把新加入的Entry对象放在数组table[i]位置,此Entry的next值指向以前的Entry)。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。 简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度依然为O(1),因为最新的Entry会插入链表头部,只需要简单改变引用链即可,而对于查找操作来讲,此时就需要遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++接口继承与实现继承的区别和选择

    《Effective C++》条款三十四:区分接口继承和实现继承中介绍的比较啰嗦,概括地说需要理解三点: (1)纯虚函数只提供接口继承,但可以被实现; ...

    Dabelv
  • PHP接口继承及接口多继承原理与实现方法详解

    本文实例讲述了PHP接口继承及接口多继承原理与实现方法。分享给大家供大家参考,具体如下: 在PHP的接口中,接口可以继承接口。虽然PHP类只能继承一个父类(单继...

    用户2323866
  • Java 继承Thread类和实现Runnable接口的区别

    ava中线程的创建有两种方式: 1.  通过继承Thread类,重写Thread的run()方法,将线程运行的逻辑放在其中 2.  通过实现Runnabl...

    xiangzhihong
  • Java中实现多线程继承Thread类与实现Runnable接口的区别

    1. 通过继承Thread类,重写Thread的run()方法,将线程运行的逻辑放在其中

    孙晨c
  • Java基础10 接口的继承与抽象类

    在实施接口中,我们利用interface语法,将interface从类定义中独立出来,构成一个主体。interface为类提供了接口规范。 在继承中,我们为了提...

    Vamei
  • Java基础10 接口的继承与抽象类

    在实施接口中,我们利用interface语法,将interface从类定义中独立出来,构成一个主体。interface为类提供了接口规范。

    Java团长
  • Java 继承泛型类和实现泛型接口

    用户2965768
  • 继承、接口与多态的相关问题

    继承:通过继承实现代码复用。Java中所有的类都是通过直接或间接地继程java.lang.Object类得到的。继承而得到的类称为子类,被继承的类称为父类。子类...

    哲洛不闹
  • JavaScript实现java中的|接口|继承|抽象类|继承|多态|对象|工厂模式|重写|重载|

    //定一个接口方法, var Interface = function(name,methods){ if(arguments.length != 2){ ...

    前朝楚水
  • Java运行时多态性:继承和接口的实现

    image.png Java是面向对象的语言,而运行时多态性是面向对象程序设计代码重用的一个最强大机制,动态性的概念也可以被说成“一个接口,多个方法”。Ja...

    java达人
  • es6类和继承的实现原理

    javascript使用的是原型式继承,我们可以通过原型的特性实现类的继承, es6为我们提供了像面向对象继承一样的语法糖。

    ConardLi
  • 实现接口的契约测试

    在当前微服务和前后端分离大行其道的行业背景下,越来越多的团队采用了前后端分离和微服务的架构风格。 A团队开发某服务并提供对应API服务,B团队是A团队的使用者调...

    赵云龙龙
  • JavaSE 基础学习之三 —— Java 的继承与接口

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/...

    剑影啸清寒
  • C++实现不能被继承的类——终结类

    C++如何实现不能被继承的类,即终结类。Java中有final关键字修饰,C#中有sealed关键字修饰,而C++目前还没有类似的关键字来修饰类实现终结类,需编...

    Dabelv
  • 第五节:详细讲解Java中的接口与继承

    大家好,我是 Vic,今天给大家带来详细讲解Java中的接口与继承的概述,希望你们喜欢

    达达前端
  • 关于Java中的对象、类、抽象类、接口、继承之间的联系

    寒假学习JavaSE基础,其中的概念属实比较多,关联性也比较大,再次将相关的知识点复习一些,并理顺其中的关系。

    xbhog
  • 接口的编写与测试

    https://wap.ztestin.com/site/register?usercode=FAAAQwMQGAAXAwQBA3QhExcDHAQDPjVaA...

    小老鼠
  • Android多线程:继承Thread类 & 实现Runnable接口 使用解析(含实例教程)

    很多情况下,开发者会选择一种更加方便的方法去创建线程:**匿名类**

    Carson.Ho
  • HashSet 源码分析

    HashSet 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,所以在...

    lwen

扫码关注云+社区

领取腾讯云代金券