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

Question

现在我正在开发一个使用语音识别的 Android 应用程序。基本上，我想知道从语音识别中获得字符串后最好的搜索方法是什么。我目前正在包名称列表上使用线性搜索，使用以下命令获取该列表:

    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 列表(pkgAppsList)并对其进行搜索可能更好，但是是否有比简单的线性搜索并使用结果打开应用程序更快的方法来搜索该列表带着 Intent 。 现在我能想到的就是:

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

有没有一种可以与 contains 方法一起使用的更快的搜索方法，或者可以在不使用 contains 方法的情况下执行此操作的方法？

Answer 1

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

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

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