java 中HashMap、HashSet、TreeMap、TreeSet判断元素相同的几种方法比较

1.1     HashMap

       先来看一下HashMap里面是怎么存放元素的。Map里面存放的每一个元素都是key-value这样的键值对，而且都是通过put方法进行添加的，而且相同的key在Map中只会有一个与之关联的value存在。put方法在Map中的定义如下。

  V put(K key, V value);

       它用来存放key-value这样的一个键值对，返回值是key在Map中存放的旧value，如果之前不存在则返回null。HashMap的put方法是这样实现的。

 public V put(K key, V value) {

    if (key == null)

      return putForNullKey(value);

    int hash = hash(key);

    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;

  }

       从上我们可以看到在添加对应的key-value这样的组合时，如果原本已经存在对应的key，则直接改变对应的value，并返回旧的value，而在判断key是否存在的时候是先比较key的hashCode，再比较相等或equals的。这里可能我们还看不出来，直接从上面代码来看是比较的对应Map.Entry的hashCode和key的hashCode，而实际上在后面我们可以看到Map.Entry的hashCode其实就是其存放key的hashCode。而如果对应的key原本不存在的话将调用addEntry将对应的key-value添加到Map中。addEntry传递的参数hash就是对应key的hashCode。接着我们来看一下addEntry的方法定义。

 void addEntry(int hash, K key, V value, int bucketIndex) {

    if ((size >= threshold) && (null != table[bucketIndex])) {

      resize(2 * table.length);

      hash = (null != key) ? hash(key) : 0;

      bucketIndex = indexFor(hash, table.length);

    }

 

    createEntry(hash, key, value, bucketIndex);

  }

 

  void createEntry(int hash, K key, V value, int bucketIndex) {

    Entry<K,V> e = table[bucketIndex];

    table[bucketIndex] = new Entry<>(hash, key, value, e);

    size++;

  }

        addEntry的核心是调用createEntry来建立表示对应key-value的Map.Entry对象并进行存放，很显然上述table是一个Map.Entry的数组。Map.Entry中用一个属性hash保存了对应key的hashCode。还是来看一下上面调用的Map.Entry的构造方法吧。

   Entry(int h, K k, V v, Entry<K,V> n) {

      value = v;

      next = n;

      key = k;

      hash = h;

    }

       很显然，其内部保存了对应key、value和key对应的hashCode。

       了解了HashMap是怎样存放元素的以后，我们再来看HashMap是怎样存放元素的就比较简单了。HashMap中判断元素是否相同主要有两个方法，一个是判断key是否相同，一个是判断value是否相同。其实在介绍HashMap是怎样存放元素时我们已经介绍了HashMap是怎样判断元素Key是否相同的，那就是首先得hashCode相同，其次是key相等或equals。Map中判断key是否相同是通过containsKey()方法进行的，其在HashMap中的实现如下。

 public boolean containsKey(Object key) {

    return getEntry(key) != null;

  }

 

  final Entry<K,V> getEntry(Object key) {

    int hash = (key == null) ? 0 : 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 != null && key.equals(k))))

        return e;

    }

    return null;

  }

       很明显，它就是先判断key的hashCode是否相同，再判断key是否相等或equals的。

       Map中用来判断value是否相同是通过containsValue方法来判断的，其在HashMap中的实现如下。

  public boolean containsValue(Object value) {

    if (value == null)

      return containsNullValue();

 

    Entry[] tab = table;

    for (int i = 0; i < tab.length ; i++)

      for (Entry e = tab[i] ; e != null ; e = e.next)

        if (value.equals(e.value))

          return true;

    return false;

  }

       很显然，对于非null形式的value是通过value的equals来进行判断的，而null形式的只要相等即可，即保存的元素中有value为null即可。

1.2     HashSet

       知道了HashMap是如何存放元素和判断元素是否相同的方式以后，我们再来看HashSet是如何判断元素是否相同就比较简单了。

       HashSet中的元素其实是通过HashMap来保存的，在每个HashSet对象中都持有一个对应的HashMap对象的引用，在对HashSet进行元素的添加、删除等操作时都是通过其持有的HashMap来进行的。在保存元素时其会将对应的元素作为持有的HashMap的key来进行保存，对应的value是一个常量Object，所以其在保存的时候判断元素是否相同所使用的是HashMap判断key是否相同的逻辑。其在判断是否包含某一元素时也是调用了所持有的HashMap的containsKey方法来进行判断的。

 public boolean contains(Object o) {

    returnmap.containsKey(o);

  }

       有兴趣的朋友可以去看一下HashSet的源码。 

1.3     TreeMap

       TreeMap中存放的元素都是有序的，而且是根据key进行排序的。TreeMap在对存放的元素进行排序时有两种方式，一种是通过自身持有的Comparator进行排序，另一种是通过实现了Comparable接口的key进行排序，优先使用第一种方式，当持有的Comparator（默认为null）为null时则采用第二种方式。TreeMap好几个构造方法，可以通过其构造方法来初始化其持有的Comparator。我们还是先来看一下TreeMap是如何保存元素的，其put方法实现如下。

  public V put(K key, V value) {

    Entry<K,V> t = root;

    if (t == null) {

      compare(key, key); // type (and possibly null) check

 

      root = new Entry<>(key, value, null);

      size = 1;

      modCount++;

      return null;

    }

    int cmp;

    Entry<K,V> parent;

    // split comparator and comparable paths

    Comparator<? super K> cpr = comparator;

    if (cpr != null) {

      do {

        parent = t;

        cmp = cpr.compare(key, t.key);

        if (cmp < 0)

          t = t.left;

        elseif (cmp > 0)

          t = t.right;

        else

          return t.setValue(value);

      } while (t != null);

    }

    else {

      if (key == null)

        thrownew NullPointerException();

      Comparable<? super K> k = (Comparable<? super K>) key;

      do {

        parent = t;

        cmp = k.compareTo(t.key);

        if (cmp < 0)

          t = t.left;

        elseif (cmp > 0)

          t = t.right;

        else

          return t.setValue(value);

      } while (t != null);

    }

    Entry<K,V> e = new Entry<>(key, value, parent);

    if (cmp < 0)

      parent.left = e;

    else

      parent.right = e;

    fixAfterInsertion(e);

    size++;

    modCount++;

    return null;

  }

        从上述实现我们可以看到，第一个元素将直接存进去。之后的元素分两种情况进行，一种是持有的Comparator不为空的情况，一种是持有的Comparator为空的情况。Comparator不为空的时候将通过Comparator来确定存放元素的位置，其中有一点很重要的是当通过Comparator比较了现有元素的key与当前存放元素的key的结果为0时，将认为当前存放的元素key在原有Map中已经存在，然后改变原有的key对应的value为新value，然后就直接返回了旧value。当持有的Comparator为空时将通过实现了Comparable接口的key的compareTo方法来决定元素存放的位置，有一点与使用Comparator类似的地方是当原有key作为Comparable与新存入的key进行比较的结果为0时将认为新存入的key在原Map中已经存在，将直接改变对应的原key的value，而不再新存入key-value对。实际上其判断元素是否存在的containsKey方法的主要实现逻辑也是类似的，具体实现如下。

 public boolean containsKey(Object key) {

    return getEntry(key) != null;

  }

 

  final Entry<K,V> getEntry(Object key) {

    // Offload comparator-based version for sake of performance

    if (comparator != null)

      return getEntryUsingComparator(key);

    if (key == null)

      thrownew NullPointerException();

    Comparable<? super K> k = (Comparable<? super K>) key;

    Entry<K,V> p = root;

    while (p != null) {

      int cmp = k.compareTo(p.key);

      if (cmp < 0)

        p = p.left;

      elseif (cmp > 0)

        p = p.right;

      else

        return p;

    }

    return null;

  }

        因为TreeMap判断元素是否存在的逻辑是通过判断Comparator或Comparable进行比较后的结果是否为0，所以我们在使用TreeMap希望实现某种类似于元素equals的逻辑时要特别小心。

       TreeMap的containsValue的逻辑还是判断的对应的value是否equals，与HashMap类似，有兴趣的朋友可以查看一下TreeMap的源码。

1.4     TreeSet

       TreeSet也是的Set的一种实现，其存放的元素是不重复的，而且是有序的，默认情况下所存放的元素必须实现Comparable接口，因为默认情况下将把元素当做Comparable对象进行比较。TreeSet也是可以通过Comparator来比较其中存放的元素的，这可以在构造TreeSet的时候通过传入一个Comparator对象或一个持有Comparator对象的TreeMap来实现。TreeSet的实现与HashSet的实现类似，其内部也持有了一个Map的引用，只不过它引用的不是HashMap，而是TreeMap。TreeSet中元素的新增、删除等操作都是由其持有的TreeMap来实现的，所以与HashSet类似，TreeSet中判断元素是否相同的方式与TreeMap是一致的，也是通过Comparator或Comparable来判定的，而不是传统的equals方法。有兴趣的朋友可以去查看一下TreeSet的源码。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# HashMap  # HashSet  # TreeMap  # TreeSet判断元素相同  # HashMap、HashSet、TreeMap、TreeSet判断元素相同方法比较  # java判断元素是否相同  # Java HashSet添加 遍历元素源码分析  # JAVA HashSet和TreeSet 保证存入元素不会重复的操作  # Java 8 对 HashSet 元素进行排序的操作方法  # 都是  # 是怎样  # 方法来  # 为空  # 有兴趣  # 可以看到  # 的是  # 看一下  # 是一个  # 是否存在  # 两种  # 可以通过  # 再来  # 不存在  # 在对  # 来实现  # 先来  # 时将  # 键值  # 存了 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： Laravel如何使用集合（Collections）进行数据处理_Laravel Collection常用方法与技巧  公司网站制作需要多少钱,找人做公司网站需要多少钱？  Laravel如何与Inertia.js和Vue/React构建现代单页应用  Python文件流缓冲机制_IO性能解析【教程】  如何在IIS中新建站点并配置端口与物理路径？  Laravel如何优化应用性能？（缓存和优化命令）  Firefox Developer Edition开发者版本入口  如何快速搭建高效服务器建站系统？  千问怎样用提示词获取健康建议_千问健康类提示词注意事项【指南】  Laravel如何实现事件和监听器？（Event & Listener实战）  C#如何调用原生C++ COM对象详解  Chrome浏览器标签页分组怎么用_谷歌浏览器整理标签页技巧【效率】  Laravel如何使用Facades（门面）及其工作原理_Laravel门面模式与底层机制  Laravel软删除怎么实现_Laravel Eloquent SoftDeletes功能使用教程  Python3.6正式版新特性预览  如何用虚拟主机快速搭建网站？详细步骤解析  Laravel怎么实现验证码功能_Laravel集成验证码库防止机器人注册  Laravel如何配置Horizon来管理队列？（安装和使用）  如何在IIS中配置站点IP、端口及主机头？  Windows10怎样连接蓝牙设备_Windows10蓝牙连接步骤【教程】  Laravel如何使用Spatie Media Library_Laravel图片上传管理与缩略图生成【步骤】  网站制作价目表怎么做,珍爱网婚介费用多少？  如何用ChatGPT准备面试 模拟面试问答与职场话术练习教程  魔方云NAT建站如何实现端口转发？  VIVO手机上del键无效OnKeyListener不响应的原因及解决方法  免费制作统计图的网站有哪些,如何看待现如今年轻人买房难的情况？  Python自然语言搜索引擎项目教程_倒排索引查询优化案例  Win11怎么关闭专注助手 Win11关闭免打扰模式设置【操作】  如何快速搭建自助建站会员专属系统？  html文件怎么打开证书错误_https协议的html打开提示不安全【指南】  企业在线网站设计制作流程,想建设一个属于自己的企业网站，该如何去做？  详解jQuery停止动画——stop()方法的使用  JS弹性运动实现方法分析  简单实现Android验证码  如何在阿里云虚拟服务器快速搭建网站？  香港服务器WordPress建站指南：SEO优化与高效部署策略  Laravel怎么防止CSRF攻击_Laravel CSRF保护中间件原理与实践  Laravel如何实现多级无限分类_Laravel递归模型关联与树状数据输出【方法】  济南网站建设制作公司,室内设计网站一般都有哪些功能？  QQ浏览器网页版登录入口 个人中心在线进入  ,怎么在广州志愿者网站注册？  哪家制作企业网站好,开办像阿里巴巴那样的网络公司和网站要怎么做？  Laravel怎么解决跨域问题_Laravel配置CORS跨域访问  Win11搜索栏无法输入_解决Win11开始菜单搜索没反应问题【技巧】  Windows10电脑怎么查看硬盘通电时间_Win10使用工具检测磁盘健康  美食网站链接制作教程视频,哪个教做美食的网站比较专业点？  黑客入侵网站服务器的常见手法有哪些？  详解Android——蓝牙技术 带你实现终端间数据传输  Claude怎样写约束型提示词_Claude约束提示词写法【教程】  Laravel怎么配置自定义表前缀_Laravel数据库迁移与Eloquent表名映射【步骤】