List和Has查找数据效率对比

分享知识 传递快乐

最近研究JDK源码时发现一个很有意思的东西，记录一下所学内容，希望能帮助更多的人。

Java 集合 List、Set 中均有对集合中元素是否存在的判断方法 contains(Object o)。

Map 中有对 key 及 value 是否存在的判断方法 containsKey(Object key) 和 containsValue(Object value)。

示例：

public static void main(String[] args) {
        List arrayList = new ArrayList();
        List linkedList = new LinkedList();

        Set hashSet = new HashSet();

        Map map = new HashMap();

        // 模拟百万数据
        long begin = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            String str = i + "_test";

            arrayList.add(str);
            linkedList.add(str);

            hashSet.add(str);

            map.put(str, str);
        }
        System.out.println("模拟数据耗时:" + (System.currentTimeMillis() - begin) + " 毫秒");

        begin = System.currentTimeMillis();
        System.out.println(arrayList.contains("999999_test"));
        System.out.println("arrayList.contains 耗时: " + (System.currentTimeMillis() - begin) + " 毫秒");

        begin = System.currentTimeMillis();
        System.out.println(linkedList.contains("999999_test"));
        System.out.println("linkedList.contains 耗时: " + (System.currentTimeMillis() - begin) + " 毫秒");

        begin = System.currentTimeMillis();
        System.out.println(hashSet.contains("999999_test"));
        System.out.println("beginHashSet.contains 耗时: " + (System.currentTimeMillis() - begin) + " 毫秒");

        begin = System.currentTimeMillis();
        System.out.println(map.containsValue("999999_test"));
        System.out.println("map.contains 耗时 : " + (System.currentTimeMillis() - begin) + " 毫秒");

        begin = System.currentTimeMillis();
        System.out.println(map.containsKey("999999_test"));
        System.out.println("map.containsKey 耗时 : " + (System.currentTimeMillis() - begin) + " 毫秒");

    }      

结果：

模拟数据耗时:396 毫秒
true
arrayList.contains 耗时: 15 毫秒
true
linkedList.contains 耗时: 15 毫秒
true
beginHashSet.contains 耗时: 0 毫秒
true
map.contains 耗时 : 56 毫秒
true
map.containsKey 耗时 : 0 毫秒      

总结：

集合方法	contains	containskey	containsValue
ArrayList	O(N)	/	/
LinkedList	O(N)	/	/
HashSet	O(1)	/	/
HashMap	/	O(1)	O(N)

代码分析

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;
}      

LinkList

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

源码：

public boolean contains(Object o) {
    return indexOf(o) != -1;
}


public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}      

HashSet

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

源码：

private transient HashMap<E,Object> map;

public HashSet() {
    map = new HashMap<>();
}

public boolean contains(Object o) {
    return map.containsKey(o);
}

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

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;
}      

HashMap

HashMap 中有 containsKey 方法和 containsValue 方法，一个判断 key 是否存在，一个判断 value 是否存在。

HashMap的底层主要是基于数组和链表（散列表或者叫哈希表）来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。所以 containsKey 通过 key 的哈希值直接查找 key 是否存在，时间复杂度为 O(1)，响应的 HashSet 查找元素的时间复杂度也是 O(1)。

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;
}


public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

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;
}