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

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

最近让部门技术大佬帮忙代码review的时候，他给我指出了一个小的技术细节，就是对于集合的contains方法尽量选用Set而不是List，平时没怎么注意，仔细看了下源码，大佬就是大佬，技术细节也把握的死死的。

java集合List、Set中均有对集合中元素是否存在的判断方法contains(Object o)；Map中有对key及value是否存在的判断方法containsKey(Object key)和containsValue(Object value)。

1.ArrayList

在ArrayList中contains方法通过遍历list中的元素，利用==或equals来判断是否存在目标元素，复杂度为O(N)

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;

}

2.HashSet

HashSet中元素以Key的形式存于HashMap中，判断元素是否存在即是判断对应Map中key是否存在。

HashSet:

private transient HashMap map; //将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会被序列化。

/**

* Constructs a new, empty set; the backing HashMap instance has

* default initial capacity (16) and load factor (0.75).

*/

public HashSet() {

map = new HashMap<>();

}

public boolean contains(Object o) {

return map.containsKey(o);

}

3.HashMap

HashMap中有两个contains方法，一个判断key是否存在，一个判断value是否存在。

HashMap的底层主要是基于数组和链表（散列表或者叫哈希表）来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。

所以containsKey通过key的哈希值直接查找key是否存在，时间复杂度为O(1)，响应的HashSet查找元素的时间复杂度也是O(1)。

对于containsValue方法判断map中是否存在value的判断，其方法为将map中的Node数组进行遍历，然后判断是否存在。

transient Node[] table;

public boolean containsKey(Object key) {

return getNode(hash(key), key) != null;

}

final Node getNode(int hash, Object key) {

Node[] tab; Node 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)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;

}

public boolean containsValue(Object value) {

Node[] tab; V v;

if ((tab = table) != null && size > 0) {

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

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

if ((v = e.value) == value ||

(value != null && value.equals(v)))

return true;

}

}

}

return false;

}

4.总结

集合各方法的时间复杂度

contains

containskey

aOydpZTxn containsValue

ArrayList

O(N)

HashSet

O(1)

HashKey

O(1)

O(N)

对于这种技术细节需要平时注意和积累，不断学习和记录，应用于实际开发中，不断提高运行效率。后续也会将这些技术细节记录下来，在日常开发中加以运用。

补充：ArrayList的contains方法的效率果然不高

看代码吧~

之前做的一个项目，数据库抽出了40多万条数据，然后从csv文件抽出了大概也是40多万条数据，进行对比分析 之前代码如下：

List keys = new ArrayList();

int isize = msTaiyousr.size();

for (int i=0;i

Map msyaiyousr = msTaiyousr.get(i);

String id = (String) msyaiyousr.get("taiyousrid");

String usrtorokukbn = (String) msyaiyousr.get("usrtorokukbn");

keys.add(usrtorokukbn+":"+id);

}

int jsize = wkTaiyousr.size();

for (int j=0;j

Map wktaiyousr = wkTaiyousr.get(j);

String id = (String) wktaiyousr.get("taiyousrid");

String usrtorokukbn = (String) wktaiyousr.get("usrtorokukbn");

if (keys.contains(usrtorokukbn+":"+id)) {

updateList.add(wktaiyousr);

} else {

insertList.add(wktaiyousr);

}

}

由于 第二个for循环使用了 ArrayList的contains方法，跑完第二个for循环使用了 12分钟左右，我的个天，第一个循环不到1秒。然后使用了 HashSet 代替 ArrayList 代码如下：

Set keys = new HashSet();

int isize = msTaiyousr.size();

for (int i=0;i

Map msyaiyousr = msTaiyousr.get(i);

String id = (String) msyaiyousr.get("taiyousrid");

String usrtorokukbn = (String) msyaiyousr.get("usrtorokukbn"http://);

keys.add(usrtorokukbn+":"+id);

}

int jsize = wkTaiyousr.size();

for (int j=0;j

Map wktaiyousr = wkTaiyousr.get(j);

String id = (String) wktaiyousr.get("taiyousrid");

String usrtorokukbn = (String) wktaiyousr.get("usrtorokukbn");

if (keys.contains(usrtorokukbn+":"+id)) {

updateList.add(wktaiyousr);

} else {

insertList.add(wktaiyousr);

}

}

结果不到1秒，两个for循环瞬间跑完。果然大数据的时候还是不要用到ArrayList的contains方法，改用HashSet的吧。

Map msyaiyousr = msTaiyousr.get(i);

String id = (String) msyaiyousr.get("taiyousrid");

String usrtorokukbn = (String) msyaiyousr.get("usrtorokukbn");

keys.add(usrtorokukbn+":"+id);

}

int jsize = wkTaiyousr.size();

for (int j=0;j

Map wktaiyousr = wkTaiyousr.get(j);

String id = (String) wktaiyousr.get("taiyousrid");

String usrtorokukbn = (String) wktaiyousr.get("usrtorokukbn");

if (keys.contains(usrtorokukbn+":"+id)) {

updateList.add(wktaiyousr);

} else {

insertList.add(wktaiyousr);

}

}

由于 第二个for循环使用了 ArrayList的contains方法，跑完第二个for循环使用了 12分钟左右，我的个天，第一个循环不到1秒。然后使用了 HashSet 代替 ArrayList 代码如下：

Set keys = new HashSet();

int isize = msTaiyousr.size();

for (int i=0;i

Map msyaiyousr = msTaiyousr.get(i);

String id = (String) msyaiyousr.get("taiyousrid");

String usrtorokukbn = (String) msyaiyousr.get("usrtorokukbn"http://);

keys.add(usrtorokukbn+":"+id);

}

int jsize = wkTaiyousr.size();

for (int j=0;j

Map wktaiyousr = wkTaiyousr.get(j);

String id = (String) wktaiyousr.get("taiyousrid");

String usrtorokukbn = (String) wktaiyousr.get("usrtorokukbn");

if (keys.contains(usrtorokukbn+":"+id)) {

updateList.add(wktaiyousr);

} else {

insertList.add(wktaiyousr);

}

}

结果不到1秒，两个for循环瞬间跑完。果然大数据的时候还是不要用到ArrayList的contains方法，改用HashSet的吧。

Map wktaiyousr = wkTaiyousr.get(j);

String id = (String) wktaiyousr.get("taiyousrid");

String usrtorokukbn = (String) wktaiyousr.get("usrtorokukbn");

if (keys.contains(usrtorokukbn+":"+id)) {

updateList.add(wktaiyousr);

} else {

insertList.add(wktaiyousr);

}

}

由于 第二个for循环使用了 ArrayList的contains方法，跑完第二个for循环使用了 12分钟左右，我的个天，第一个循环不到1秒。然后使用了 HashSet 代替 ArrayList 代码如下：

Set keys = new HashSet();

int isize = msTaiyousr.size();

for (int i=0;i

Map msyaiyousr = msTaiyousr.get(i);

String id = (String) msyaiyousr.get("taiyousrid");

String usrtorokukbn = (String) msyaiyousr.get("usrtorokukbn"http://);

keys.add(usrtorokukbn+":"+id);

}

int jsize = wkTaiyousr.size();

for (int j=0;j

Map wktaiyousr = wkTaiyousr.get(j);

String id = (String) wktaiyousr.get("taiyousrid");

String usrtorokukbn = (String) wktaiyousr.get("usrtorokukbn");

if (keys.contains(usrtorokukbn+":"+id)) {

updateList.add(wktaiyousr);

} else {

insertList.add(wktaiyousr);

}

}

结果不到1秒，两个for循环瞬间跑完。果然大数据的时候还是不要用到ArrayList的contains方法，改用HashSet的吧。

Map msyaiyousr = msTaiyousr.get(i);

String id = (String) msyaiyousr.get("taiyousrid");

String usrtorokukbn = (String) msyaiyousr.get("usrtorokukbn"http://);

keys.add(usrtorokukbn+":"+id);

}

int jsize = wkTaiyousr.size();

for (int j=0;j

Map wktaiyousr = wkTaiyousr.get(j);

String id = (String) wktaiyousr.get("taiyousrid");

String usrtorokukbn = (String) wktaiyousr.get("usrtorokukbn");

if (keys.contains(usrtorokukbn+":"+id)) {

updateList.add(wktaiyousr);

} else {

insertList.add(wktaiyousr);

}

}

结果不到1秒，两个for循环瞬间跑完。果然大数据的时候还是不要用到ArrayList的contains方法，改用HashSet的吧。

Map wktaiyousr = wkTaiyousr.get(j);

String id = (String) wktaiyousr.get("taiyousrid");

String usrtorokukbn = (String) wktaiyousr.get("usrtorokukbn");

if (keys.contains(usrtorokukbn+":"+id)) {

updateList.add(wktaiyousr);

} else {

insertList.add(wktaiyousr);

}

}

结果不到1秒，两个for循环瞬间跑完。果然大数据的时候还是不要用到ArrayList的contains方法，改用HashSet的吧。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。