是否有產生記得所有我們所遇到

我處理成百上千的文件的字符串中的一個密鑰的方法，是否有產生記得所有我們所遇到

我必須處理這些文件1 * 1，在這樣做，我需要記住已處理的文件。

我能想到的只是每個文件在一個數組中的每個文件的文件路徑，然後每次檢查它的重複。

但是，我認爲應該有一些更好的辦法，

是否有可能對我來說，生成密鑰（這是一個數字）或什麼的，只是記住了所有已處理的文件？

來源

2010-11-10 Alphaneo

另請參閱http://stackoverflow.com/questions/2962207/constructing-a-hash-table-hash-function – 2010-11-10 05:21:49

你需要什麼來記住它們？這取決於你將使用這些信息。 – 2010-11-10 05:22:16

@J Kugelman，意思是它不是一個哈希表，而只是一個只記得一個鍵，如果一個特定的字符串已經遇到或沒有。 – Alphaneo 2010-11-10 05:26:56

你需要什麼，恕我直言，是某種基於樹或散列的集合實現。它基本上是一個數據結構，它支持非常快速的添加，刪除和查詢操作，並且只保留每個元素的一個實例（即不重複）。幾十萬個字符串（假設它們本身不是幾十萬個字符）應該不會成爲這種數據結構的問題。

你選擇的編程語言可能已經有一個，所以你不需要自己寫一個。 C++有std::set。 Java具有Set實現TreeSet和HashSet。 Python有一個Set。它們都允許您添加元素並快速檢查元素的存在（O（1）用於基於哈希表的集合，O（log（n））用於基於樹的集合）。除此之外，還有很多免費的集合實現以及可以使用的通用二元搜索樹和散列表。

來源

2010-11-10 07:00:17 MAK

這是我得到的最接近的建議，雖然布隆過濾器是我正在尋找的，所以我會繼續接受這個答案。 – Alphaneo 2010-11-25 00:47:41

你可以使用某種散列函數（MD5，SHA1）。

僞代碼：

for each F in filelist 
    hash = md5(F name) 

    if not hash in storage 
     process file F 
     store hash in storage to remember

看到http://tools.ietf.org/html/rfc1321的C實現MD5的

來源

2010-11-10 05:21:24

@RC感謝您的回覆，請給我更多的細節。 – Alphaneo 2010-11-10 05:22:38

@RC Thankyou瞭解詳情，我想我需要重述一下我的問題。我只是有興趣知道我是否已經使用文件名處理文件。還有一個鍵會讓我知道我是否已經處理了文件名... – Alphaneo 2010-11-10 05:35:22

@Alphaneo，添加了說明 – 2010-11-10 05:41:02

有跡象表明，給予近似的結果概率論方法，但如果你想知道自己是否一個字符串是一個你已經前面看過或沒看過，你必須存儲你迄今爲止看到的所有字符串，或者等價的信息。這是一個鴿子的原則論據。當然，你可以通過不使用散列表，二叉樹等各種不同的方法直線搜索你已經看到的字符串。

來源

2010-11-10 05:44:39

如果我正確理解你的問題，你想創建一個SINGLE鍵應該具有特定的值，並且從這個值你應該能夠推斷哪些文件已經被處理了？我不知道你是否能夠做到這一點，僅僅是因爲你的空間非常大，在如此巨大的空間中生成獨特的關鍵演示需要大量的內存。

如前所述，您可以做的只是將每個路徑URL存儲在HashSet中。將十萬個條目放入集合中並不是那麼糟糕，並且查找時間是分段恆定時間O（1），所以它會很快。

來源

2010-11-10 05:52:34

Bloom filter可以解決您的問題。布盧姆過濾器的想法很簡單。它從具有一定長度的空數組開始，其所有成員都具有零值。我們將有K個散列函數。當我們需要將一個項目插入布隆過濾器時，我們擁有包含所有K哈希函數的項目。這些散列函數將在布隆過濾器上獲得K個索引。對於這些索引，我們需要將成員值更改爲1. 要檢查布隆過濾器中是否存在項目，只需使用所有K哈希對其進行哈希處理並檢查相應的數組索引。如果它們全部爲1，則該項目存在於布隆過濾器中。

請注意，bloom濾鏡可以提供假陽性結果。但是這絕不會產生錯誤的否定結果。您需要調整bloom濾波算法來解決這些誤報情況。

來源

2010-11-10 09:33:29 kjoshi

是否有產生記得所有我們所遇到

回答

相關問題