0

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

我有一个简单的豆子： 

 public class Points { 

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

    //getters+setters 

    }

我想创建几个bean并将它们存储在某种数据结构中。并且能够使用两个参数进行搜索 - 名称和地址。

例如，用户输入“7” - 它会返回几个对象，哪个名称或地址包含该字符？

我应该使用什么数据结构以及如何搜索它？

如果它很重要，我实际上需要将它实现到我的 android 应用程序中——我想在地图上搜索我的点此外，到目前为止我不想创建一个数据库，因为它们只有 20 个。

非常感谢您提前。

4

2 回答 2

1

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

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

如果您正在寻找 substring 搜索，而不仅仅是前缀 - 您可能希望使用后缀树。
使用 java 现有容器的一种（低效）替代方案 - 将键的所有子字符串存储在 aSet或 aMap中，但它需要二次空间。

于 2012-08-09T10:48:05.353 回答
1

试试java 的集合，例如hashmap。虽然我在 PC 上运行了这个，10000 个项目，搜索返回 3440 个结果，它花了 76 毫秒。

    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;
        }
    }
于 2012-08-09T11:41:49.847 回答