搜索与多个参数，Java集合的选择建议

Question

我应该在的情况下使用什么数据结构如下：

我有一个简单的bean：

public class Points { 

    private String name; 
    private String address; 
    private int phone; 
    private int coord1; 
    private int coord2; 

    //getters+setters 

    } 

我想创造一些豆类和商店他们在某种数据结构中。 并且能够使用两个参数 - 名称和地址进行搜索。

例如，用户键入“7” - 并且它给了他几个对象， 哪个名字或地址包含这个字符？

我应该使用哪种数据结构，以及如何通过它进行搜索？

如果是重要的，我确实需要这个落实到我的Android应用程序 - 我想通过我的点在地图 上搜索我也不想到目前为止创建一个数据库，因为只有20其中。

非常感谢您提前。

Answer 1

尝试Java的集合，例如HashMap中。虽然我在PC上运行了这个项目，但有10000个项目，搜索 返回了3440个结果，但花了76ms。

class Points { 

     String name; 
     String address; 
     int phone; 
     int coord1; 
     int coord2; 

     // getters+setters 
    }; 

    class PointsIdentifier { 

     private String name; 
     private String address; 

     public PointsIdentifier(String name, String address) { 
      this.name = name; 
      this.address = address; 

     } 

     public boolean contains(String seq) { 
      return name.contains(seq) || address.contains(seq); 
     } 

     @Override 
     public boolean equals(Object obj) { 
      Points other = (Points) obj; 
      return name.equals(other.name) && address.equals(other.address); 
     } 

     @Override 
     public int hashCode() { 
      return name.hashCode() + address.hashCode(); 
     } 
    }; 

    class PointsCollection { 
     private Map<PointsIdentifier, Points> map; 

     public PointsCollection() { 
      map = new HashMap<PointsIdentifier, Points>(); 
     } 

     public void add(Points p) { 
      map.put(new PointsIdentifier(p.name, p.address), p); 
     } 

     public List<Points> findIdsContaining(String seq) { 
      List<Points> resultList = new ArrayList<Points>(); 
      for (Entry<PointsIdentifier, Points> entry : map.entrySet()) { 
       if (entry.getKey().contains(seq)) { 
        resultList.add(entry.getValue()); 
       } 
      } 
      // optionally cache result 
      return resultList; 
     } 
    } 

    public class Question_11881630 { 

     public static void main(String[] args) { 
      PointsCollection places = createCollection(10000); 
      System.out.println("Collection created"); 
     String seq = "1"; 

     System.out.format("Searching for: \"%s\"\n", seq); 
     List<Points> verifySearch = verifySearch(places, seq); 
     //show(verifySearch); 
    } 

    private static void show(List<Points> verifySearch) { 
     int i = 1; 
     for (Points p : verifySearch) { 
      System.out.println(i + ": " + p.name + ", " + p.address); 
      i++; 
     } 
    } 

    private static List<Points> verifySearch(PointsCollection places, String seq) { 
     long start = System.currentTimeMillis(); 
     List<Points> searchResult = places.findIdsContaining(seq); 
     System.out.println("Search results: " + searchResult.size()); 
     long end = System.currentTimeMillis(); 
     System.out.println("Operation time: " + formatTime(end - start)); 
     return searchResult; 
    } 

    private static String formatTime(long elapsed) { 
     return elapsed + " miliseconds"; 
    } 

    private static PointsCollection createCollection(int number) { 
     PointsCollection coll = new PointsCollection(); 
     while (number > 0) { 
      coll.add(createSamplePoint(number)); 
      number--; 
     } 
     return coll; 
    } 

    private static Points createSamplePoint(int number) { 
     Points p = new Points(); 
     p.name = "VeryVeryLongName: " + number; 
     p.address = "VeryVeryLongLongAddress: " + number; 
      p.coord1 = 123; 
      p.coord2 = 456; 
      return p; 
     } 
    } 

Answer 2

A trie似乎很适合。查找具有特定前缀的所有字符串是一种高效的数据结构。

如果您想使用其中一个现有java集合，可以使用TreeSet及其floor()方法在需要的前缀之前获取元素 - 然后在仍然匹配时开始迭代集合。

如果你被串寻找搜索，不仅前缀 - 你可能想使用suffix tree代替。
使用Java现有容器的一种（低效率）替代方案是将密钥的所有子字符串存储在Set或Map中，但需要二次空间。