給定一組已知的密鑰，是否可以爲它們確定一個最佳散列函數？

gperf似乎是一種選擇（如果使用C或C++），但是有更好的選擇，至少在某些情況下？示例應用程序將鏈接代碼與例外。對於常見的異常處理實現，鏈接器需要從返回地址（用於調用可能生成異常的函數）到函數的銷燬/定型代碼地址構造一個最佳關聯查找，以便堆棧展開。給定一組已知的密鑰，是否可以爲它們確定一個最佳散列函數？

來源

2017-03-02 WaltK

標題聽起來更像是一個數學/ CS問題，然後是編程問題。不確定你在問題的正文中得到了什麼。 – NathanOliver

@NathanOliver是的，但它與我標記的語言有關，並且我還標記了算法。與異常處理的相關性與Java和C++的相關性。 – WaltK

什麼是*「最佳散列函數」*？ –

如果您事先知道所有已知的密鑰集，然後構建密鑰的trie/keyword tree。在每個單詞末尾添加一個唯一的索引。

這樣，你的散列函數將永遠不會超過O(length_of_the_largest_string)時間。而內存需要的是O(total_character_in_all_the_strings)

如果你只使用唯一的前綴，那麼你可以減少一些時間和內存。

來源

2017-03-02 18:39:35 silentboy

是的，但有另一種方法更快，使用更少的內存（執行時）。 – WaltK

@WaltK您能詳細說明您建議的具體方法嗎？ – silentboy

這是一個誠實的問題，我沒有辦法建議。 Modulo，FNV，CRC是我認爲最快的哈希函數之一。如果給定一組密鑰，你可以爲它們的CRC哈希推導出一個最佳多項式，這將是很酷的。 – WaltK

給定一組已知的密鑰，是否可以爲它們確定一個最佳散列函數？

回答

相關問題