資訊專欄INFORMATION COLUMN
摘要：前幾天發(fā)了一篇名為存儲的元素前是計算的值的文章，因缺乏相關(guān)的背景知識，導(dǎo)致得出了不正確的推論。反正存儲的元素前還是計算的值，但這只是散列函數(shù)中的其中一個過程或步驟。
前幾天發(fā)了一篇名為 存儲 dict 的元素前是計算 key 的 hash 值？ 的文章，因缺乏相關(guān)的背景知識，導(dǎo)致得出了不正確的推論。
那篇文章的推論是
在不考慮 hash 沖突的情況下， "a" 所在內(nèi)存地址的 hash 值與 "b" 所在內(nèi)存地址的 hash 值之間的差值 和 "a" 的內(nèi)存地址與 "b" 的內(nèi)存地址之間的差值 相等，也就是說以下的等式成立才對
hash(id("a")) - hash(id("b")) == id("a") - id("b")
簡單說是：存儲 dict 的元素前計算的是 key 所在內(nèi)存地址的 hash 值
上面的等式是成立的
>>> hash(id("a")) - hash(id("b")) == id("a") - id("b")
True
>>> id("a") - id("b")
1680
>>> hash(id("a")) - hash(id("b"))
1680
但是需要糾正說明的是，我上面的那個推論是錯的！
等式成立的原因這里先說上面的等式為什么成立，因為整數(shù)的 hash 值是其本身
>>> a 1234567 >>> hash(a) 1234567
又因為內(nèi)存地址是個整數(shù)，所以內(nèi)存地址的 hash 值也是其本身，即和內(nèi)存地址一樣的值
>>> my_dict = {"a": "apple", "b": "banana"}
>>> hash(id("a")) == id("a")
True
>>> id("a")
2673717403464
>>> hash(id("a"))
2673717403464
這就是為什么這個等式成立
hash(id("a")) - hash(id("b")) == id("a") - id("b")
推論錯誤的原因
如果兩個值不同，那么它們的內(nèi)存地址也不同，這是正確的，但我錯誤的認為如果值相同，那么內(nèi)存地址也相同。下面是一個具有相同值不同內(nèi)存地址的例子
>>> c = "a-c" >>> d = "a-c" >>> id(c) == id(d) False >>> id(c) 2673720167592 >>> id(d) 2673720167704
注：上面的 c 和 d 雖然值是相同的，但它們不是同一個對象，所以內(nèi)存地址不一樣
回到那個錯誤的推論：
存儲 dict 的元素前計算的是 key 所在內(nèi)存地址的 hash 值
該推論成立的前提之一是：相同的 key 值的內(nèi)存地址必須相同，但事實是像上面的例子一樣，相同的 key 值可以擁有不同的內(nèi)存地址
假設(shè)該推論成立的話，就會導(dǎo)致 dict 中出現(xiàn)兩個相同的 key 值，但事實不是這樣的，即便內(nèi)存地址不同，只要值相同就不可以同時作為 dict 的 key，后者會覆蓋前者。
>>> c
"a-c"
>>> d
"a-c"
>>> {c: 0, d: 1}
{"a-c": 1}
因為相同的 key 具有相同的 hash 值
>>> hash(c) == hash(d) True >>> hash(c) -8124728931706162487 >>> hash(d) -8124728931706162487存儲 dict 的元素前是計算 key 的 hash 值
首先了解下關(guān)于 key 與其 hash 值之間的幾點事實：
相同的 key 肯定具有相同的 hash 值；
應(yīng)該不用解釋，這是 hash 算法決定的；
不同的 key 也可能具有相同的 hash 值；
因為 hash 算法會將任何長度的數(shù)據(jù)轉(zhuǎn)換成一個固定長度的字符串（int 對象除外），所以可能生成的 hash 值的數(shù)量是有限的，而可用來計算 hash 值的數(shù)據(jù)量理論上是無窮的，這就造成兩個數(shù)據(jù)的 hash 值可能相同
具有相同 hash 值的 key 不一定相同；
原因正是因為不同的 key 可以具有相同的 hash 值
具有不同 hash 值的 key 肯定不同
原因正是因為相同的 key 具有相同的 hash 值；
dict 是基于哈希表的數(shù)據(jù)結(jié)構(gòu)，哈希表是一塊連續(xù)的內(nèi)存空間（數(shù)組），因為所存儲的 key-value 散落在不同的位置上，key-value 之間存在大量的空白空間是很常見的，所以哈希表又稱散列表。
dict 本質(zhì)就是一個能利用散列函數(shù)將 key 轉(zhuǎn)化為索引的數(shù)組（散列函數(shù)+數(shù)組），散列函數(shù)的功能之一是將 key 值轉(zhuǎn)換為數(shù)組索引（dict 的 key 具有唯一性的本質(zhì)是數(shù)組索引的唯一性）。在轉(zhuǎn)換的過程中，需要對 key 進行 hash 值計算，計算 hash 值的目的是為了確定 key 應(yīng)該存儲在數(shù)組中的哪個位置（索引），即定位，而不是判斷兩個 key 是否相同。因為通過比較 hash 值是無法判斷兩個 key 是否相同的（參考前面的第 3 點事實），所以當(dāng) hash 值相同時，會定位到相同的表元（索引對應(yīng)的元素），該表元里的 key 是否與計算的 key 相等還需要進一步判斷。
反正存儲 dict 的元素前還是計算 key 的 hash 值，但這只是散列函數(shù)中的其中一個過程或步驟。
閱讀更多手動漢化 PyCharm 的過程
模擬登陸Github
字符圖像識別——數(shù)字字母混合
爬取貓眼實時票房數(shù)據(jù)
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/42473.html
摘要：大多數(shù)情況下，相比計算這些不同對象類型的值，直接計算對象所在內(nèi)存地址整數(shù)的值性能更高，這也就是為什么不是計算的值，而是計算所在內(nèi)存地址的值閱讀更多手動漢化的過程模擬登陸字符圖像識別數(shù)字字母混合爬取貓眼實時票房數(shù)據(jù) dict 的高性能與其存儲方式是分不開的，我們知道 dict 的存儲是基于哈希表（又稱散列表），需要計算 hash 值，那么是計算誰的 hash 值呢？是像別人說的：存儲 d...
字典作為python中一個內(nèi)置的數(shù)據(jù)機構(gòu)，它其實和列表是一樣的，但是它又是沒有順序的，以鍵值的方式，用來存儲數(shù)據(jù)，那么，它的使用教程是什么呢？下文給大家做個解答。 一.什么是字典 字典作為Python的一個內(nèi)置數(shù)據(jù)結(jié)構(gòu)，和列表一樣都是可變序列的，但是它是無序的，以鍵值對的方式存儲數(shù)據(jù)?！ 《?創(chuàng)建字典 創(chuàng)建字典的兩種方式，一種使用{}另一種使用內(nèi)置函數(shù)dict() #author:爪哇斗...
摘要：字典，這個東西你現(xiàn)在還用嗎隨著網(wǎng)絡(luò)的發(fā)展，用的人越來越少了。最早的名字叫伍記小字典，但未能編纂完成。新華字典由商務(wù)印書館出版。成為迄今為止世界出版史上最高發(fā)行量的字典。也被稱為關(guān)聯(lián)數(shù)組或哈希表。 字典，這個東西你現(xiàn)在還用嗎？隨著網(wǎng)絡(luò)的發(fā)展，用的人越來越少了。不少人習(xí)慣于在網(wǎng)上搜索，不僅有web版，乃至于已經(jīng)有手機版的各種字典了。我曾經(jīng)用過一本小小的《新華字典》。 《新華字典》是...
小伙伴們好，此篇文章主要是跟大家分享13個Python中非常有利的代碼片段，有興趣的同學(xué)們趕緊來看一下吧，對大家有所幫助得話不要忘記保存以下 ListsSnippets 大家從最常見的算法設(shè)計目錄剛開始 1.把兩個目錄合拼成詞典 假定大家在Python中有兩種目錄，我希望把它們合并為詞典方式，其中的一個目錄的項做為詞典的鍵，另外做為值。這就是在用Python編寫代碼時經(jīng)常碰到的一個很常...
閱讀 1819·2019-08-30 13:54
閱讀 2734·2019-08-29 17:27
閱讀 1123·2019-08-29 17:23
閱讀 3357·2019-08-29 15:20
閱讀 1234·2019-08-29 11:28
閱讀 1577·2019-08-26 10:39
閱讀 1324·2019-08-26 10:29
閱讀 649·2019-08-26 10:13
