2010-10-24 43 views
1

hash(x)可以返回的最小值是多少?我想要使​​用散列給數據庫值一個快速的「指紋」(基本上可以很容易地看出兩個較長的,相似的文本實際上是否相等),並且想要消除負數(爲了簡單起見),所以我想我只是添加儘可能小的值來獲得零和上的值。 the manual非常有用地指出「哈希值是整數」。這與我之前所知道的一樣多。hash()函數的最小值?在Python中(3)

今天我有點驚訝,當我發現我的64位ubuntu上的手工編譯的Python顯然使用64位左右的散列函數;我一直認爲應該是32位。機器體系結構對hash()函數有影響嗎?

另外,當我編譯Python時,我沒有設置任何選項來編譯64位體系結構(希望它會「只是工作」)。 python是否會自行調整它,或者我現在是否在64位機器上有32位python?不是一個愚蠢的問題,我相信很多次你根據處理器提供單獨的軟件包。

編輯:我強烈懷疑,答案將被密切相關的sys.maxint已經黯然蟒蛇3.我的懷疑去除的是,我應該def xhash(x): return hash(x) - (-maxint - 1)如果maxint是可用的。我知道由於整數和長整數的統一,這個值「失去了價值」,但這裏可能是一個可以證明有用的區域。任何人都有一個想法如何實現模擬?

+0

即使缺少'maxint',您可能很樂意假定哈希在平臺上佔用了一些底層整數類型。如果你只是想弄清楚它是32位還是64位,那麼就把任何舊事物(好吧,不是整數0)的哈希值加一下,看看答案的大小順序。假設一個好的散列函數,散列的前32位二進制數字是* all * 0的可能性可以忽略不計,因此一個散列值會告訴你該範圍。或者,犧牲1比特的散列質量,並使用'abs(hash(x))'。 – 2010-10-24 23:41:43

回答

4

散列函數通常使用全部範圍的返回值。原因是它們通常是通過位運算(移位,xoring等)構造的 - 返回值中的位全部在算法中使用。

爲什麼積極的價值觀比消極的價值觀更容易或更難?

+0

這只是一個印刷問題;我只想擺脫減號。而且,是的,負數比正數更難,這就是爲什麼他們在歷史的後期被發現/發明的原因。但我的擔心更多印刷。 – flow 2010-10-24 23:06:01

+0

如何格式化他們無符號或十六進制? – 2010-10-25 00:19:03

+0

我確實以十六進制顯示了它們,但是它們當然保留了減號,然後 – flow 2010-10-25 10:15:59

5

hash()可以返回任何整數,正如您所見,整數的大小可以隨架構而變化。這是字典排序是任意的原因之一:兩個不同平臺上的相同操作集可能會給出不同的結果,因爲沿途使用的散列可能會有所不同。

如果你正在做的是顯示快速指紋的散列,那麼只需保留一部分位。它仍然是一個有效的散列。散列函數的唯一要求是相等的值必須具有相等的散列值。之後,哈希之間的差異僅僅影響使用散列算法的算法的效率,因爲碰撞的可能性升高或降低。

因此,例如,你可以決定你想要一個8位的散列,並用得到它:

hash(x) % 100000000 

或者你可以得到一個八個字符的字母數字哈希與顯示:

md5(hash(x)).hexdigest()[:8] 
+0

如果'hash'可以返回負值,那麼'hash(x)%100000000'可以是負數。我很快查找了滿足方程x =(x // y)* y + x %% y的操作'%%',但我沒有找到它。它存在於Python中嗎? – 2010-10-25 06:57:22

+0

我想你會發現Python%運算符可以實現你想要的。 2.6文檔聲稱它滿足x ==(x/y)* y +(x%y)。但是,如果您發現負數正在爬行,您可以使用abs(hash(x))%10000000 – 2010-10-25 11:59:25

1

回答你的問題應該是:

assert(hash(100) == 100 and hash(-100) == -100) 
smallest_hash_value= -2**min(range(256), key=lambda i: hash(-2**i)) 

這取決於Python使用的事實整數本身作爲散列(除了-1)iff整數是有效的hash()結果。無論體系結構如何,算法通常應保持不變。

+0

我似乎無法理解您打算用'-2 ** min(範圍(256),鍵= lambda i:hash(-2 ** i))';謹慎解釋? – flow 2010-10-25 14:43:05

+0

@flow:這會計算出您安裝Python時可能產生的最小'hash()'結果。 – tzot 2010-10-25 15:48:05

+0

哦,哇,帶了我一點,但現在我明白了。 '256'的確可以是任何大於最大預期字數的數字,對吧? – flow 2010-10-25 16:59:01

1

所以今天我在谷歌賭場幸運,這是我發現:

(1)系統架構給定蟒是否是64或32位機器上運行可以通過

可以找到
from platform import architecture 
print(architecture()) 

從文件:「查詢關於各種結構信息的給定的可執行文件(默認爲Python解釋二進制)返回的元組(位,連鎖),其包含關於位架構和聯動格式用於信息。兩個值都以字符串的形式返回。「在我的機器上,這是('64bit', 'ELF')。答對了。

(2)最小整數 python 3中沒有sys.maxint沒有更多,但有sys.maxsize。該文檔說:「給出最大值的整型變量的類型爲Py_ssize_t可以採用,通常在32位平臺上爲2**31 - 1,在64位平臺上爲2**63 - 1。」因此,

from sys import maxsize 
assert maxsize == 2**63 - 1 

在我的機器上工作。

(3)直接回答原來的問題:「應該是減去hash()功能的最小值任何sys.maxsize報告基於這個原因,可以預期的是

def xhash(x): return hash(x) + sys.maxsize + 1 

僅會。報告值≥0「。