糾正<存儲 dict 的元素前是計算 key 的 hash 值？>

luqiuwen 發布于2019-07-30 17:52 / 2642人閱讀

摘要：前幾天發了一篇名為存儲的元素前是計算的值的文章，因缺乏相關的背景知識，導致得出了不正確的推論。反正存儲的元素前還是計算的值，但這只是散列函數中的其中一個過程或步驟。

前幾天發了一篇名為存儲 dict 的元素前是計算 key 的 hash 值？的文章，因缺乏相關的背景知識，導致得出了不正確的推論。
那篇文章的推論是

在不考慮 hash 沖突的情況下， "a" 所在內存地址的 hash 值與 "b" 所在內存地址的 hash 值之間的差值 和 "a" 的內存地址與 "b" 的內存地址之間的差值 相等，也就是說以下的等式成立才對

hash(id("a")) - hash(id("b")) == id("a") - id("b")

簡單說是：存儲 dict 的元素前計算的是 key 所在內存地址的 hash 值
上面的等式是成立的

>>> hash(id("a")) - hash(id("b")) == id("a") - id("b")
True
>>> id("a") - id("b")
1680
>>> hash(id("a")) - hash(id("b"))
1680

但是需要糾正說明的是，我上面的那個推論是錯的！

等式成立的原因

這里先說上面的等式為什么成立，因為整數的 hash 值是其本身

>>> a
1234567
>>> hash(a)
1234567

又因為內存地址是個整數，所以內存地址的 hash 值也是其本身，即和內存地址一樣的值

>>> 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")

推論錯誤的原因

如果兩個值不同，那么它們的內存地址也不同，這是正確的，但我錯誤的認為如果值相同，那么內存地址也相同。下面是一個具有相同值不同內存地址的例子

>>> c = "a-c"
>>> d = "a-c"
>>> id(c) == id(d)
False
>>> id(c)
2673720167592
>>> id(d)
2673720167704

注：上面的 c 和 d 雖然值是相同的，但它們不是同一個對象，所以內存地址不一樣

回到那個錯誤的推論：

存儲 dict 的元素前計算的是 key 所在內存地址的 hash 值

該推論成立的前提之一是：相同的 key 值的內存地址必須相同，但事實是像上面的例子一樣，相同的 key 值可以擁有不同的內存地址

假設該推論成立的話，就會導致 dict 中出現兩個相同的 key 值，但事實不是這樣的，即便內存地址不同，只要值相同就不可以同時作為 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 值

首先了解下關于 key 與其 hash 值之間的幾點事實：

相同的 key 肯定具有相同的 hash 值；

應該不用解釋，這是 hash 算法決定的；

不同的 key 也可能具有相同的 hash 值；

因為 hash 算法會將任何長度的數據轉換成一個固定長度的字符串（int 對象除外），所以可能生成的 hash 值的數量是有限的，而可用來計算 hash 值的數據量理論上是無窮的，這就造成兩個數據的 hash 值可能相同

具有相同 hash 值的 key 不一定相同；

原因正是因為不同的 key 可以具有相同的 hash 值

具有不同 hash 值的 key 肯定不同

原因正是因為相同的 key 具有相同的 hash 值；

dict 是基于哈希表的數據結構，哈希表是一塊連續的內存空間（數組），因為所存儲的 key-value 散落在不同的位置上，key-value 之間存在大量的空白空間是很常見的，所以哈希表又稱散列表。
dict 本質就是一個能利用散列函數將 key 轉化為索引的數組（散列函數+數組），散列函數的功能之一是將 key 值轉換為數組索引（dict 的 key 具有唯一性的本質是數組索引的唯一性）。在轉換的過程中，需要對 key 進行 hash 值計算，計算 hash 值的目的是為了確定 key 應該存儲在數組中的哪個位置（索引），即定位，而不是判斷兩個 key 是否相同。因為通過比較 hash 值是無法判斷兩個 key 是否相同的（參考前面的第 3 點事實），所以當 hash 值相同時，會定位到相同的表元（索引對應的元素），該表元里的 key 是否與計算的 key 相等還需要進一步判斷。

反正存儲 dict 的元素前還是計算 key 的 hash 值，但這只是散列函數中的其中一個過程或步驟。

閱讀更多

手動漢化 PyCharm 的過程

模擬登陸Github

字符圖像識別——數字字母混合

爬取貓眼實時票房數據

GPU云服務器云服務器 asp中&lt&gt的意思 python &lt&gt java &lt=&gt java&lt &gt

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/42473.html

存儲 dict 的元素前是計算 key 的 hash 值？

摘要：大多數情況下，相比計算這些不同對象類型的值，直接計算對象所在內存地址整數的值性能更高，這也就是為什么不是計算的值，而是計算所在內存地址的值閱讀更多手動漢化的過程模擬登陸字符圖像識別數字字母混合爬取貓眼實時票房數據 dict 的高性能與其存儲方式是分不開的，我們知道 dict 的存儲是基于哈希表（又稱散列表），需要計算 hash 值，那么是計算誰的 hash 值呢？是像別人說的：存儲 d...

dkzwm 2019-07-30 17:49 評論0 收藏0
Python基礎知識解答：字典詳細使用教程

　　字典作為python中一個內置的數據機構，它其實和列表是一樣的，但是它又是沒有順序的，以鍵值的方式，用來存儲數據，那么，它的使用教程是什么呢？下文給大家做個解答。　　一.什么是字典　　字典作為Python的一個內置數據結構，和列表一樣都是可變序列的，但是它是無序的，以鍵值對的方式存儲數據。　　二.創建字典　　創建字典的兩種方式，一種使用{}另一種使用內置函數dict()　#author:爪哇斗...

89542767 2022-09-16 17:01 評論0 收藏0
[零基礎學Python]字典，你還記得嗎？

摘要：字典，這個東西你現在還用嗎隨著網絡的發展，用的人越來越少了。最早的名字叫伍記小字典，但未能編纂完成。新華字典由商務印書館出版。成為迄今為止世界出版史上最高發行量的字典。也被稱為關聯數組或哈希表。字典，這個東西你現在還用嗎？隨著網絡的發展，用的人越來越少了。不少人習慣于在網上搜索，不僅有web版，乃至于已經有手機版的各種字典了。我曾經用過一本小小的《新華字典》。《新華字典》是...

galaxy_robot 2019-07-31 11:32 評論0 收藏0
共享13個非常有利的Python代碼片段

　　小伙伴們好，此篇文章主要是跟大家分享13個Python中非常有利的代碼片段，有興趣的同學們趕緊來看一下吧，對大家有所幫助得話不要忘記保存以下　　ListsSnippets　　大家從最常見的算法設計目錄剛開始　　1.把兩個目錄合拼成詞典　　假定大家在Python中有兩種目錄，我希望把它們合并為詞典方式，其中的一個目錄的項做為詞典的鍵，另外做為值。這就是在用Python編寫代碼時經常碰到的一個很常...

89542767 2022-12-29 11:15 評論0 收藏0