如何使用String.contains最好地搜索java中的字符串列表？

Question

现在，我正在开发一个使用语音恢复的android应用程序。基本上，当我从语音识别中得到字符串时，我想知道最好的搜索方法是什么。我目前正在使用packagename列表上的线性搜索，使用以下方法获得该列表：

    pkgNames = new ArrayList<String>();
    pkgAppsList = (ArrayList<ApplicationInfo>) getPackageManager()
            .getInstalledApplications(PackageManager.GET_META_DATA);

    // List available packages on phone.
    for (ApplicationInfo appInfo : pkgAppsList) {

        if (!isSystemPackage(appInfo))
            pkgNames.add(appInfo.packageName);
    }

我已经决定使用ApplicationInfo list(pkgAppsList)并对其进行搜索可能更好，但是是否有一种更快的方法来搜索列表，而不仅仅是简单的线性搜索和使用结果来打开应用程序。现在，我能想到的就是：

    for(ApplicationInfo ai: pkgAppsList){
        if((ai.name).contains(voice_recog_result))
           //open Launch Intent for ai.packageName
    }

是否有一种更快的搜索方法可以用于contains方法，或者我可以在不使用contains方法的情况下做到这一点？

Answer 1

对于少量搜索的字符串(应用程序名称)，应该选择最简单的方法(遍历链接列表)。

自动增长的哈希表通常用于类似的任务，但前提是搜索的字符串集通常很大。哈希表最坏的性能与遍历链接列表(由于自动增长和潜在的大规模哈希值冲突)相同，而且它具有不可忽略的开销。因此，这不是一个很好的选择，“以防万一”保险针对更长的一组字符串。

理论上适合这项任务的数据结构称为trie。尝试不是JCL或Android库的一部分，而是可用的实现可得。最坏的情况下，trie的性能与最长字符串的长度成正比，而不管字符串的数量如何。然而，尝试往往占用大量内存，这使它们成为移动环境中的不合适。