如何在一个巨大的数字列表中找到两个数字，其中xi = xj？

Question

我有以下问题，并在我的尖叫声与哈希的解决方案：

问题：

鉴于巨大的号码列表，x1........xn其中xi <= T，我们想知道是否 或不存在两个指数i,j，其中x_i == x_j。
在O(n)运行时间中找到算法，并且期望值为O(n)。

我此刻解决方案：我们使用散列，我们将使用chaining有一个映射功能h(x)。

首先 - 我们建立一个新的数组，我们称之为A，其中每个单元格都是一个链表 - 这将是目标数组。

现在我们运行所有n数字，并使用散列函数将x1........xn中的每个元素映射到合适的位置。这将需要O(n)运行时间。

之后我们将在A上运行，并寻找冲突。如果我们找到一个单元，其中length(A[k]) > 1 然后我们返回xi和xj映射到存储在A[k]中的值 - 对于最差的情况，总运行时间将是O(n)，如果两个数字的映射值（如果它们确实存在）在A的最后一个单元格中。

Answer 1

同样的方法可以快两倍（平均），平均而言仍然是O(n) - 但具有更好的常数。

没有必要所有的元素融入到哈希表，然后去在它 - 一个更快的解决方案可能是：

for each element e: 
    if e is in the table: 
     return e 
    else: 
    insert e into the table 

还要注意，如果T < n，必须有第一T+1元素中的欺骗，从pigeonhole principle。
也适用于小型T，您可以使用T大小的简单数组，不需要散列(hash(x) = x)。 Initializing T can be done in O(1)包含零作为初始值。