.equals() vs .equalsignorecase() vs .contains()的时间复杂度

Question

我的任务是创建一个不使用导入库(如LinkedList和ArrayList)的BFS网络爬虫。

因此，我需要创建我自己的动态数组和LinkedList实现。

其中一个要求是尝试使我的程序比仅仅使用导入的库更有效。

当检查我已经爬行的URL是否已经在我的动态数组中，我使用equals()或equalsignorecase()而不是contains()

请问这是否会改善时间复杂度?

我知道最坏的情况是O(n)但我看到equals()有时也可以是O(1)

`
public boolean find (String URL) {
for (int i = 0; i < this.arraylist.length; i++) {
if (URL.equalsIgnoreCase(this.arraylist[i])) {
return true;
}
}
return false;
}
`

Answer 1

您没有'Hashmap'甚至'Vector'吗?

在我看来，你正在对一个数组进行顺序搜索，这是O(n)，不太好。

相反，您可以使用数组列表的一个数组，并使用哈希码。比如:

List<String>[] arrayLists = new List[100];
{
for (int i=0; i<100; i++) arrayLists[i] = new ArrayList();
}
public void store(String URL){
arrayLists[URL.hashCode()%arrayLists.length].add(URL);
}
public boolean find (String URL) {
List<String> myArrayList = arrayLists[URL.toLowerCase().hashCode()%arrayLists.length];
for (int i = 0; i < myArrayList.size(); i++) {
if (URL.equalsIgnoreCase(myArrayList.get(i))) {
return true;
}
}

return false;
}

这应该给你的复杂度为0 (N/arrayLists.length) -当数组列表的长度接近你的URL的长度时，复杂度将下降到0(1)最坏的情况