Java list与set中contains()方法效率案例详解

  • list.contains(o) :遍历集合所有元素,用每个元素和传入的元素进行 equals 比较,如果集合元素有 n 个,则会比较 n 次,所以时间复杂度为 O(n) 。方法源码如下:
// ArrayList 中的方法
public boolean contains(Object o) {
      return indexOf(o) >= 0;
}

public int indexOf(Object o) {
      if (o == null) {
          for (int i = 0; i < size; i++)
              if (elementData[i]==null)
                  return i;
      } else {
          for (int i = 0; i < size; i++)
              if (o.equals(elementData[i]))
                  return i;
      }
      return -1;
}
  • set.contains(o) :set 集合是用 HashMap 实现的,其中 add 方法将每个元素当做键,以一个object 对象作为值放在 HashMap 中,而 set 的 contains 方法调用了 HashMap 的 containKey 方法,直接获取传入元素的键值对信息做判断,所以 contains 的方法复杂度为 O(1) 。方法源码如下:
// HashSet 中的方法
public boolean add(E e) {
	 // PRESENT 是一个object对象
   return map.put(e, PRESENT)==null;
}
public boolean contains(Object o) {
      return map.containsKey(o);
}

//  HashMap 中的方法
public boolean containsKey(Object key) {
  	  return getNode(hash(key), key) != null;
}

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;
}
//  getNode 方法同样也被hashMap中的get方法所调用
public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
}
  • 在进行contians判断时,全部用Set集合的contains方法,避免踩坑

到此这篇关于Java list与set中contains()方法效率案例详解的文章就介绍到这了,更多相关Java list与set中contains()方法效率内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 如何解决Mybatis--java.lang.IllegalArgumentException: Result Maps collection already contains value for X

    这两天因为项目需要整合spring.struts2.mybatis三大框架,但启动的时候总出现这个错误,困扰我好久,在网上找到的答案都不是我想要的,今天终于知道原因了. user-mapper.xml如下: <?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE mapper PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN" "http:/

  • Java集合中contains方法的效率对比分析

    最近让部门技术大佬帮忙代码review的时候,他给我指出了一个小的技术细节,就是对于集合的contains方法尽量选用Set而不是List,平时没怎么注意,仔细看了下源码,大佬就是大佬,技术细节也把握的死死的. Java集合List.Set中均有对集合中元素是否存在的判断方法contains(Object o):Map中有对key及value是否存在的判断方法containsKey(Object key)和containsValue(Object value). 1.ArrayList 在Arr

  • Java 集合的Contains和Remove方法

    一.包含与删除两种方法解析 1.boolean contains(Object o);判断集合中是否包含某个元素. package com.bjpowernode.java_learning; import java.util.*; ​ public class D85_1_ContainsMethod { public static void main(String[] args) { //创建集合 Collection c = new ArrayList(); //创建两个Integer类型

  • Java contains用法示例

    学习Demo  contains方法:用于判断list集合是否包含某个元素 containsKey方法:用于判断Map键中是否包含某个键 containsValue方法:用于判断map中是否包含某个value值 码上行动 import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /** * contains方法用于判断list集合是否包含某个元素 * con

  • Java list与set中contains()方法效率案例详解

    list.contains(o) :遍历集合所有元素,用每个元素和传入的元素进行 equals 比较,如果集合元素有 n 个,则会比较 n 次,所以时间复杂度为 O(n) .方法源码如下: // ArrayList 中的方法 public boolean contains(Object o) { return indexOf(o) >= 0; } public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size;

  • java 中createStatement()方法的实例详解

    java 中createStatement()方法的实例详解 用缺省设置创建时,ResultSet 是一种只能访问一次(one-time-through).只能向前访问(forward-only)和只读的对象.您只能访问数据一次,如果再次需要该 数据,必须重新查询数据库. 然而,并不只有这一种方式.通过设置 Statement 对象上的参数,您可以控制它产生的 ResultSet.例如: ... Class.forName(driverName); db = DriverManager.getC

  • java编程创建型设计模式工厂方法模式示例详解

    目录 1.什么是工厂方法模式? 2.案例实现 3.JDK中的工厂方法模式 1.什么是工厂方法模式? 工厂方法模式设计方案:  将披萨项目的实例化功能抽象成抽象方法,在不同的口味点餐子类中具体实现. 工厂方法模式:  定义了一个创建对象的抽象方法,由子类决定要实例化的类.工厂方法模式将对象的实例化推迟到子类. 何时使用?  不同条件下创建不用实例时.方法是让子类实现工厂接口. 2.案例实现 假如说,我们现在有这样一个需求:客户在点披萨时,可以点不同口味的披萨,比如北京的奶酪pizza.北京的胡椒p

  • Go Java算法之字符串中第一个唯一字符详解

    目录 字符串中第一个唯一字符 方法一:哈希表(Java) 方法二:队列(Go) 字符串中第一个唯一字符 给定一个字符串 s ,找到 它的第一个不重复的字符,并返回它的索引 .如果不存在,则返回 -1 . 示例 1: 输入: s = "leetcode" 输出: 0 示例 2: 输入: s = "loveleetcode" 输出: 2 示例 3: 输入: s = "aabb" 输出: -1 提示: 1 <= s.length <= 10

  • Java创建型设计模式之工厂方法模式深入详解

    目录 简单工厂模式 定义产品对象 创建工厂类 工厂使用反射 工厂方法模式 概述 应用场景 优缺点 主要角色 工厂方法模式的基本使用 创建抽象产品 创建具体产品 创建抽象工厂 创建具体工厂 客户端执行 简单工厂模式 简单工厂模式(Simple Factory Pattern)是指由一个工厂对象决定创建出哪一种产品类的实例,但是它不属于设计模式. 简单工厂适用于工厂类负责创建的对象较少的场景,且客户端只需要传入工厂类的参数,对于如何创建对象的逻辑不需要关心. 定义产品对象 public interf

  • java多线程之停止线程的方法实例代码详解

    和线程停止相关的三个方法 /* 中断线程.如果线程被wait(),join(),sleep()等方法阻塞,调用interrupt()会清除线程中断状态,并收到InterruptedException异常.另外interrupt();对于isAlive()返回false的线程不起作用. */ public void interrupt(); /* 静态方法,判断线程中断状态,并且会清除线程的中断状态.所以连续多次调用该方法,第二次之后必定返回false.另外,isAlive()用于判断线程是否处于

  • 对Python2与Python3中__bool__方法的差异详解

    学习Python面向对象编程的时候,遇到了一个很有意思的小问题.Python的__bool__方法不起作用的问题. 我反复读了我手中的教程,确认了我写的代码应该管用.可是在测试的时候却一直不通过,后来发现我实现的__bool__方法似乎并不是Python本身的接口. 代码如下: class Demo(): def __init__(self,value = 0): self.value = value def __bool__(self): return bool(self.value > 5)

  • jQuery中each方法的使用详解

    概述: each() 方法规定为每个匹配元素规定运行的函数. 返回 false 可用于及早停止循环,相当于break. 返回 true 可以结束本次循环,相当于continue. 语法: $(selector).each(function(index,element){ }) index - 选择器的 index 位置 element - 当前的元素(也可使用 "this" 选择器) $(selector).each(function(){ }) $.each(array,functi

  • Vue3中setup方法的用法详解

    目录 1.参数props 2.参数context 3. 子组件向父组件派发事件 4.优化事件派发 5.获取父组件传递的值 1.参数props props是一个对象,包含父组件传递给子组件的所有数据.在子组件中使用props进行接收.包含配置声明并传入的所有的属性的对象. 也就是说,如果你想通过props的方式输出父组件传递给子组件的值.你需要使用props进行接收配置.即props:{......}.如果你未通过Props进行接受配置,则输出的值是undefined <template> &l

  • Java ThreadLocal原理解析以及应用场景分析案例详解

    目录 ThreadLocal的定义 ThreadLocal的应用场景 ThreadLocal的demo TheadLocal的源码解析 ThreadLocal的set方法 ThreadLocal的get方法 ThreadLocalMap的结构 ThreadLocalMap的set方法 ThreadLocalMap的getEntry方法 ThreadLocal的内存泄露 如何避免内存泄露呢 应用实例 实际应用二 总结 ThreadLocal的定义 JDK对ThreadLocal的定义如下: The

随机推荐