python中可哈希（python中可哈希的數據類型）

• 1、python字典的構成形式為
• 2、什麼是可哈希（hashable）性？
• 3、Python如何哈希字符串
• 4、Python中冷門但非常好用的內置函數
• 5、Python字典的底層實現
• 6、一文搞懂python數據類型和結構

python字典的構成形式為：字典是Python語言中唯一的映射類型。

映射類型對象里哈希值（鍵，key）和悔櫻悶指向的對象（值，value）是一對多的關係，通常被認為是可變的哈希表。

字典對象是可變的，它是一個容器類型，能存儲任意個數的Python對象，其中也可包括其他容器類型。

字典類型與序列類型的區別：

1、存取和訪問數據的方式不同。

2、序列類型使用數字類型的鍵（從序列的開始按數值順序索引）。

3、映射類型可以用其他對象類型作鍵（如：數字、字符串、元祖，一般用字符串作鍵），和序列類型的鍵不同，映射類型的鍵直接或間接的和存儲數據值相關聯。

4、映射類型中的數據是無序排列的。這和序列類型是不一樣的，序列類型是以數值序排列的。

5、映射類型用鍵直接「映射」到值。

字典是Python中最強大的數據類型之一

使用字典的注意不能允許一鍵對應多個值；鍵必須是可哈希的。

len（）返回字典的長度。

hash（）返回對象的哈希值，可以用來判斷一個對象能否用來作為字典的鍵。

dict（）工廠函數，用來創建字典頌跡。

簡要的說可哈希的數據類型，即不可變的數據結構(字符串str、元組tuple、對象集objects)。

哈希有啥作用？

它是一個將大體量數據轉化為很小數據的過程，甚至可以僅僅是一個數字，以便我們可以用在固定的時間複雜度下查詢它，所以，哈希對高效的算法和數據結構很重要。

同理，不可哈希的數據類型，即可變的數據結構 (字典dict，列表list，集合set)

字典的值可以是任意Python對象，而鍵通常是不可變的標量類型（整數、浮點型、字符串）或元組（元組中的對象必須是不可變的）。這被稱為「可哈希性」。可以用hash函數檢測一個對象是否是可哈希的（可被用作字典的鍵）：

要用列表當做鍵，一種方法是將列錶轉化為元組，只要內部元素可以被哈希，它也就可以被哈希：

Python中字符串是可哈希的，即可以作為字典的鍵或者HashTable的鍵使用。

您可以這樣子使用Python內置函數hash（散列函數）：

您也可以將字符串轉為一個集合：

總之，Python裏面有很多內置的hash功能性數據結構和函數。

Python中有許多內置函數,不像print、len那麼廣為人知,但它們的功能卻異常強大,用好了可以大大提高代碼效率，同時提升代碼的簡潔度，增強可閱讀性

Counter

collections在python官方文檔中的解釋是High-performance container datatypes，直接的中文翻譯解釋高性能容量數據類型。這個模塊實現了特定目標的容器，以提供Python標準內建容器 dict , list , set , 和 tuple 的替代選擇。在python3.10.1中它總共包含以下幾種數據類型：

容器名簡介

namedtuple() 創建命名元組子類的工廠函數

deque 類似列表(list)的容器，實現了在兩端快速添加(append)和彈出(pop)

ChainMap 類似字典(dict)的容器類，將多個映射集合到一個視圖裏面

Counter 字典的子類，提供了可哈希對象的計數功能

OrderedDict 字典的子類，保存了他們被添加的順序

defaultdict 字典的子類，提供了一個工廠函數，為字典查詢提供一個默認值

UserDict 封裝了字典對象，簡化了字典子類化

UserList 封裝了列表對象，簡化了列表子類化

UserString 封裝了字符串對象，簡化了字符串子類化

其中Counter中文意思是計數器，也就是我們常用於統計的一種數據類型，在使用Counter之後可以讓我們的代碼更加簡單易讀。Counter類繼承dict類，所以它能使用dict類裏面的方法

舉例

#統計詞頻

fruits = [‘apple’, ‘peach’, ‘apple’, ‘lemon’, ‘peach’, ‘peach’]

result = {}

for fruit in fruits:

if not result.get(fruit):

result[fruit] = 1

else:

result[fruit] += 1

print(result)

#{‘apple’: 2, ‘peach’: 3, ‘lemon’: 1}下面我們看用Counter怎麼實現：

from collections import Counter

fruits = [‘apple’, ‘peach’, ‘apple’, ‘lemon’, ‘peach’, ‘peach’]

c = Counter(fruits)

print(dict(c))

#{‘apple’: 2, ‘peach’: 3, ‘lemon’: 1}顯然代碼更加簡單了，也更容易閱讀和維護了。

elements()

返回一個迭代器，其中每個元素將重複出現計數值所指定次。元素會按首次出現的順序返回。如果一個元素的計數值小於1，elements()將會忽略它。

c = Counter(a=4, b=2, c=0, d=-2)

sorted(c.elements())

[‘a’, ‘a’, ‘a’, ‘a’, ‘b’, ‘b’]most_common([n])

返回一個列表，其中包含n個最常見的元素及出現次數，按常見程度由高到低排序。如果n被省略或為None，most_common()將返回計數器中的所有元素。計數值相等的元素按首次出現的順序排序：

Counter(‘abracadabra’).most_common(3)

[(‘a’, 5), (‘b’, 2), (‘r’, 2)]這兩個方法是Counter中最常用的方法，其他方法可以參考 python3.10.1官方文檔

實戰

Leetcode 1002.查找共用字符

給你一個字符串數組words，請你找出所有在words的每個字符串中都出現的共用字符（包括重複字符），並以數組形式返回。你可以按任意順序返回答案。

輸入：words = [“bella”, “label”, “roller”]

輸出：[“e”, “l”, “l”]

輸入：words = [“cool”, “lock”, “cook”]

輸出：[“c”, “o”]看到統計字符，典型的可以用Counter完美解決。這道題是找出字符串列表裏面每個元素都包含的字符，首先可以用Counter計算出每個元素每個字符出現的次數，依次取交集最後得出所有元素共同存在的字符，然後利用elements輸出共用字符出現的次數

class Solution:

def commonChars(self, words: List[str]) – List[str]:

from collections import Counter

ans = Counter(words[0])

for i in words[1:]:

ans = Counter(i)

return list(ans.elements())提交一下，發現83個測試用例耗時48ms，速度還是不錯的

sorted

在處理數據過程中，我們經常會用到排序操作，比如將列表、字典、元組裏面的元素正/倒排序。這時候就需要用到sorted()，它可以對任何可迭代對象進行排序，並返回列表

對列表升序操作：

a = sorted([2, 4, 3, 7, 1, 9])

print(a)

# 輸出：[1, 2, 3, 4, 7, 9]對元組倒序操作：

sorted((4,1,9,6),reverse=True)

print(a)

# 輸出：[9, 6, 4, 1]使用參數：key，根據自定義規則，按字符串長度來排序：

fruits = [‘apple’, ‘watermelon’, ‘pear’, ‘banana’]

a = sorted(fruits, key = lambda x : len(x))

print(a)

# 輸出：[‘pear’, ‘apple’, ‘banana’, ‘watermelon’]all

all() 函數用於判斷給定的可迭代參數iterable中的所有元素是否都為 TRUE，如果是返回 True，否則返回 False。元素除了是 0、空、None、False外都算True。注意：空元組、空列表返回值為True。

all([‘a’, ‘b’, ‘c’, ‘d’]) # 列表list，元素都不為空或0

True

all([‘a’, ‘b’, ”, ‘d’]) # 列表list，存在一個為空的元素

False

all([0, 1，2, 3]) # 列表list，存在一個為0的元素

False

all((‘a’, ‘b’, ‘c’, ‘d’)) # 元組tuple，元素都不為空或0

True

all((‘a’, ‘b’, ”, ‘d’)) # 元組tuple，存在一個為空的元素

False

all((0, 1, 2, 3)) # 元組tuple，存在一個為0的元素

False

all([]) # 空列表

True

all(()) # 空元組

Trueany函數正好和all函數相反：判斷一個tuple或者list是否全為空，0，False。如果全為空，0，False，則返回False；如果不全為空，則返回True。

F-strings

在python3.6.2版本中，PEP 498提出一種新型字符串格式化機制，被稱為 「字符串插值」 或者更常見的一種稱呼是F-strings，F-strings提供了一種明確且方便的方式將python表達式嵌入到字符串中來進行格式化：

s1=’Hello’

s2=’World’

print(f'{s1} {s2}!’)

# Hello World!在F-strings中我們也可以執行函數：

def power(x):

return x*x

x=4

print(f'{x} * {x} = {power(x)}’)

# 4 * 4 = 16而且F-strings的運行速度很快，比傳統的%-string和str.format()這兩種格式化方法都快得多，書寫起來也更加簡單。

本文主要講解了python幾種冷門但好用的函數，更多內容以後會陸陸續續更新~

字典是一種可變、無序容器數據結構。元素以鍵值對存在，鍵值唯一。它的特點搜索速度很快：數據量增加10000倍，搜索時間增加不到2倍；當數據量很大的時候，字典的搜索速度要比列錶快成百上千倍。

在Python中，字典是通過散列表（哈希表）實現的。字典也叫哈希數組或關聯數組，所以其本質是數組（如下圖），每個 bucket 有兩部分：一個是鍵對象的引用，一個是值對象的引用。所有 bucket 結構和大小一致，我們可以通過偏移量來讀取指定 bucket。

定義一個字典 dic = {}，假設其哈希數組長度為8。

Python會根據哈希數組的擁擠程度對其擴容。「擴容」指的是:創造更大的數組，這時候會對已經存在的鍵值對重新進行哈希取余運算保存到其它位置；一般接近 2/3 時，數組就會擴容。擴容後，偏移量的數字個數增加，如數組長度擴容到16時，可以用最右邊4位數字作為偏移量。

計算鍵對象 name 的哈希值，然後比較哈希數組對應索引內的bucket是否為空，為空返回 None ，否則計算這個bucket的鍵對象的哈希值，然後與 name 哈希值比較，相等則返回 值對象 ，否則繼續左移計算哈希值。

注意：

1.鍵必須為可哈希的，如數字、元組、字符串；自定義對象需要滿足支持hash、支持通過 __eq__() 方法檢測相等性、若 a == b 為真，則 hash(a) == hash(b) 也為真。

2.字典的內存開銷很大，以空間換時間。

3.鍵查詢速度很快，列表查詢是按順序一個個遍歷，字典則是一步到位。

4.往字典裏面添加新鍵可能導致擴容，導致哈希數組中鍵的次序變化。因此，不要在遍歷字典的同時進行字典的修改。

每次python從入門到精通都是從頭開始看，做這個學習筆記主要是為了讓自己可以省去學習數據類型和結構那幾章的時間，所以「偷懶」可以促進生產力發展……

分別是： 整數型、浮點型、複數、常量、布爾型、字符串 。其中複數基本不會使用到，可以不用太關注

分別是 列表、字典、集合和元組 ，其中最常見並且工作中經常使用到的就是列表和字段，其他兩個不常見。

02、字典

列表之外，字典可能是python中用的也比較多的數據結構了，由於字典的底層應用哈希映射，所以要求字典的所有key必須是不可變元素（可哈希對象），增刪改查操作一般都能實現O(1)複雜度，是低複雜度的必備數據結構。

03、集合

集合（set）是一個無序的不重複元素序列。

可以使用大括號 { } 或者 set() 函數創建集合，注意：創建一個空集合必須用 set() 而不是 { }，因為 { } 是用來創建一個空字典。

集合操作可能最常見於用於對列表去重，它的最大特性是各元素僅保留1次，底層也是應用了哈希函數，所以在集合中查找元素一般也可實現O(1)複雜度，同時集合的嵌套元素也要求是不可變類型（可哈希對象）

add：在集合中增加一個元素，如果元素已存在，則無實際操作

pop：不接受任何參數，堪稱是最神秘的操作，不同於列表的從尾端刪除、字典的指定鍵刪除，集合的pop操作看似是”隨機”刪除。但實際上是按照加入集合的先後順序，刪除”最早”加入的元素

除了與列表和字典中類似的增刪改操作外，集合還支持數學概念下的集合操作，如交集、並集、差集等。

04、元組

如果說列表、字典和集合都有其各自擅長應用場景的話，那麼元組可能是最沒有存在感的數據結構：它接口有限、功能單一，而且是不可變類型。一般而言，用元組解決的問題都可以用列表實現。但使用用元組時，更多在於暗示該序列為不可變類型。當然，當元組內嵌套子列表時實際上是可以對嵌套的子列表進行更改操作的。

有問題可以私信我，歡迎交流！