地圖與位置索引

Question

哪個集合將滿足下面的測試程序：

public class TestOrderedList { 

    // The class I'm looking for: 
    MapWithIndex<String,Person> ol = new MapWithIndex<String, Person>(); 

    // class Person left out for brevity 

    public TestOrderedList() { 

    Person benny = new Person("Benny"); 
    Person charles = new Person("Charles"); 
    Person alvin = new Person("Alvin"); 
    Person calvin = new Person("Calvin"); 

    ol.put("Benny", benny);  // should return 0 
    ol.put("Charles", charles); // should return 1 
    ol.put("Alvin", alvin);  // should return 0 
    ol.put("Calvin", calvin); // should return 2 

    int index = ol.findIndex("Benny"); // should return 1 
    Person adam = new Person("Adam"); 
    ol.put("Adam", adam);    // should return 0 (new pos) 
    index = ol.findIndex("Benny");  // should return 2 
    ol.remove("Alvin");    // should return 1 (existing pos) 
    index = ol.findIndex("Benny");  // should return 1 
    } 
} 

集合不必是實現任何特定的接口，或可轉換爲另一個集合（然而這是可能這將是尼斯）。

它不必是線程安全的，但如果是....好！

返回-1找不到或錯誤的情況是OK的時候。

收集的目的是，我很快就需要知道在哪個位置一個新插入的記錄放入。此外，我想在一個記錄存在什麼位置查找。

收集並不需要支持重複鍵。

---更新----

我去ArrayList的解決方案，其中我把它插入之前做一個二進制查找排序（得到它應插入索引）。這樣，列表中的位置總是對應於行號（在與該列表同步的表中）。它快速簡單。我確定必須存在比我更強大的實現，儘管？！？！

Answer 1

您可以使用數組以「發現」的二進制搜索實現，問題是，有一個數組是昂貴的添加/刪除項目。一個indexable skip list會更容易增長/縮小，與數組的查找次數相同，但是數組有更好的最壞情況查找，並且也可能具有更好的高速緩存性能。如果你期望經常增加/刪除，那麼我會說使用可索引跳過列表，如果它們很少，那麼使用一個數組。也可能有某種方法來緩衝數組的增加/刪除以獲得更好的攤銷性能，但是我不知道你會如何做到這一點。

Answer 2

使用linkedHashMap，以確保秩序和保持他們的指數在一個單獨的地圖實現。

Answer 3

import java.util.Map; 
import java.util.Set; 
import java.util.TreeMap; 

public class MySortMap { 


// The class I'm looking for: 
    Map<String,Person> ol = new TreeMap<String, Person>(); 

    // class Person left out for brevity 

    public void TestOrderedList() { 

    Person benny = new Person("Benny"); 
    Person charles = new Person("Charles"); 
    Person alvin = new Person("Alvin"); 
    Person calvin = new Person("Calvin"); 

    ol.put("Benny", benny);  // should return 0 
    ol.put("Charles", charles); // should return 1 
    ol.put("Alvin", alvin);  // should return 0 
    ol.put("Calvin", calvin); // should return 2 

    int index = getIndex(ol.keySet(), "Benny"); // should return 1 
    System.out.println("expected 1, index=" + index); 
    Person adam = new Person("Adam"); 
    ol.put("Adam", adam);    // should return 0 (new pos) 
    index = getIndex(ol.keySet(), "Benny");  // should return 2 
    System.out.println("expected 2, index=" + index); 
    ol.remove("Alvin");    // should return 1 (existing pos) 
    index = getIndex(ol.keySet(), "Benny");  // should return 1 
    System.out.println("expected 1, index=" + index); 

    } 

    private int getIndex(Set<String> paramSet, String paramSearchStr) { 
     int result = -1; 
     for (String strSetValue : paramSet) { 
     result++; 
     if (strSetValue.equals(paramSearchStr)) { 
      return result; 
     } 
    } 
     return -1; 
    } 
/** 
* @param args 
*/ 
public static void main(String[] args) { 
    MySortMap mySortMap = new MySortMap(); 
    mySortMap.TestOrderedList(); 
} 

    class Person { 
     public Person(String paramPerson) { 

     } 
    } 
} 

RESULT: 
expected 1, index=1 
expected 2, index=2 
expected 1, index=1