如何减少Ruby Hash中的查找次数？以查找数组首个重复元素为例

假设你要找出数组里的第一个重复元素，可以用下面的代码实现：

cnt = {};
[ 11, 22, 77, 22, 33 ].each_with_index { |x,i|
  j = cnt[x];          ## <1>
  break [x, j, i] if j
  cnt[x] = i           ## <2>
} #=> [ 22, 1, 3 ]

只要Ruby Hash的查找和插入操作是O(1)，这段代码的时间复杂度就是O(n)，但它会执行两次查找（标记<1>和<2>的位置）。

那有没有办法避免这第二次查找？

我试过这么写：

cnt = {}
some_array.each_with_index { |x,i|
  j = cnt.exchange( x, i );
  break [x, j, i] if j
}

还自己实现了exchange方法：

def exchange( k, val )
  old, self[k] = self[k], val
  return old
end

但本质上这只是把第二次查找藏起来了，并没有真正避免它。

内容的提问来源于stack exchange，提问作者Toni Schilling