無需迭代即可取得給定 LinkedHashSet 元素的索引

1. 概述

在本教程中，我們將學習如何處理一個罕見的情況：在查詢元素索引時，我們需要確保元素的唯一性。最合理的做法是利用類別中已有的機制，但這可能並非最佳選擇，我們將探討其中的原因。

總的來說，本文提出的方法應該根據特定任務進行調整，並考慮其優缺點。

2. LinkedHashSet

當我們尋找一種能夠確保唯一性並保持元素順序的資料結構時， LinkedHashSet通常是首選。此外，我們還可以遍歷它來尋找給定元素的位置：

public static <E> int getIndex(LinkedHashSet<E> set, E element) {

 int index = 0;

 for (E current : set) {

 if (current.equals(element)) {

 return index;

 }

 index++;

 }

 return -1;

 }

另一種方法是從LinkedHashSet中取得迭代器，但總的來說，方法不會改變；我們只是讓迭代過程更明確：

public static <E> int getIndexUsingIterator(LinkedHashSet<E> set, E element) {

 Iterator<E> iterator = set.iterator();

 int index = 0;

 while (iterator.hasNext()) {

 if (iterator.next().equals(element)) {

 return index;

 }

 index++;

 }

 return -1;

 }

它的主要優點在於幾乎所有功能都開箱即用。然而，它也存在一個小問題：我們無法在常數時間內透過索引來取得元素。這種操作的時間複雜度是線性的，因此如果查找次數過多，可能會顯著影響程式碼的效能。但同時，如果LinkedHashSet的大小成長不大，而尋找操作相對於新增作業而言很少，那麼這種方法或許值得考慮。

3. 轉換

作為一種選擇，我們可以建立一個特殊的資料結構用於查找，例如，將LinkedHashSet轉換為List或陣列：

public static <E> int getIndexByConversion(Set<E> set, E element) {

 List<E> list = new ArrayList<>(set);

 return list.indexOf(element);

 }

在某些情況下，這種方法被認為性能更高。這種誤解源自於我們使用了一個簡單的indexOf()方法，讓我們誤以為它能優化流程。實際上，它執行的迭代次數與之前相同：

public static <E> E getElementByIndex(Set<E> set, int index) {

 List<E> list = new ArrayList<>(set);

 if (index >= 0 && index < list.size()) {

 return list.get(index);

 }

 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + list.size());

 }

將LinkedHashSet轉換為陣列是可行的，但需要一些額外的類型轉換步驟：

@SuppressWarnings("unchecked")

 public static <E> E[] convertToArray(Set<E> set, Class<E> clazz) {

 return set.toArray((E[]) java.lang.reflect.Array.newInstance(clazz, set.size()));

 }



 public static <E> int getIndexByArray(Set<E> set, E element, Class<E> clazz) {

 E[] array = convertToArray(set, clazz);

 for (int i = 0; i < array.length; i++) {

 if (array[i].equals(element)) {

 return i;

 }

 }

 return -1;

 }

一般來說，這種方法並不合理，原因很簡單： indexOf()方法執行的是精確的線性搜索，就像我們在第一個例子中明確做的那樣。此外，我們創建了一個新的資料結構，使該解決方案所需的空間翻倍。但是，如果我們想透過索引來尋找元素，則可以實現常數時間查找。因此，我們需要知道哪些操作需要優先處理，才能選擇合適的方法。

4. List和Set

我們可以稍微改變一下視角，將唯一性和順序維護這兩個要求分開來看。這樣，我們可以使用兩種不同的結構： List和Set. List負責維護順序， Set負責維護唯一性，因此每次我們想要添加一個元素時，我們首先要將其與集合進行比對，然後才能將其插入List中。

public class ListAndSetApproach<E> {

 private final List<E> list;

 private final Set<E> set;



 public ListAndSetApproach() {

 this.list = new ArrayList<>();

 this.set = new HashSet<>();

 }



 public boolean add(E element) {

 if (set.add(element)) {

 list.add(element);

 return true;

 }

 return false;

 }



 public int indexOf(E element) {

 return list.indexOf(element);

 }



 // Other methods

 }

但是，我們應該確保正確地移除元素。在之前的方法中，移除過程是透明的。而現在，我們需要手動移動元素以保持順序：

public class ListAndSetApproach<E> {



 // Initialization, fields, and a constructor



 public boolean remove(E element) {

 if (set.remove(element)) {

 list.remove(element);

 return true;

 }

 return false;

 }



 // Other methods

 }

即使進行了所有這些修改並引入了兩種資料結構，查找操作的時間複雜度仍然是線性的。因此，我們仍然面臨著先前的問題。雖然我們可以添加緩存，但這不會帶來太大改變，因為查找操作和創建資料結構的時間複雜度相同。優化解決方案的唯一方法是創建一個自訂實作來滿足我們所有的需求。

然而，這種方法與前一種方法的情況相同。透過索引來尋找的操作時間複雜度為常數，因此如果我們想要最佳化這些操作，這可能是個不錯的解決方案：

public class ListAndSetApproach<E> {



 // Initialization, fields, and a constructor



 public E get(int index) {

 return list.get(index);

 }



 // Other methods

 }

透過結合兩種資料結構，我們可以融合它們的特性。在本例中，我們利用Set保持唯一性，並利用List保持順序。

5. 客製化實施

為了保持查找的一致性，我們可以使用Maps ，但這需要更複雜的映射。因此，最佳方法是將邏輯封裝到一個單獨的類別中。例如，當我們按照約定連接多個資料結構時，如果我們從第一個資料結構中刪除元素，卻忘記對第二個資料結構執行相同的操作，就會出現很多問題。此外，這種方法有助於我們只展示我們關心的功能，從而限制互動選項：

public class IndexAwareSetWithTwoMaps<E> {

 private final Map<E, Integer> elementToIndex;

 private final Map<Integer, E> indexToElement;

 private int nextIndex;



 public IndexAwareSetWithTwoMaps() {

 this.elementToIndex = new HashMap<>();

 this.indexToElement = new HashMap<>();

 this.nextIndex = 0;

 }



 public boolean add(E element) {

 if (elementToIndex.containsKey(element)) {

 return false;

 }

 elementToIndex.put(element, nextIndex);

 indexToElement.put(nextIndex, element);

 nextIndex++;

 return true;

 }



 public boolean remove(E element) {

 Integer index = elementToIndex.get(element);

 if (index == null) {

 return false;

 }



 elementToIndex.remove(element);

 indexToElement.remove(index);



 for (int i = index + 1; i < nextIndex; i++) {

 E elementAtI = indexToElement.get(i);

 if (elementAtI != null) {

 indexToElement.remove(i);

 elementToIndex.put(elementAtI, i - 1);

 indexToElement.put(i - 1, elementAtI);

 }

 }



 nextIndex--;

 return true;

 }



 public int indexOf(E element) {

 return elementToIndex.getOrDefault(element, -1);

 }



 public E get(int index) {

 if (index < 0 || index >= nextIndex) {

 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + nextIndex);

 }

 return indexToElement.get(index);

 }

 }

這樣，我們也可以透過將LinkedHashSet封裝在一個自訂類別中來簡化解決方案。即使我們只使用一種資料結構，這也有助於我們隱藏快取或在未來更改實作。例如，我們可以先進行簡單的轉換，然後隨著效能對應用程式的影響，在不更改應用程式其他部分的情況下進行必要的改進。

6. 複雜性概述

列出的所有方法都有其優缺點。為了選擇最合適的方法，我們應該了解哪些操作會佔據主導地位、預期處理的資料集的大小以及資料的變化率。我們可以參考下表來決定方法：

方法	添加	消除	索引	取得（按索引）
LinkedHashSet（遍歷索引）	O(1)	O(1)	O(n) （迭代）	不適用
按需轉換為列表/數組	O(n) （重建）	O(n) （重建）	O(n) （線性搜尋）	O(n) （重建占主導地位）
列表 + 設定	O(1)	O(n) （清單刪除）	O(n) （清單搜尋）	O(1)
自訂（兩張地圖，移除時重新索引）	O(1)	O(n) （移位索引）	O(1)	O(1)

大多數情況下，自訂方法效果最佳，因為除了刪除操作外，大多數操作都需要恆定時間。

7. 多線程

當多個執行緒存取這些資料結構時，正確性與時間複雜度同等重要。在單執行緒環境下運行良好的解決方案，如果更新操作協調不當，在並發存取下很容易失效。如果使用單一資料結構，並發集合可以有效解決這個問題。 Java提供了線程安全的實現，可以保護各個操作並降低競態條件的風險。

假設我們採用一種方法，該方法依賴兩個集合的協同工作。即使這兩個集合是並發的，它們的操作也並非同步的。諸如在一個結構中檢查唯一性，然後更新另一個結構之類的複合操作，仍然必須以原子方式執行，以保持資料一致性。

確保這種一致性的最簡單可靠的方法是使用synchronized關鍵字。透過同步相關的方法或程式碼區塊，我們可以保證多步驟操作作為一個整體執行，從而在保持正確性的同時最大限度地降低複雜度。在高競爭應用中，這種直接的方法可能難以擴展。在這種情況下，值得探索更高級的並發技術，並可能需要重新思考整體設計以減少共享的可變狀態。

8. 結論

本文討論了優化indexOf方法的幾種方法。在某些情況下，單一資料結構的功能不足以滿足我們的需求。因此，我們需要將它們結合起來。所有方法各有優缺點，並且高度依賴程式碼的運行環境。因此，並不存在“最佳”解決方案。然而，最靈活的方法是將程式碼封裝在一個專用類別中。這樣，在必要時可以更輕鬆地更改或改進實作。

像往常一樣，本教程中的所有程式碼都可以在GitHub 上找到。