python 字典，可愛(ài)的字典

練習(xí)39.字典,可愛(ài)的字典

接下來(lái)我要教你另外一種讓你傷腦筋的容器型數(shù)據(jù)結(jié)構(gòu)，因?yàn)橐坏┠銓W(xué)會(huì)這種容器，你將擁有超酷的能力。這是最有用的容器：字典(dictionary)。

Python 將這種數(shù)據(jù)類(lèi)型叫做 “dict”，有的語(yǔ)言里它的名稱(chēng)是 “hash”。這兩種名字我都會(huì)用到，不過(guò)這并不重要，重要的是它們和列表的區(qū)別。你看，針對(duì)列表你可以做這樣的事情：

>>> things = ['a', 'b', 'c', 'd']
>>> print things[1]
b
>>> things[1] = 'z'
>>> print things[1]
z
>>> things
['a', 'z', 'c', 'd']

你可以使用數(shù)字作為列表的索引，也就是你可以通過(guò)數(shù)字找到列表中的元素。你現(xiàn)在應(yīng)該了解列表的這些特性，而你也應(yīng)了解，你也只能通過(guò)數(shù)字來(lái)獲取列表中的元素。

而 dict 所作的，是讓你可以通過(guò)任何東西找到元素，不只是數(shù)字。是的，字典可以將一個(gè)物件和另外一個(gè)東西關(guān)聯(lián)，不管它們的類(lèi)型是什么，我們來(lái)看看：

>>> stuff = {'name': 'Zed', 'age': 39, 'height': 6 * 12 + 2}
>>> print stuff['name']
Zed
>>> print stuff['age']
39
>>> print stuff['height']
74
>>> stuff['city'] = "San Francisco"
>>> print stuff['city']
San Francisco

你將看到除了通過(guò)數(shù)字以外，我們還可以用字符串來(lái)從字典中獲取 stuff ，我們還可以用字符串來(lái)往字典中添加元素。當(dāng)然它支持的不只有字符串，我們還可以做這樣的事情：

>>> stuff[1] = "Wow"
>>> stuff[2] = "Neato"
>>> print stuff[1]
Wow
>>> print stuff[2]
Neato
>>> stuff
{'city': 'San Francisco', 2: 'Neato', 'name': 'Zed', 1: 'Wow', 'age': 39, 'height': 74}

在這段代碼中，我使用了數(shù)字，當(dāng)我打印stuff的時(shí)候，你可以看到，不止有數(shù)字還有字符串作為字典的key。事實(shí)上，我可以使用任何東西，這么說(shuō)并不準(zhǔn)確，不過(guò)你先這么理解就行了。

當(dāng)然了，一個(gè)只能放東西進(jìn)去的字典是沒(méi)啥意思的，所以我們還要有刪除的方法，也就是使用del 這個(gè)關(guān)鍵字：

>>> del stuff['city']
>>> del stuff[1]
>>> del stuff[2]
>>> stuff
{'name': 'Zed', 'age': 36, 'height': 74}

一個(gè)字典實(shí)例

接下來(lái)我們要做一個(gè)練習(xí)，你必須非常仔細(xì)，我要求你將這個(gè)練習(xí)寫(xiě)下來(lái)，然后試著弄懂它做了些什么。注意一下這個(gè)例子中是如何對(duì)應(yīng)這些州和它們的縮寫(xiě)，以及這些縮寫(xiě)對(duì)應(yīng)的州里的城市。 記住, "映射" 是字典中的關(guān)鍵概念.

# create a mapping of state to abbreviation
states = {
    'Oregon': 'OR',
    'Florida': 'FL',
    'California': 'CA',
    'New York': 'NY',
    'Michigan': 'MI'
}

# create a basic set of states and some cities in them
cities = {
    'CA': 'San Francisco',
    'MI': 'Detroit',
    'FL': 'Jacksonville'
}

# add some more cities
cities['NY'] = 'New York'
cities['OR'] = 'Portland'

# print out some cities
print '-' * 10
print "NY State has: ", cities['NY']
print "OR State has: ", cities['OR']

# print some states
print '-' * 10
print "Michigan's abbreviation is: ", states['Michigan']
print "Florida's abbreviation is: ", states['Florida']

# do it by using the state then cities dict
print '-' * 10
print "Michigan has: ", cities[states['Michigan']]
print "Florida has: ", cities[states['Florida']]

# print every state abbreviation
print '-' * 10
for state, abbrev in states.items():
    print "%s is abbreviated %s" % (state, abbrev)

# print every city in state
print '-' * 10
for abbrev, city in cities.items():
    print "%s has the city %s" % (abbrev, city)

# now do both at the same time
print '-' * 10
for state, abbrev in states.items():
    print "%s state is abbreviated %s and has city %s" % (
        state, abbrev, cities[abbrev])

print '-' * 10
# safely get a abbreviation by state that might not be there
state = states.get('Texas')

if not state:
    print "Sorry, no Texas."

# get a city with a default value
city = cities.get('TX', 'Does Not Exist')
print "The city for the state 'TX' is: %s" % city

你看到的結(jié)果

$ python ex39.py
----------
NY State has:  New York
OR State has:  Portland
----------
Michigan's abbreviation is:  MI
Florida's abbreviation is:  FL
----------
Michigan has:  Detroit
Florida has:  Jacksonville
----------
California is abbreviated CA
Michigan is abbreviated MI
New York is abbreviated NY
Florida is abbreviated FL
Oregon is abbreviated OR
----------
FL has the city Jacksonville
CA has the city San Francisco
MI has the city Detroit
OR has the city Portland
NY has the city New York
----------
California state is abbreviated CA and has city San Francisco
Michigan state is abbreviated MI and has city Detroit
New York state is abbreviated NY and has city New York
Florida state is abbreviated FL and has city Jacksonville
Oregon state is abbreviated OR and has city Portland
----------
Sorry, no Texas.
The city for the state 'TX' is: Does Not Exist

字典能做什么

字典是另一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，和列表一樣，是編程中最常用的數(shù)據(jù)結(jié)構(gòu)之一。 字典是用來(lái)做映射或者存儲(chǔ)你需要的鍵值對(duì)，這樣當(dāng)你需要的時(shí)候，你可以通過(guò)key來(lái)獲取它的值。同樣，程序員不會(huì)使用一個(gè)像“字典”這樣的術(shù)語(yǔ)，來(lái)稱(chēng)呼那些不能像一個(gè)寫(xiě)滿(mǎn)詞匯的真實(shí)字典正常使用的事物，所以我們只要把它當(dāng)做真實(shí)世界中的字典來(lái)用就好。

假如你想知道這個(gè)單詞"Honorificabilitudinitatibus"的意思。你可以很簡(jiǎn)單的把它復(fù)制粘貼放進(jìn)任何一個(gè)搜索引擎中找到答案。我們真的可以說(shuō)一個(gè)搜索引擎就像一個(gè)巨大的超級(jí)復(fù)雜版本的《牛津英語(yǔ)詞典》(OED).在搜索引擎出現(xiàn)之前，你可能會(huì)這樣做：

1. 走進(jìn)圖書(shū)館，找到一本字典，我們稱(chēng)這本字典為OED
2. 你知道單詞"honorificabilitudinitatibus" 以字母 'H'開(kāi)頭，所以你查看字典的小標(biāo)簽，找到以 'H' 開(kāi)頭的部分.
3. 然后你會(huì)瀏覽書(shū)頁(yè)，直到找到"hon"開(kāi)頭的地方。
4. 然后你再翻過(guò)一些書(shū)頁(yè)，直到找到 "honorificabilitudinitatibus" 或者找到以 "hp" 開(kāi)頭的單詞，發(fā)現(xiàn)這個(gè)詞不在我們的字典中。
5. 當(dāng)你找到這個(gè)條目，你就可以仔細(xì)閱讀并弄明白它的意思。

這個(gè)過(guò)程跟我們?cè)诔绦蛑惺褂米值涞氖窍嗨频?，你?huì)映射（"mapping"）找到這個(gè)單詞"honorificabilitudinitatibus"的定義。Python中的字典就跟真實(shí)世界中的這本牛津詞典（OED）差不多。

定義自己的字典類(lèi)

這節(jié)練習(xí)的最后一段代碼給你演示了如何使用你剛學(xué)會(huì)的list來(lái)創(chuàng)建一個(gè)字典數(shù)據(jù)結(jié)構(gòu)。這段代碼可能有些難以理解，所以如果你要花費(fèi)你很長(zhǎng)的時(shí)間去弄明白代碼額含義也不要擔(dān)心。代碼中會(huì)有一些新的知識(shí)點(diǎn)，它確實(shí)有些復(fù)雜，還有一些事情需要你上網(wǎng)查找

為了使用Python中的dict保存數(shù)據(jù)，我打算把我的數(shù)據(jù)結(jié)構(gòu)叫做hashmap,這是字典數(shù)據(jù)結(jié)構(gòu)的另一個(gè)名字。你要把下面的代碼輸入一個(gè)叫做hashmap.py的文件，這樣我們就可以在另一個(gè)文件 ex39_test.py中執(zhí)行它。

def new(num_buckets=256):
    """Initializes a Map with the given number of buckets."""
    aMap = []
    for i in range(0, num_buckets):
        aMap.append([])
    return aMap

def hash_key(aMap, key):
    """Given a key this will create a number and then convert it to
    an index for the aMap's buckets."""
    return hash(key) % len(aMap)

def get_bucket(aMap, key):
    """Given a key, find the bucket where it would go."""
    bucket_id = hash_key(aMap, key)
    return aMap[bucket_id]

def get_slot(aMap, key, default=None):
    """
    Returns the index, key, and value of a slot found in a bucket.
    Returns -1, key, and default (None if not set) when not found.
    """
    bucket = get_bucket(aMap, key)

    for i, kv in enumerate(bucket):
        k, v = kv
        if key == k:
            return i, k, v

    return -1, key, default

def get(aMap, key, default=None):
    """Gets the value in a bucket for the given key, or the default."""
    i, k, v = get_slot(aMap, key, default=default)
    return v

def set(aMap, key, value):
    """Sets the key to the value, replacing any existing value."""
    bucket = get_bucket(aMap, key)
    i, k, v = get_slot(aMap, key)

    if i >= 0:
        # the key exists, replace it
        bucket[i] = (key, value)
    else:
        # the key does not, append to create it
        bucket.append((key, value))

def delete(aMap, key):
    """Deletes the given key from the Map."""
    bucket = get_bucket(aMap, key)

    for i in xrange(len(bucket)):
        k, v = bucket[i]
        if key == k:
            del bucket[i]
            break

def list(aMap):
    """Prints out what's in the Map."""
    for bucket in aMap:
        if bucket:
            for k, v in bucket:
                print k, v

上面的代碼創(chuàng)建了一個(gè)叫做hashmap的模塊，你需要把這個(gè)模塊import到文件 ex39_test.py 中，并讓這個(gè)文件運(yùn)行起來(lái)：

import hashmap

# create a mapping of state to abbreviation
states = hashmap.new()
hashmap.set(states, 'Oregon', 'OR')
hashmap.set(states, 'Florida', 'FL')
hashmap.set(states, 'California', 'CA')
hashmap.set(states, 'New York', 'NY')
hashmap.set(states, 'Michigan', 'MI')

# create a basic set of states and some cities in them
cities = hashmap.new()
hashmap.set(cities, 'CA', 'San Francisco')
hashmap.set(cities, 'MI', 'Detroit')
hashmap.set(cities, 'FL', 'Jacksonville')

# add some more cities
hashmap.set(cities, 'NY', 'New York')
hashmap.set(cities, 'OR', 'Portland')

# print out some cities
print '-' * 10
print "NY State has: %s" % hashmap.get(cities, 'NY')
print "OR State has: %s" % hashmap.get(cities, 'OR')

# print some states
print '-' * 10
print "Michigan's abbreviation is: %s" % hashmap.get(states, 'Michigan')
print "Florida's abbreviation is: %s" % hashmap.get(states, 'Florida')

# do it by using the state then cities dict
print '-' * 10
print "Michigan has: %s" % hashmap.get(cities, hashmap.get(states, 'Michigan'))
print "Florida has: %s" % hashmap.get(cities, hashmap.get(states, 'Florida'))

# print every state abbreviation
print '-' * 10
hashmap.list(states)

# print every city in state
print '-' * 10
hashmap.list(cities)

print '-' * 10
state = hashmap.get(states, 'Texas')

if not state:
  print "Sorry, no Texas."

# default values using ||= with the nil result
# can you do this on one line?
city = hashmap.get(cities, 'TX', 'Does Not Exist')
print "The city for the state 'TX' is: %s" % city

你應(yīng)該發(fā)現(xiàn)這段代碼跟我們?cè)谶@節(jié)開(kāi)始時(shí)寫(xiě)的代碼幾乎相同，除了它使用了你新實(shí)現(xiàn)的HashMap。通讀代碼并且確信你明白這段代碼中的每一行是如何與ex39.py中的代碼實(shí)現(xiàn)相同的功能。

代碼分析

這個(gè) hashmap 只不過(guò)是"擁有鍵值對(duì)的有插槽的列表"，用幾分鐘時(shí)間分析一下我說(shuō)的意思：

"一個(gè)列表"在 hashmap 函數(shù)中，我創(chuàng)建了一個(gè)列表變量aMap，并且用其他的列表填充了這個(gè)變量。"有插槽的列表"最開(kāi)始這個(gè)列表是空的,當(dāng)我給這個(gè)數(shù)據(jù)結(jié)構(gòu)添加鍵值對(duì)之后，它就會(huì)填充一些插槽或者其他的東西"擁有鍵值對(duì)"表示這個(gè)列表中的每個(gè)插槽都包含一個(gè)(key, value)這樣的元素或者數(shù)據(jù)對(duì)。

如果我的這個(gè)描述仍舊沒(méi)讓你弄明白是什么意思，花點(diǎn)時(shí)間在紙上畫(huà)一畫(huà)它們，直到你搞明白為止。實(shí)際上，手動(dòng)在紙上運(yùn)算是讓你弄明白它們的好辦法。

你現(xiàn)在知道數(shù)據(jù)是如何被組織起來(lái)的，你還需要知道它每個(gè)操作的算法。算法指的是你做什么事情的步驟。它是是數(shù)據(jù)結(jié)構(gòu)運(yùn)行起來(lái)的代碼。我們接下來(lái)要逐個(gè)分析下代碼中用到的操作， 下面是在 hashmap算法中一個(gè)通用的模式：

1. 把一個(gè)關(guān)鍵字轉(zhuǎn)換成整數(shù)使用哈希函數(shù): hash_key.
2. Convert this hash to a bucket number using a %(模除) 操作.
3. Get this bucket from the aMap list of buckets, and then traverse it to find the slot that contains the key we want.

操作set 實(shí)現(xiàn)以下功能,如果key值存在，則替換原有的值，不存在則創(chuàng)建一個(gè)新值。

下面我們逐個(gè)函數(shù)分析一下hashmap的代碼，讓你明白它是如何工作的。 跟我一起分析并確保你明白每一行代碼的意思。給每一行加上注釋?zhuān)_保你明白他們是做什么的。就是如此簡(jiǎn)單，我建議你對(duì)下面提到的每一行代碼都花點(diǎn)時(shí)間在Python shell或者紙上多練習(xí)練習(xí):

new首先，我以創(chuàng)建一個(gè)函數(shù)來(lái)生成一個(gè)hashmap開(kāi)始，也被稱(chēng)為初始化。 我先創(chuàng)建一個(gè)包含列表的變量，叫做aMap,然后把列表num_buckets放進(jìn)去， num_buckets用來(lái)存放我給hashmap設(shè)置的內(nèi)容。 后面我會(huì)在另一個(gè)函數(shù)中使用len(aMap) 來(lái)查找一共有多少個(gè) buckets。確信你明白我說(shuō)的。

hash_key這個(gè)看似簡(jiǎn)單的函數(shù)是一個(gè)dict如何工作的核心。它是用Python內(nèi)建的哈希函數(shù)將字符串轉(zhuǎn)換為數(shù)字。Python為自己的字典數(shù)據(jù)結(jié)構(gòu)使用此功能，而我只是復(fù)用它. 你應(yīng)該啟動(dòng)一個(gè)Python控制臺(tái)，看看它是如何工作的. 當(dāng)我拿到key對(duì)應(yīng)的數(shù)字的時(shí)候, 我使用 % (模除) 操作和 len(aMap) 來(lái)獲得一個(gè)放置這個(gè)key的位置。你應(yīng)該知道，% (模除) 操作將會(huì)返回除法操作的余數(shù)。我也可以使用這個(gè)方法來(lái)限制大數(shù)，將其固為較小的一組數(shù)字。如果你不知道我在說(shuō)什么，使用Python解析器研究一下。

get_bucket這個(gè)函數(shù)使用hash_key來(lái)找到一個(gè)key所在的“bucket”。當(dāng)我在hash_key函數(shù)中進(jìn)行%len(aMap)操作的時(shí)候，我知道無(wú)論我獲得哪一個(gè) bucket_id都會(huì)填充進(jìn) aMap 列表中. 使用 bucket_id 可以找到一個(gè)key所在的“bucket” 。

get_slot這個(gè)函數(shù)使用get_bucket來(lái)獲得一個(gè)key所在的“bucket”， 它通過(guò)查找bucket中的每一個(gè)元素來(lái)找到對(duì)應(yīng)的key。找到對(duì)應(yīng)的key之后，它會(huì)返回這樣一個(gè)元組(i, k, v)，i表示的是key的索引值，k就是key本身，v是key對(duì)應(yīng)的值。你現(xiàn)在已經(jīng)了解了足夠字典數(shù)據(jù)結(jié)構(gòu)運(yùn)行的原理。它通過(guò)keys、哈希值和模量找到一個(gè)bucket，然后搜索這個(gè)bucket，找到對(duì)應(yīng)的條目。它有效的減少了搜索次數(shù)。

get這是一個(gè)人們需要hashmap的最方便的函數(shù)。它使用get_slot來(lái)獲得 元組(i, k, v) 但是只返回v. 確定你明白這些默認(rèn)變量是如何運(yùn)行的，以及get_slot中(i, k, v) 分派給i, k, v的變量是如何獲得的。

set設(shè)置一個(gè)key/value鍵值對(duì)，并將其追加到字典中，保證以后再用到的時(shí)候可以獲取的到。但是，我希望我的hashmap每個(gè)key值存儲(chǔ)一次。為了做到這點(diǎn)， 首先，我要找到這個(gè)key是不是已經(jīng)存在，如果存在，我會(huì)替換它原來(lái)的值，如果不存在，則會(huì)追加進(jìn)來(lái)。這樣做會(huì)比簡(jiǎn)單的追加慢一些，但是更滿(mǎn)足hashmap使用者的期望。如果你允許一個(gè)key有多個(gè)value，你需要使用 get方法查閱所有的“bucket”并返回一個(gè)所有value的列表。這是平衡設(shè)計(jì)的一個(gè)很好的例子?，F(xiàn)在的版本是你可以更快速的 get, 但是會(huì)慢一些 set.

delete刪除一個(gè)key, 找到key對(duì)應(yīng)的 bucket，并將其從列表中刪除。因?yàn)槲疫x擇一個(gè)key只能對(duì)應(yīng)一個(gè)value，當(dāng)我找到一個(gè)相應(yīng)的key的時(shí)候，我就可以停止繼續(xù)查找和刪除。如果我選擇允許一個(gè)key可以對(duì)應(yīng)多個(gè)value的話，我的刪除操作也會(huì)慢一些，因?yàn)槲乙业剿衚ey對(duì)應(yīng)的value，并將其刪除。

list最后的功能僅僅是一個(gè)小小的調(diào)試功能，它能打印出hashmap 中的所有東西，并且能幫助你理解字典的細(xì)微之處。

在所有的函數(shù)之后，我有一點(diǎn)點(diǎn)的測(cè)試代碼，可以確保他們正常工作。

三級(jí)列表

正如我在討論中提到的， 由于我選擇 set 來(lái)重寫(xiě) (替換) 原有的keys，這會(huì)讓set執(zhí)行的慢一些，但是這決定能讓其他的一些函數(shù)快一些。如果我想要一個(gè)hashmap允許一個(gè)key對(duì)應(yīng)多個(gè)value，但又要求所有函數(shù)仍然執(zhí)行的很快，怎么辦

我要做的就是讓每個(gè)“bucket”中的插槽的值都是一個(gè)列表。這意味著我要給字典再增加第三級(jí)列表。這種hashmap仍然滿(mǎn)足字典的定義。我說(shuō)過(guò)， "每一個(gè)key可以有對(duì)個(gè)value"的另一種說(shuō)法就是"每一個(gè)key有一個(gè)value的列表"。

你應(yīng)該看到的結(jié)果（again）

$ python ex39_test.py
Traceback (most recent call last):
  File "ex39_test.py", line 1, in <module>
    import hashmap
ImportError: No module named hashmap

什么時(shí)候選擇字典，什么時(shí)候選擇列表

如同我在練習(xí)38中提到的，列出有特定的特性，幫助你控制和組織需要放在表結(jié)構(gòu)的東西。 字典也一樣，但是dict的特性是與列表不同的，因?yàn)樗麄兪怯面I值對(duì)映射來(lái)工作的。當(dāng)遇到下面情況的時(shí)候，可以使用字典：

1. 你要檢索的東西是以一些標(biāo)識(shí)為基礎(chǔ)的，比如名字、地址或其他一切可以作為key的東西。
2. 你不需要這些東西是有序的。詞典通常不會(huì)有序的概念，所以你必須使用一個(gè)列表。
3. 你想要通過(guò)key增刪一個(gè)元素。

也就是說(shuō)，如果你要用一個(gè)非數(shù)字的key，使用dict，如果你需要有序的東西，使用list.

附加題

1. 用自己國(guó)家的州和城市做一些類(lèi)似的映射關(guān)系
2. 在 Python 文檔中找到 dictionary 的相關(guān)的內(nèi)容，學(xué)著對(duì) dict 做更多的操作。
3. 找出一些 dict 無(wú)法做到的事情。例如比較重要的一個(gè)就是 dict 的內(nèi)容是無(wú)序的，你可以檢查一下看看是否真是這樣。
4. 閱讀python的關(guān)于斷言的功能，然后修改hashmap的代碼，給每一個(gè)測(cè)試增加一些斷言相關(guān)的代碼，替換原來(lái)的打印代碼。比如，你可以斷言第一個(gè)操作返回"Flamenco Sketches" 而不是直接打印出"Flamenco Sketches" 。
5. 有沒(méi)有注意到list方法沒(méi)有按照你增加元素的順序把它們列出來(lái)？這是字典不維持秩序的一個(gè)例子，如果你將代碼進(jìn)行分析，你就會(huì)明白為什么。
6. 像寫(xiě)list方法一樣寫(xiě)一個(gè)dump方法，實(shí)現(xiàn)備份字典內(nèi)所有內(nèi)容的功能
7. 確定你知道hash在代碼中實(shí)現(xiàn)了什么功能，它是一個(gè)特殊的函數(shù)，能將字符串轉(zhuǎn)化為整數(shù)。在網(wǎng)上找到相關(guān)文檔，了解在程序設(shè)計(jì)中，什么是哈希函數(shù)。

常見(jiàn)問(wèn)題

Q：字典和列表的區(qū)別？

list是一個(gè)有序的項(xiàng)目列表，dict是匹配一些項(xiàng)目（稱(chēng)為“鍵”）和其他項(xiàng)目（稱(chēng)為“值”）。

Q: 我怎樣使用字典？

當(dāng)你需要通過(guò)一個(gè)值來(lái)訪問(wèn)另一個(gè)值的時(shí)候，使用字典。實(shí)際上，你可以把字典稱(chēng)作“對(duì)照表”

Q: 我怎樣使用列表？

對(duì)任何需要有序的事情集合使用列表，你只需要通過(guò)他們的數(shù)值索引來(lái)訪問(wèn)它們。

Q:加入我需要一個(gè)字典，但是又需要是有序的，怎么辦？

看看python中collections.OrderedDict這個(gè)數(shù)據(jù)結(jié)構(gòu)。網(wǎng)上搜索相關(guān)的文檔。