为什么以下两个重复查找算法的时间复杂度不同？

我正在读这个question https://stackoverflow.com/questions/3951547/java-array-finding-duplicates。所选答案包含以下两种算法。我不明白为什么第一个的时间复杂度是O(ln(n))。在最坏的情况下，如果数组不包含任何重复项，它将循环 n 次，第二个也是如此。我错了还是我错过了什么？谢谢

1）更快（极限）的方式

这是一种基于哈希的方法。你必须为自动装箱付费，但它是 O(ln(n)) 而不是 O(n2)。一个有进取心的人会去寻找一个基于 int 的原始哈希集（我认为 Apache 或 Google Collections 有这样的东西。）

boolean duplicates(final int[] zipcodelist)
{
  Set<Integer> lump = new HashSet<Integer>();
  for (int i : zipcodelist)
  {
    if (lump.contains(i)) return true;
    lump.add(i);
  }
  return false;
}

2）向海勒鞠躬

请参阅 HuyLe 的答案，了解或多或少的 O(n) 解决方案，我认为这需要几个附加步骤：

static boolean duplicates(final int[] zipcodelist) {    
    final int MAXZIP = 99999;    
    boolean[] bitmap = new boolean[MAXZIP+1];    
    java.util.Arrays.fill(bitmap, false);    

    for (int item : zipcodeList)
        if (!bitmap[item]) bitmap[item] = true;
        else return true;    
    }

    return false; 
}

第一个解决方案的预期复杂度应该为 O(n)，因为必须遍历整个邮政编码列表，并且处理每个邮政编码的预期时间复杂度为 O(1)。

即使考虑到插入 HashMap 可能会触发重新哈希，复杂度仍然是O(1) http://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec20.html。这有点不合逻辑，因为 Java HashMap 和链接中的假设之间可能没有关系，但它表明这是可能的。

From HashSet http://docs.oracle.com/javase/1.4.2/docs/api/java/util/HashSet.html文档：

本课程提供恒定时间基本操作的性能（add， 消除，contains和大小），假设哈希函数将元素正确地分散在桶中。

第二个解也是一样，分析正确：O(n)。

（只是一个题外话，BitSet 比数组更快，如原始帖子中所示，因为 8booleans 被打包成 1byte，使用更少的内存）。