效率不高的「專用」散列

Question

我的問題聽起來有點奇怪： 我知道用於加密的散列函數必須具有可以大幅改變輸出的特性，即使由於某種雪崩效應。

是否有不適當哈希存在的特點爲相似字符串它產生類似的輸出？

如果答案是肯定的，你能告訴我是否有辦法操縱這個方面（「類似」的定義）與文本的字符之間的基礎預知關係？

Answer 1

這些哈希函數被稱爲locality sensitive。

Answer 2

是的，它存在。正如你所期望的，必須給出類似的定義。但這取決於你的應用程序 - 我可以舉個例子。

假設您的字符串是域，並且您想將所有子域散列到一個存儲桶中。然後，你可以扭轉字符串一樣：

finance.yahoo.com => com.yahoo.finance 
sport.yahoo.com => com.yahoo.sport 
user.mail.yahoo.com => com.yahoo.mail.user 

和哈希只有前兩個部分：com.yahoo，下降休息。你的哈希函數可能看起來像這樣（在Python中）：

def hash(url): 
    return any_other_hash_function(".".join(url.split(".")[::-1][:2])) 

你的問題根本就不奇怪。您可以在Google的map-reduce或BigTable（以及許多其他系統中）中找到類似的方法來完全保留類似的東西，以便加速計算。

我給出的例子是字符串，但是您可以對其他對象使用類似的方法。這裏的想法是將項目分成組並散列組ID（高級域名）。