假設我們有一個位元組字串的集合，像往常一樣按字典順序排序。我們想要定義一個散列函式，將一個字串映射到一個整數，這樣散列值的排序可以將字串的排序保留到足夠的程度。也就是說，給定字串 A 小于或等于字串 B，H(A) 應該總是產生一個小于或等于 H(B) 的值。
顯然，這種不太好的散列函式是可能的。例如，我們可以為每個字串取一個固定前綴（比如 8 個位元組），并將其假裝為大端無符號 int64。結果整數將按所需順序排序。這種方法甚至適用于較短的字串：我們可以將一些 0 附加到一個短字串以使其至少具有前綴位元組長（但前提是我們可以假設 0 不是有效的位元組值）。
不幸的是，這種潛在的解決方案雖然快速簡單，但也存在重大缺陷。在字串傾向于具有相當大的公共前綴的情況下，它變得相當無用。當 '0x00' 是一個有意義的位元組并且我們希望在較長的字串之前對較短的字串進行排序時，它不能處理比??所選前綴短的字串。
所以問題是是否有可能做得更好？一些算術（或者更確切地說是 Knuth 的“具體數學”之類的）技巧可以考慮字串的所有位元組并產生適當排序的哈希值？
uj5u.com熱心網友回復：
你能做的最好的事情是應用一個保序的算術編碼，基于你能想出的最好的字串統計模型，然后取一個前綴來形成“散列”代碼。
然后，根據該統計模型，每個哈希碼的可能性相同。
如果您的模型只是所有字串的可能性均等，那么這將簡化為您的“僅采用前綴的想法”...因此，這是否對您有用實際上取決于您對字串的了解程度以及您的水平需要這個代碼。
另請注意，許多現實模型也將允許更簡單的編碼方案。“只取前綴”又是一個例子。
人們可能認為他們想用這樣的“哈希碼”做的大多數事情都是不切實際的——你最終可能會做其他事情。也許你想問你真正的問題，所以我們可以通過其他方式幫助解決它。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446428.html