最近让部门技术大佬帮忙代码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.HashSetHashSet中元素以Key的形式存于HashMap中,判断元素是否存在即是判断对应Map中key是否存在。
HashSet: private transient HashMap<E,Object> map; //将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会被序列化。 /** * Constructs a new, empty set; the backing <tt>HashMap</tt> 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.HashMapHashMap中有两个contains方法,一个判断key是否存在,一个判断value是否存在。
HashMap的底层主要是基于数组和链表(散列表或者叫哈希表)来实现的,它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。所以containsKey通过key的哈希值直接查找key是否存在,时间复杂度为O(1),响应的HashSet查找元素的时间复杂度也是O(1)。
对于containsValue方法判断map中是否存在value的判断,其方法为将map中的Node数组进行遍历,然后判断是否存在。
transient Node<K,V>[] table;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;}public boolean containsValue(Object value) { Node<K,V>[] tab; V v; if ((tab = table) != null && size > 0) { for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) { if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false;} 4.总结 集合各方法的时间复杂度containscontainskeycontainsValueArrayListO(N)HashSetO(1)HashKeyO(1)O(N)对于这种技术细节需要平时注意和积累,不断学习和记录,应用于实际开发中,不断提高运行效率。后续也会将这些技术细节记录下来,在日常开发中加以运用。