散列正整數/負整數序列

Question

我有一個包含數百萬行的文件（實際上它是一個在線的數據流，這意味着我們逐行接收），每行包含一個整數數組排序（正面和負面）沒有限制的每個數字和長度是不同的，我們可能有重複值在一行，

我想刪除duplicate lines（如果2行具有相同的值，無論他們是如何命令我們認爲它們是重複的），有沒有什麼好的散列函數？

我們要做到這一點在O(n)而n是行數（我們可以假設，在每一行元素的最大possibele數量是恆定的，例如，我們有最大的在每行100種元素）

我已經閱讀了一些在這裏發佈的stackoverflow的問題，我也google了一下，其中大部分是針對數組長度相同或者整數是正數甚至是整數的情況，有什麼方法可以解決這在一般情況下？

我的解決方案： 首先，我們使用排序算法0​​排序每一行。 Counting sort，然後我們把它們放到一個字符串中，然後我們使用md5散列將它們放到一個哈希集合中。如果它不在集合中，我們將它放入該集合中，如果它已經在列表中，我們檢查具有相同哈希值的數組。

問題與解決方案：使用Counting Sort排序需要大量的空間，因爲沒有數量的限制和碰撞是可能的。

Answer 1

在一組數據上使用散列算法的問題很大，這是因爲兩個不同的行散列到相同的值的概率很高。你想留在O（n），但我不確定這是可能的，數據的大小和準確性需要。如果你使用heapsort，這是節省空間，然後遍歷新的排序數據刪除連續的行是相同的，你可以在O（nlogn）中完成這一行