2017-02-17 83 views
2

目前,我正在學習「隊列」接口的屬性也碰到了下面的語句在Java Documentation比較「隊列」中的Java對象

隊列的實現一般並不定義基於元素的方法 equals和hashCode而是繼承身份從Object類基於 版本,因爲基於元素的平等是不 與相同的元素,但不同的 的排序屬性的隊列始終明確。

我不完全確定這個段落的意思,就如何比較相同實現類型和不同實現類型的「隊列」對象而言。有人可以向我解釋一下比較「隊列」對象的方法嗎?

回答

3

我覺得文檔指出Queue實現通常不會覆蓋默認從Object類的隊列中的元素排序equals方法可以爲每個執行有很大的不同,因此他們在一個通用的方法比較可能會出現意想不到的結果。

如果要根據自己的條件比較隊列對象,可以實現Comparator<Queue>類(具體爲compare方法)。然後,您可以使用此方法來直接比較兩個隊列,或者用它來排序隊列集合等

javadoc for Comparator

1

隊列的默認實現通過引用進行比較(在Object類中默認實現) 。因此,如果要比較隊列,則必須覆蓋equals,或者可以將隊列轉換爲其他集合(例如,列表或集合或數組),然後比較這些集合,從實現的角度來看會更容易一些。

這樣做的原因行爲(不重寫equals)在Javadoc(你已經報吧)指出,這意味着是這樣的:我們不能告訴如果1 2 3相同3 2 1因爲元素的順序隊列可能很重要,所以請自行解決。

2

這裏的困難是,隊列確實有被訂購的語義,但排序不總是在隊列的迭代順序清單。爲有序集合定義equals()hashCode()幾乎需要按元素的語義順序迭代元素。如果你不能在它們的語義順序遍歷元素,你不能定義一個合理的equals()hashCode()合同。

PriorityQueue就是一個很好的例子。元素的語義順序由提供的比較器或元素的自然順序來定義。但是,PriorityQueue的迭代順序是undefined

迭代器不返回任何特定順序的元素。

原因是PriorityQueue是heap data structure存儲在一個數組中。元素不按順序存儲。它們以符合堆不變量的方式存儲,這比總排序要弱。有許多不同的方法可以將相同的元素存儲在代表相同語義排序的堆中。您可以通過從隊列中提取PriorityQueue的元素來獲取它們的語義順序中的元素 - 這具有銷燬隊列的副作用。

我想通過使用語義順序並應用類似於List的規則,可以定義隊列的equals()hashCode()。對於PriorityQueue,這需要創建數組的臨時副本並在每次調用時對其進行排序。我懷疑這太繁重了;許多程序員會驚訝地發現,計算PriorityQueue的哈希碼需要O(n log n)個時間和O(n)個臨時空間。出於這個原因,我懷疑equals()hashCode()對於隊列沒有指定,從Object繼承基於身份的版本。