嘿，我正在寻找一个更好的方法来搜索LinkedList数组中的字符串元素。
public static void main(String[] args) {
int m = 1000;
LinkedList<String>[] arrayOfList = new LinkedList[m];
for (int i = 0; i < m; i++) {
arrayOfList[i] = new LinkedList<>();
}
}
这是我的搜索方法:
public int search(String word) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < arrayOfList[i].size(); j++) {
if (arrayOfList[i].get(j).equals(word)) {
return i;
}
}
}
return -1;
}
这就是我的LinkedLists的样子:
Example output: arrayOfList[0] = [house,car,tree.....]
arrayOfList[1] = [computer,book,pen....]
......
until arrayOfList[1000] = [...]
我的搜索方法应该找到我的单词的索引。 示例:搜索（“计算机”）=1； 搜索（“房屋”）=0
啊，经典！
LinkedList对于随机访问（即list.get(j)方法）来说是出了名的糟糕。 它在遍历列表方面要好得多，因此它可以从每个项跳到下一项。
您可以使用list.iterator（），但是foreach循环执行同样的操作:
public int search(String word) {
for (int i = 0; i < m; i++) {
for (String listValue: arrayOfList[i]) {
if (listValue.equals(word)) {
return i;
}
}
}
return -1;
}
另一个答案指出，通过迭代每个LinkedList，而不是使用List.get，可以获得更好的性能。 这是因为list.get每次都必须从列表的开始搜索。 例如，如果LinkedList有100个元素，那么平均每个对List.get(j)的调用将必须迭代超过50个元素，而您正在进行100次迭代。 foreach循环只对LinkedList元素迭代一次。
foreach策略在O(n)时间内运行，也就是说，执行查找所需的时间与总字数n成比例地增加，因为您必须为每个字搜索它们全部。
如果您要经常这样做，并且您可以使用LinkedList以外的数据结构，那么您应该对LinkedList数组进行一次迭代，并构建一个HashMap，其中键是单词，值是单词所在数组的编号。 设置这个hashmap将需要O(n)时间，但是后续的查找将只需要O(1)时间，这意味着一个恒定的时间，与涉及的字数无关。 因此，如果您要执行不止一次的查找，那么创建hashmap将在big-O方面具有更好的性能，尽管对于极少量的查找（2或3次），扫描数组仍然可能更快。
您可以像下面这样构建一个HashMap:
Map<String, Integer> index = new HashMap<>();
for (int i = 0; i < m; i++) {
for (String word: arrayOfList[i]) {
index.put(word, i);
}
}
现在search变成:
public int search(String word) {
return index.getOrDefault(word, -1);
}
根据程序中如何构造字符串以及调用搜索方法的频率，测试字符串的哈希代码可以提高性能。 例如:
public int search(String word) {
int wordHashCode = word.hashCode();
for (int i = 0; i < m; i++) {
for (String listValue: arrayOfList[i]) {
if (listValue.hashCode() == wordHashCode && listValue.equals(word)) {
return i;
}
}
}
return -1;
}
