我們經常使用的集合如ArrayList,LinkedList，Vector, **你在調用contains()方法的時候, 或者是你在根據對象移除元素 remove(Object o) 你知道他們是如何判斷集合中的元素是否 是相等的嗎**? 接下來我們跟著源碼去詳細探究一下 數據數據結構不同判斷的依據就不同,我們先來看一下List類的判斷依據.
先簡單的了解一下 List類 : 有序，可以有重復元素。
ArrayList 底層是一個對象數組 PRivate transient Object[] elementData; LinkedList 屬于鏈式數據結構,底層用的是一個Node類的節點,包括指針域和數據域.
private static class Node { E item; Node next; Node prev;
Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; }}ArrayList LinkedList他們都是線程不同步的 Vector非常類似ArrayList，但是Vector是同步的。, ArrayList LinkedList多線程訪問會拋出 ConcurrentModificationException。如果想使他們線程同步的可以使用 Collections.synchronizedList 方法將該集合“包裝”起來
回歸正題
我們想知道他們如何判斷集合元素是否相等,我們應該想到的是contains(Object o)方法,接下來我們看一下contains(Object o)方法
public boolean contains(Object o) { return indexOf(o) >= 0; }他的方法內部調用了indexOf(o)這個方法,我們繼續追蹤看一下indexOf(o)方法
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; }看到這里我們應該能明白了 先判斷要查找的元素是否為空,不為空的話就調用equals方法.由此我們得到一個結論 List類中判斷元素是否相等依賴的是equals方法.
set類 : 無序，不允許重復
HashSet : 此實現不是同步的 我們知道HashSet它不允許出現重復元素,他是如何保證元素唯一的呢,我們應該首先想到的是看他的add()方法 如下
public boolean add(E e) { return map.put(e, PRESENT)==null; } 這里出現了一個map我們找找看看他是什么
我們在上面看到了他的定義
private transient HashMap<E,Object> map;現在我們知道了HashSet的內部其實是一個HashMap來維護的,眾所周知HashMap的鍵是不允許有相同的,不用說HashMap的鍵就是HashSet的值,接下來我們只需要知道HashMap的鍵是如何保證唯一的就行了
我們就要追蹤HashMap的添加元素方法 put(K key, V value)
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordaccess(this); return oldValue; } }雖然有點麻煩我們只需要仔細看看 一定可以看明白 抓住最重要的一句
e.hash == hash && ((k = e.key) == key || key.equals(k))現在我們也知道了HashSet 和HaspMap 保證元素唯一的辦法是 先比較兩個元素的哈希值,如果哈希值相等,在比較元素的地址是否相同,或者調用兩個元素的equals方法如果哈希值不同,就根本不用在比較了.
新聞熱點
疑難解答
