.equals()/equalsIgnoreCase()/contains()时间复杂度与爬虫效率问题

核心结论 #

你当前实现的find方法时间复杂度并不优于内置类库的contains()方案，也无法满足自研实现效率超过内置类库的要求，具体原因如下：

• 内置ArrayList.contains()的底层逻辑本身就是遍历数组内的有效元素，逐次调用元素的equals()方法做匹配，和你当前写的遍历+比对逻辑属于完全同构的线性查找，最坏时间复杂度均为O(n)，不存在时间复杂度量级上的优势。
• 你提到的equals()部分场景O(1)的特性，来自String类的两个前置判断：先比对两个字符串的内存引用是否一致，再比对字符串长度是否相等，这两个判断确实是O(1)，引用相同直接返回true、长度不同直接返回false。但你当前使用的equalsIgnoreCase()本身也带长度校验的O(1)前置逻辑，且后续逐字符比对时还要额外处理大小写转换，常数级开销比普通equals()更高，不存在性能优势。

当前实现的额外性能问题 #

你贴出的代码还存在两个拉低效率、甚至会触发异常的问题：

1. 遍历边界错误：你循环的上界是this.arraylist.length，这是底层数组的总容量，不是动态数组实际存储的有效元素个数。常规动态数组扩容都会预留空闲容量，按总容量遍历会无意义访问空槽位，不仅平白增加遍历开销，还会因为对null值调用equalsIgnoreCase()触发空指针异常。
2. 线性查找的天然瓶颈：BFS爬虫的URL查重是高频操作，当已爬URL量级达到十万、百万级时，每次查重都遍历全量集合的O(n)逻辑会让整体时间复杂度退化为O(n²)，不管怎么优化比对方法的常数开销，都解决不了根因。

可满足效率要求的优化方向 #

• 首先修正遍历边界：把循环上界改成动态数组的实际有效元素计数，只遍历已经存入URL的槽位，先把基础逻辑的开销降到和内置contains()同一水平线。
• 替换线性查找为哈希索引：自研一个简单的开链法哈希表配套使用，URL存入动态数组的同时，将统一转小写（或大写）后的URL计算哈希值映射到对应哈希桶，查重时先计算待查URL的哈希值直接定位到对应桶，平均时间复杂度可以降到O(1)，这是能让自研实现性能大幅超过内置线性遍历contains()的核心优化。
• 降低单次比对开销：存储URL时就统一转成全小写/全大写格式，查重时直接用equals()比对，省掉每次调用equalsIgnoreCase()的大小写转换开销。

补充：如果项目要求必须用纯动态数组实现、不允许额外加哈希结构，你可以把URL按域名、路径前缀做分桶存储，把全量遍历的n拆成多个小子集的遍历，也能获得明显的常数级性能提升。

内容的提问来源于stack exchange，提问作者Sam Wong