python奇遇記：數(shù)據(jù)結(jié)構(gòu)窺探3

toddmark 發(fā)布于2019-07-30 15:06 / 974人閱讀

摘要：字典和集合都是基于散列表實(shí)現(xiàn)的，散列表也就是表，了解過(guò)數(shù)據(jù)結(jié)構(gòu)的應(yīng)該知道。而使用另一種辦法，任何鍵在找不到的情況下都會(huì)用中的值數(shù)據(jù)類型比如替換。在設(shè)計(jì)時(shí)就可以使用創(chuàng)建你的數(shù)據(jù)接口。

這次主要說(shuō)說(shuō)字典和集合這兩種數(shù)據(jù)類型。

字典和集合都是基于散列表實(shí)現(xiàn)的，散列表也就是hash表，了解過(guò)數(shù)據(jù)結(jié)構(gòu)的應(yīng)該知道。與散列表相關(guān)的一個(gè)概念叫做可散列，什么是可散列？在python官方定義中是這樣說(shuō)的：如果一個(gè)對(duì)象是可散列的，那么在這個(gè)對(duì)象的生命周期中，它的散列值是不變的，而且這個(gè)對(duì)象需要實(shí)現(xiàn)__hash__()方法。

python中，原子不可變類型(str、bytes和數(shù)值類型)都是可散列類型，同時(shí)所有的不可變類型也是可散列的。

集合

什么是集合？在數(shù)學(xué)中指的是具有某種特定性質(zhì)的事物的總體，在python中集合指許多唯一對(duì)象的聚集。注意這個(gè)唯一，也就是說(shuō)集合中不允許重復(fù)值出現(xiàn)，所以集合可以用來(lái)去重。

在python中，用大括號(hào)括起來(lái)表示一個(gè)集合。

data = [11, 11, 2, 3, 4, 4, 5, 4, 6]
set(data)

{2, 3, 4, 5, 6, 11}

將列表類型的data轉(zhuǎn)換為集合類型后，重復(fù)值被去掉了。

在數(shù)學(xué)中，集合可以求并集、交集、差集等，python也可以做同樣的事。比如：

data1 = {1, 2, 3, 4, 5}
data2 = {3, 4, 5, 6, 7}
# 交集
print(data1 & data2)
# 差集
print(data1 - data2)
# 并集
print(data1 | data2)

{3, 4, 5}
{1, 2}
{1, 2, 3, 4, 5, 6, 7}

上面說(shuō)過(guò)，集合類型用大括號(hào)表示，如果我需要?jiǎng)?chuàng)建一個(gè)空集合，是不是用{ }表示就行了？問(wèn)題來(lái)了，空集合用{ }表示，空字典也用{ }表示，這肯定不行。python中，創(chuàng)建一個(gè)空集合使用set()生成，{ }只會(huì)創(chuàng)建一個(gè)空的字典。

還有一個(gè)要提到的是集合推導(dǎo)。和列表推導(dǎo)、字典推導(dǎo)類似，這里就不講了。

字典

字典中有幾個(gè)方法需要說(shuō)一下，看個(gè)例子。

a = {"x": 1, "y": 2, "z": 3}

# a.keys()返回所有鍵的集合,a.items()返回鍵值對(duì)集合，a.values返回值集合
# 可對(duì)字典進(jìn)行集合運(yùn)算，比較大小等運(yùn)算
b = {"w" : 10,"x" : 11,"y" : 2}
# 直接進(jìn)行集合操作，a.values()不可以
print(a.keys() & b.keys())
print(a.items() & b.items())
print(a.keys() - b.keys())

{"x", "y"}
{("y", 2)}
{"z"}

在字典中，可以使用a.keys()返回所有鍵的集合,a.items()返回鍵值對(duì)集合，a.values返回值集合，既然返回的是集合，就可以使用上面集合中說(shuō)到的運(yùn)算，大大簡(jiǎn)化操作。

在查找字典中的某個(gè)鍵時(shí)，如果鍵不存在就會(huì)報(bào)錯(cuò)，影響程序運(yùn)行，為了避免不必要的麻煩，我們可以使用d.get(k, default)，給找不到的鍵一個(gè)默認(rèn)值。使用get的問(wèn)題是，它不太符合python的哲學(xué)，d[k]比d.get(k)更加直觀和簡(jiǎn)潔。

其實(shí)我們還可以這樣，使用setdefault（k, default）來(lái)指定一個(gè)默認(rèn)值，這個(gè)方法比get方法更高效，但是我們需要指定特殊的鍵。而使用另一種辦法defaultdict（），任何鍵在找不到的情況下都會(huì)用defaultdict（）中的值（數(shù)據(jù)類型比如list、str）替換。

d = {1: "a", 2: "b", 3: "c"}
d.get(4, "d")

import collections
from collections import defaultdict

d.setdefault(4, "d")
d[4]
# 如果查詢5找不到，還要指定默認(rèn)值

# 找不到的話用空字符串替換
d = defaultdict(str)

d[5]

""

第二個(gè)要說(shuō)的是OrderedDict，它可以保持字典中的順序，插入時(shí)是什么樣就是什么樣，不會(huì)改變。在設(shè)計(jì)API時(shí)就可以使用OrderDict創(chuàng)建你的數(shù)據(jù)接口。

怎么合并兩個(gè)或者多個(gè)字典？使用ChainMap，接受字典作為參數(shù)，如果參數(shù)中某個(gè)鍵重復(fù)了，ChainMap會(huì)返回第一個(gè)字典中的值，這個(gè)方法也是放在collections模塊下。

a = {"x": 1, "z": 3 }
b = {"y": 2, "z": 4 }

from collections import ChainMap
c = ChainMap(a,b)
print(c["x"])
print(c["y"])
# 只會(huì)返回第一個(gè)參數(shù)a中的z
print(c["z"])