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

dkzwm 發布于2019-07-30 17:49 / 1665人閱讀

摘要：大多數情況下，相比計算這些不同對象類型的值，直接計算對象所在內存地址整數的值性能更高，這也就是為什么不是計算的值，而是計算所在內存地址的值閱讀更多手動漢化的過程模擬登陸字符圖像識別數字字母混合爬取貓眼實時票房數據

dict 的高性能與其存儲方式是分不開的，我們知道 dict 的存儲是基于哈希表（又稱散列表），需要計算 hash 值，那么是計算誰的 hash 值呢？是像別人說的：存儲 dict 元素前計算 key 的 hash 值？

驗證

這里先創建個字典

>>> my_dict = {"a": "apple", "b": "banana"}

由于哈希表是一塊連續的內存空間（數組），在不考慮 hash 值沖突的情況下，如果計算的是 key 的 hash 值，那么："a" 的 hash 值與 "b" 的 hash 值之間的差值與 "a" 的內存地址與 "b" 的內存地址之間的差值（可理解為內存地址里的距離）相等才對，也就是說以下的等式成立才對

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

但事實上面等式返回的是 False

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

先看看其中各項的具體值是多少

>>> hash("a")
-7336862871683211644
>>> hash("b")
3607308758832868774
>>> id("a")
1290454097736
>>> id("b")
1290454096056

>>> id("a") - id("b")
1680
>>> hash("a") - hash("b")
-10944171630516080418

可以很明顯得看到差距還是挺大的
這說明計算的不是 key 的 hash 值（這種說法不夠嚴謹），那計算的是什么呢？

計算的是 key 所在內存地址的 hash 值

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

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

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

下面再多驗證幾個

>>> my_dict["c"] = "cherry"
>>> hash(id("b")) - hash(id("c")) == id("b") - id("c")
True
>>> id("b") - id("c")
791760
>>> hash(id("b")) - hash(id("c"))
791760

>>> a["d"] = "date"
>>> hash(id("d")) - hash(id("c")) == id("d") - id("c")
True
>>> id("d") - id("c")
1400
>>> hash(id("d")) - hash(id("c"))
1400

到這里就可以證明上面的結論

為何計算的是 key 所在的內存地址的 hash 值？

比如上面的"a"（1 個字符）明顯比其所在的內存地址 1290454097736（13 個字符）要短。短的計算不是更快嗎？
記住一句話：Python 中一切皆對象，"a"是個 str 對象，1290454097736 是個 int 對象

>>> type("a")

>>> type(id("a"))

一個對象里不是僅僅存儲對應值，它還有很多屬性（含方法），來看看誰的屬性多

>>> len(dir("a"))
77
>>> len(dir(id("a")))
70

str 對象比 int 對象多 7 個屬性

它們都有個叫 __sizeof__() 的魔法方法，用于獲取當前對象所占用的內存空間大小（字節）

>>> id("a").__sizeof__()
32
>>> "a".__sizeof__()
50

從上面可以發現：雖然 "a" 看起來只有 1 個字符，但其占用的內存空間要大于其內存地址 id("a") 所占用的空間

當然這不是主要原因，Python 解釋器會將其轉換為適當的數據類型再進行 hash 計算

不過，dict 的 key 不僅僅可以是 str 對象，也可以是 int、bytes、fromzenset 等這些可哈希(hashable)對象，可哈希對象都是不可變(immutable)對象（注意：反之不一定成立，如 tuple），不可變對象內存地址不變。大多數情況下，相比計算這些不同對象類型的 hash 值，直接計算對象所在內存地址（整數）的 hash 值性能更高，這也就是為什么不是計算 key 的 hash 值，而是計算 key 所在內存地址的 hash 值

閱讀更多

手動漢化 PyCharm 的過程

模擬登陸Github

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

爬取貓眼實時票房數據

GPU云服務器云服務器獲取字符串hash值最快的hash表算法 python的key linux的key

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

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

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

摘要：前幾天發了一篇名為存儲的元素前是計算的值的文章，因缺乏相關的背景知識，導致得出了不正確的推論。反正存儲的元素前還是計算的值，但這只是散列函數中的其中一個過程或步驟。前幾天發了一篇名為存儲 dict 的元素前是計算 key 的 hash 值？的文章，因缺乏相關的背景知識，導致得出了不正確的推論。那篇文章的推論是在不考慮 hash 沖突的情況下， a 所在內存地址的 hash 值與...

luqiuwen 2019-07-30 17:52 評論0 收藏0
Python中的字典和集合

摘要：若對于關鍵字集合中的任一個關鍵字，經散列函數映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數為均勻散列函數，這就是使關鍵字經過散列函數得到一個隨機的地址，從而減少沖突。導語：本文章記錄了本人在學習Python基礎之數據結構篇的重點知識及個人心得，打算入門Python的朋友們可以來一起學習并交流。本文重點： 1、掌握常見的字典創建，查詢，判別方法；2、了解字典中的defa...

hqman 2019-07-30 16:05 評論0 收藏0
五個步驟教你理清Redis與Memcached的區別

摘要：它們都使用來做事件循環，不過是單線程的服務器也是多線程的，只不過除了主線程以外，其他線程沒有，只是會進行一些后臺存儲工作，而是多線程的。支持設置過期時間，即，但是內部并不定期檢查數據是否過期，而是客戶進程使用該數據的時候，會歡迎大家前往騰訊云+社區，獲取更多騰訊海量技術實踐干貨哦~ 本文由Super發表于云+社區專欄 memcached和redis，作為近些年最常用的緩存服務器，相...

waterc 2019-08-06 13:36 評論0 收藏0
手動漢化 PyCharm 的過程

摘要：默認是英文界面，如果想漢化它，網上有很多相關的漢化丁可以下載。 showImg(https://segmentfault.com/img/remote/1460000016400154); PyCharm 默認是英文界面，如果想漢化它，網上有很多相關的漢化?丁可以下載。我的 Pycharm 版本是 pycharm-professional-2018.2.2，這里僅簡單展示手動漢化的原...

RayKr 2019-07-30 17:51 評論0 收藏0