java在ArrayList中查找<String>

Question

我有这个

private ArrayList<String> words;

这是一本字典，所以单词已经分类了。根据以前的研究，我知道二项式搜索应该非常快，我想Java已经实现了必要的功能

那么，找到排序的数组列表中是否存在某个字符串的最有效方法是什么？ 或者我应该使用另一种类型

谢谢

Answer 1

二进制搜索将是排序数组中最快的。如果您使用的是散列集，则可以在固定时间内进行存在性测试

Answer 2

取决于您要尝试查找特定字符串的次数。你可能想试试HashMap<String, String>，因为这会随着地图的增长而保持快速

Answer 3

如果要进行二进制搜索，我建议您将数据重新组织为Binary Search Tree

ArrayList通常用于顺序操作和随机访问。如果你要做一个搜索并且想要最快的查找，最好从一开始就组织好你的数据。这也有利于更快地插入/删除以及您希望在尽可能快的时间内完成的所有其他操作

谷歌和其他网站上有大量指南可以帮助你入门

Answer 4

Or should I use a different type?

试着改用HashSet<String>。它的contains方法具有O（1）查找，假设没有太多哈希冲突。从文件中：

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

在排序的ArrayList上的二进制搜索只有O（logn）。这仍然非常快，但没有使用HashSet那么快