hash函數是根據關鍵字key計算出應該存儲地址的位置，哈希函數把key轉成哈希值來定位數據存儲的位置，是基于哈希函數建立的一種查找表，Python 中的字典就是用哈希表來實現的。本文主要介紹哈希表、映射和集合這三種數據結構以及他們在python中的用法。

哈希表-Hash table

哈希表

哈希表(Hash table)，也叫散列表，根據鍵(Key)訪問在內存儲存位置的數據，通過把鍵值映射到表中一個位置來訪問記錄，映射函數稱為散列函數或者哈希函數，根據哈希函數建立的記錄數據的表稱為哈希表（散列表）。

比如鍵值為k，對應的值放在 f(k) 的存儲位置上，這個對應關系 f 稱為散列函數，通過它來建立的表稱為散列表。

哈希碰撞

兩個不同的key值得到相同的哈希值的情況稱為哈希碰撞（Hash Collisions），也就是 f(k1) = f(k2)。哈希碰撞的解決方案有：開放尋址(Open Addressing)法、鏈地址法(Chaining)、再哈希法（Rehash）和建立一個公共溢出區。

• 開放尋址法：產生沖突后繼續尋找下一個空閑的空間（沒有被占用的存儲地址），Python使用的就是這種方法。
• 鏈地址法：散列到同一位置的元素，不繼續往下尋找，而是將所有關鍵字為同義詞的記錄存儲在同一線性鏈表中，HashMap就采用了鏈地址法。
• 再散列函數法：產生沖突后，就再來一次哈希計算，直到沒有沖突。
• 建立一個公共溢出區：也就是建兩個表，一個作為基本表，另一個是存儲和基本表發生沖突元素的溢出表。

哈希沖突的發生，往往會降低字典和集合操作的速度。因此，為了保證其高效性，字典和集合內的哈希表，通常會保證其至少留有 1/3 的剩余空間。隨著元素的不停插入，當剩余空間小于 1/3 時，Python 會重新獲取更大的內存空間，擴充哈希表。

python 字典

Python 中的字典就是典型的哈希表，是一系列由鍵（key）和值（value）配對組成的元素的集合，其中value可以是任何數據類型，且可以重復。Key不能重復并且必須是不可變（immutable）的。

在 Python3.7+版本中，字典是有序的， 3.6 之前是無序的。

創建字典

# 創建空字典
>>> mydict={}
>>> type(mydict)
<class 'dict'>
>>> mydict
{}
>>> mydict = {1:"Apple",2:"banana"}

# dict()方法創建字典
>>> mydict = dict({1:"apple",2:"banana"})
>>> mydict = dict([(1, 'apple'), (2, 'banana')])
>>> mydict
{1: 'apple', 2: 'banana'}

# fromkeys()方法
>>> seq=(1,2,3)
>>> mydict = dict.fromkeys(seq)
>>> mydict
{1: None, 2: None, 3: None}
>>> mydict = dict.fromkeys(seq,'apple')
>>> mydict
{1: 'apple', 2: 'apple', 3: 'apple'}

理論上來說，直接使用{}創建字典比dict()方法效率更高， {} 會直接調用底層C代碼。

直接使用Dict[Key] = ‘Value’的形式新增元素，可以增加任何數據類型，比如可以嵌套字典，列表等。如果key已經存在，則進行更新。

>>> mydict={}
>>> mydict[2] = 'banana'
>>> mydict
{2: 'banana'}

訪問元素

直接使用key訪問元素值，也可以使用 get(key) 方法獲取，如果鍵不存在，調用 get() 函數可以返回一個默認值

>>> mydict = {1:"apple",2:"banana"}
>>> mydict[2]
'banana'
>>> mydict.get(2)
'banana'
>>> mydict.get(3,'null')
'null'

setdefault()方法也可以用來獲取元素值，和get()方法不同的是，如果查找的key不存在，它會設置一個默認值（default=None）：

>>> mydict.setdefault(2)
'banana'
>>> mydict.setdefault(3)
>>> mydict
{1: 'apple', 2: 'banana', 3: None}

>>> mydict.setdefault(4,'orange')
'orange'
>>> mydict
{1: 'apple', 2: 'banana', 3: None, 4: 'orange'}

刪除元素

del刪除元素

>>> mydict = {1:"apple",2:"banana"}
>>> del mydict[2]
>>> mydict
{1: 'apple'}

pop方法：

>>> mydict = {1:"apple",2:"banana"}
>>> mydict.pop(2)
'banana'
>>> mydict
{1: 'apple'}
>>>

popitem()用于隨機刪除任意鍵值對

清除字典元素

>>> mydict = {1:"apple",2:"banana"}
>>> mydict.clear()
>>> mydict
{}

合并字典

>>> mydict1 = {1:"apple",2:"banana"}
>>> mydict2 = {3:"orange"}
>>> mydict1.update(mydict2)
>>> mydict1
{1: 'apple', 2: 'banana', 3: 'orange'}
>>> 
# 或者
>>> {**mydict1,**mydict2}
{1: 'apple', 2: 'banana', 3: 'orange'}

獲取字典key，value值

>>> mydict = {1:"apple",2:"banana"}
>>> mydict.keys()
dict_keys([1, 2])
>>> 
>>> mydict.values()
dict_values(['apple', 'banana'])

items()方法返回(key, value)對：

>>> mydict = {1:"apple",2:"banana"}
>>> mydict.items()
dict_items([(1, 'apple'), (2, 'banana')])

mydict = {1:"apple",2:"banana"}
for key,value in mydict.items():
	print(key)
	print(value)

python2中，has_key()可用于判斷字典是否存在某個key：

>>> mydict = {1:"apple",2:"banana"}
>>> mydict.has_key(1)

python3刪除了has_key()方法，可以使用 in 操作符來判斷：

mydict = {1:"apple",2:"banana"}
if 1 in mydict:
	print(mydict(1))

# 或者
if 1 in mydict.keys():
	print(mydict(1))

字典排序

實際應用中，通常需要對字典進行排序，一般會根據鍵或值，進行升序或降序排序：

根據字典鍵升序排序

>>> mydict = {1:"apple",3:"banana",2:"orange"}
>>> sorted(mydict.items(), key=lambda x: x[0])
[(1, 'apple'), (2, 'orange'), (3, 'banana')]

根據字典值降序排序

>>> sorted(mydict.items(), key=lambda x: x[0], reverse=True)
[(3, 'banana'), (2, 'orange'), (1, 'apple')]
>>>

判斷一個字典是否包含另一個字典

判斷mydictA是否包含mydictB

>>> mydictA = {1:"apple",3:"banana",2:"orange"}
>>> mydictB = {1:"apple"}
>>> dict(mydictB, **mydictA) == mydictA
True

映射-Map

映射和哈希表類似，也是存儲key-value對，通過鍵(Key)查找值(Value)。
JAVA 的HashMap() 和TreeMap()

• map.set(key, value)
• map.get(key)
• map.has(key)
• map.size()
• map.clear()

python 映射函數

下面介紹一下python的map()函數用法：
map() 根據提供的函數對指定序列進行映射，返回映射函數返回值的新列表。一般結合lambda匿名函數一起使用：

>>> map(lambda x: x ** 2, [1, 2, 3, 4, 5])
[1, 4, 9, 16, 25]

兩個list相加：

>>> list1 = [1, 2, 3]
>>> list2 = [4, 5, 6]  
>>> map(lambda x, y: x + y, list1, list2)
[5, 7, 9]

集合-Set

與列表(list)類似，但集合set沒有重復元素，集合沒有鍵和值的配對，是一系列無序的、唯一的元素組合。

字典和集合的內部結構都是一張哈希表，字典存儲了哈希值（hash）、鍵和值這 3 個元素，而集合的哈希表內沒有鍵和值的配對，只有單一的元素。和列表不一樣，集合不支持索引操作。

java 的HashSet()和TreeSet()

• set.add(value)
• set.delete(value)
• set.hash(value)

python集合

可以使用{ }創建集合：

>>> setA = {'apple', 'banana'}
# 或者 setA = set(["apple", "banana"])
>>> setB = {'apple', 'banana', 'orange'}

并集

>>> setA.union(setB)
set(['orange', 'apple', 'banana'])
>>> setA | setB
set(['orange', 'apple', 'banana'])

交集

>>> setA.intersection(setB)
set(['apple', 'banana'])
>>> setA & setB
set(['apple', 'banana'])
>>> 
>>> setB.intersection_update(setA)
>>> setB
{'banana', 'apple'}

isdisjoint() 方法可用于判斷兩個集合是否包含相同的元素，如果沒有返回 True。

差集

>>> setB.difference(setA)
set(['orange'])
>>> setB-setA
set(['orange'])

子集判斷

>>> setA = {'apple', 'banana'}
>>> setB = {'apple', 'banana', 'orange'}
>>> setA.issubset(setB)
True
>>> setA.issuperset(setB)
False
>>> setB.issuperset(setA)
True

對稱差集

兩個集合中不重復的元素集合

>>> setA.symmetric_difference(setB)
set(['orange'])
>>> setA ^ setB
set(['orange'])
>>> 
>>> setA.symmetric_difference_update(setB)
>>> setA
{'orange'}

增加元素

>>> setA.add("orange")
>>> setA
set(['orange', 'apple', 'banana'])

刪除元素

remove()刪除不存在的元素會報KeyError錯誤，可以使用discard()方法避免KeyError錯誤。

>>> setA = {'apple', 'banana', 'orange'}
>>> setA.remove('orange')
>>> setA
{'banana', 'apple'}
>>> 
>>> setA.remove('pear')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'pear
>>> setA.discard('pear')

pop() 方法也可以用來刪除元素，用于刪除最后一個元素，但是，集合是無序的，所以不知道到底刪除的是哪一個元素。

>>> setA = {'apple', 'banana', 'orange'}
>>> setA.pop()
'banana'
>>> setA
{'orange', 'apple'}
>>>

清空集合

>>> setA = {'apple', 'banana'}
>>> setA.clear()
>>> setA
set()

凍結集合

凍結后集合不能添加或刪除任何元素

>>> frozen_set = frozenset(['apple', 'banana'])
>>> frozen_set.add("orange")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'
>>>

集合排序

集合排序和列表、元組類似，使用 sorted(set) 方法排序：

>>> setA = {'apple', 'orange', 'banana'}
>>> sorted(setA)
['apple', 'banana', 'orange']

python集合運算

python集合支持以下運算：
1、in ，not in

>>> setA = {'apple', 'banana'}
>>> setB = {'apple', 'banana', 'orange'}
>>> 'apple' in setA
True
>>>

2、==，!=

>>> setA = {'apple', 'banana'}
>>> setB = {'apple', 'banana'}
>>> setA == setB
True
>>>

3、<=，<
setA <= setB：setA是setB的子集
setA < setB：setA是setB的真子集

>>> setA = {'apple', 'banana'}
>>> setB = {'apple', 'banana'}
>>> setA <= setB
True
>>> setA < setB
False
>>> setB = {'apple', 'banana', 'orange'}
>>> setA < setB
True

4、>=，>
setA >= setB：setA是setB的超集
setA > setB：setA是setB的真超集

>>> setA = {'apple', 'banana'}
>>> setB = {'apple', 'banana'}
>>> setA >= setB
True
>>> setA > setB
False
>>> setA = {'apple', 'banana', 'orange'}
>>> setA > setB
True

前面提到過，還支持:

• |：并集
• &：交集
• -：差集
• ^：對稱差集

python集合特點

python集合有以下特點：
1、集合不按特定順序保存元素，是無序的，不支持索引操作，集合本質上是一個哈希表，可以將集合轉換為list后進行索引操作，也可以使用in 關鍵字。

setA = {'apple', 'banana'}
for fru in setA:
    print(fru, end="n")

輸出

banana
apple

2、python集合只能添加不可變（immutable）的實例，比如可以添加元組（tuple），字符串（string），不能添加列表（list），如果添加的元素為list，可以使用update方法，update方法用于新增多個元素。

>>> a=(1,2)
>>> setA.add(a)
>>> setA
{(1, 2), 'bapple', 'anana'}
>>> 
>>> b=[1,2]
>>> setA.add(b)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> setA.update(b)
>>> setA
{(1, 2), 1, 2, 'bapple', 'anana'}
>>>

復雜度分析

相比于數組，列表和元組，哈希表和集合的性能更優，特別是對于查找、添加和刪除操作，字典都能在常數時間復雜度內完成。對于查找，數組的時間復雜度為 O(n)，如果使用二分查找，也需要 O(logn) 的時間復雜度，但需要對數組進行排序，至少需要O(nlogn) 的時間復雜度。

http://www.bigocheatsheet.com/

--THE END--