在java中为以下数据选择完美的数据结构

Question

我必须根据我的需要选择一种数据结构，我在下面解释以下值的条件

abc,def,rty,ytr,dft   which all are map to row R1B1 (actully key is combination of R1+B1)
abEERc,dFFFef,rGGty   which all are map to row R1B2 (actully key is combination of R1+B2)

  KEY                      VALUE
abc,def,rty,ytr,dft --->    R1B1
abEERc,dFFFef,rGGty --->    R1B2

现在，比如说，如果我得到ytr，那么我将能够检索R1B1，或者说，我得到rGGty的值，那么我将能够检索R1B2

现在的情况是，重要的是搜索、复杂性和事情按顺序进行所需的时间

例如，它将首先选择要搜索的第一行，它将首先与不匹配的abc匹配，然后必须与def匹配，然后再与不匹配的rty匹配，最后与ytr匹配，最后找到键R1B1

类似地，如果需要搜索第二个字符串，比如说rGGty，那么它将扫描第一行，在其中它将找不到值，然后搜索将继续到第二行，并且在第三个元素的第二行，它将获得rGGty作为元素，然后将R1B2作为值检索

比方说，如果把这个东西放在地图上，那么序列搜索将在键上进行，然后只有我们才能找到相应的值

各位朋友，请告诉我，哪种数据结构是我用java实现的最好的数据结构，我必须在非常快的时间内搜索关键字项以找到相应的值，这也不会影响性能，这种数据结构的性能应该非常高

请忠告乡亲们

Answer 1

我认为最好保持简单，直到糟糕的性能表明需要某种改进。即使许多映射值是同一个字符串，这也应该可以，因为Java在堆中只存储一个副本。如果映射到单个字符串的键集变得非常大，则可以通过执行两次查找来提高性能——第一次是确定集合成员身份，第二次是检索与集合关联的键的值。这很容易实现。目前，这里有一个直接的方法：

import java.util.*;

public class HashMapDemo {

    static HashMap<String, String> map = new HashMap<String, String>();

    public static void lookup(String key, String value) {
        if (map.get(key) == value) {
            System.out.println(key + " lookup ok");
        } else {
            System.out.println(key + " lookup produced" + map.get(key));
        }
    }

    public static void main(String[] args) {
        // requirements:
        // abc,def,rty,ytr,dft ---> R1B1
        // abEERc,dFFFef,rGGty ---> abEERc

        Set<String> kset1 = new HashSet<String>(Arrays.asList("abc", "def",
                "rty", "ytr", "dft"));

        Set<String> kset2 = new HashSet<String>(Arrays.asList("abEERc",
                "dFFFef", "rGGty"));

        for (String s : kset1) {
            map.put(s, "R1B1");
        }

        for (String s : kset2) {
            map.put(s, "abEERc");
        }

        // testing value lookup with key

        for (String s : kset1) {
            lookup(s, "R1B1");
        }

        // prints:
        // abc lookup ok
        // dft lookup ok
        // def lookup ok
        // rty lookup ok
        // ytr lookup ok

        for (String s : kset2) {
            lookup(s, "abEERc");
        }

        // prints:
        // rGGty lookup ok
        // abEERc lookup ok
        // dFFFef lookup ok

        // change key "R1B1" to "XYZ"

        for (String s : kset1) {
            map.put(s, "XYZ");
        }

        // test the change

        for (String s : kset1) {
            lookup(s, "XYZ");
        }

        // prints:
        // abc lookup ok
        // dft lookup ok
        // def lookup ok
        // rty lookup ok
        // ytr lookup ok

    }
}

Answer 2

可以使用HashMap在O（1）中访问键值对。但是如果使用HashMap

public class MyDataStructure {

  private Map<String, MyValue> key_value = new HashMap<String, MyValue>();
  private Map<String, MyValue> value_MyValue = new HashMap<String, MyValue>();

  public void set(String key, String value) {
    MyValue v = value_MyValue.get(value);
    if (v == null) { // should rarely happen, could check with containsKey
      v = new MyValue(value);
      value_MyValue.put(v);
    }
    key_value.put(key, v);
  }

  public String get(String key) {
    return key_value.get(key).getValue(); // key might not exist
  }

  public String changeValue(String oldValue, String newValue) {
    MyValue v = value_MyValue.remove(oldValue); // oldValue might not exist
    v.setValue(newValue); 
    value_MyValue.put(newValue, v);
    // will not work if newValue already exists... then you will have to merge
  }

  private class MyValue() {
    private String value;
    public MyValue(String value) {
      this.value = value;
    }
    public String getValue() {
      return value;
    }
    public void setValue(String value) {
      this.value = value;
    }
  }
}