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