地图与位置索引

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