搜索用于存储和检索元素的完美数据结构[复制]

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

在您的情况下反转键和值，并使用多重映射数据结构。请参阅此处有关多地图的好文章。http://tomjefferys.blogspot.com/2011/09/multimaps-google-guava.html

@Test
public void getColor(){
    Multimap<String,String> myMultimap = ArrayListMultimap.create();


    myMultimap.put("R1B1","abc");
    myMultimap.put("R1B2","def");

    myMultimap.put("R1B2","abEERc");
    myMultimap.put("R1B2","rGGty");

    Multimap<String, String> invertedMultimap = Multimaps.invertFrom(myMultimap, ArrayListMultimap.<String, String>create());

    System.out.println(invertedMultimap.get("abc"));

}

Answer 2

正如评论所建议的，您可以简单地使用HashMap或HashTable，
如果您坚持自己实现一个结构，我会建议使用搜索trie。
在搜索trie中，检索数据所需的最大比较数等于所用密钥的长度，因此要检索给定密钥（abc，def，rty，ytr，dft）的数据，需要恰好3个比较。
考虑以下维基百科链接：https://en.wikipedia.org/wiki/Trie
下面是我对搜索trie的快速而肮脏的实现（前提是密钥是标准的ASCII字母）：）-

public class DictionaryNode 
{
    DictionaryNode next[];
    String data;
    DictionaryNode()
    {
        next=new DictionaryNode[128];
        for(int i=0;i<next.length;i++)
        {
            next[i]=null;
        }
        data=null;
    }
}

public class Dictionary 
{
    DictionaryNode root;
    Dictionary()
    {
        root = new DictionaryNode();
    }
    public boolean add(String key,String data)
    {
        char[]ch=key.toCharArray();
        DictionaryNode current=root;
        for(int i=0;i<ch.length;i++)
        {
            if(current.next[ch[0]]==null)
            {
                current.next[ch[0]]=new DictionaryNode();
            }
            current=current.next[ch[0]];
        }
        if(current.data==null)
        {
            current.data=data;
            return true;
        }
        else
        {
            return false;
        }
    }
    public String search(String key)
    {
        char[]ch=key.toCharArray();
        DictionaryNode current=root;
        for(int i=0;i<ch.length;i++)
        {
            if(current.next[ch[0]]==null)
            {
                return null;
            }
            else
            {
                current=current.next[ch[0]];
            }
        }
        return current.data;
    }
}

public class main {
    public static void main(String []args)
    {
        Dictionary d=new Dictionary();
        d.add("abc", "R1B1");
        d.add("def", "R1B1");
        d.add("rty", "R1B1");
        d.add("ytr", "R1B1");
        d.add("dft", "R1B1");
        System.out.println(d.search("abc"));
        System.out.println(d.search("ab"));
    }
}