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

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

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

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

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

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

>>> 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

你將看到除了通過數(shù)字以外，我們還可以用字符串來從字典中獲取 stuff ，我們還可以用字符串來往字典中添加元素。當(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ù)字還有字符串作為字典的key。事實(shí)上，我可以使用任何東西，這么說并不準(zhǔn)確，不過你先這么理解就行了。

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

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

一個字典實(shí)例

接下來我們要做一個練習(xí)，你必須非常仔細(xì)，我要求你將這個練習(xí)寫下來，然后試著弄懂它做了些什么。注意一下這個例子中是如何對應(yīng)這些州和它們的縮寫，以及這些縮寫對應(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

字典能做什么

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

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

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

這個過程跟我們在程序中使用字典的是相似的，你會映射（"mapping"）找到這個單詞"honorificabilitudinitatibus"的定義。Python中的字典就跟真實(shí)世界中的這本牛津詞典（OED）差不多。

定義自己的字典類

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

為了使用Python中的dict保存數(shù)據(jù)，我打算把我的數(shù)據(jù)結(jié)構(gòu)叫做hashmap,這是字典數(shù)據(jù)結(jié)構(gòu)的另一個名字。你要把下面的代碼輸入一個叫做hashmap.py的文件，這樣我們就可以在另一個文件 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)建了一個叫做hashmap的模塊，你需要把這個模塊import到文件 ex39_test.py 中，并讓這個文件運(yùn)行起來：

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)這段代碼跟我們在這節(jié)開始時寫的代碼幾乎相同，除了它使用了你新實(shí)現(xiàn)的HashMap。通讀代碼并且確信你明白這段代碼中的每一行是如何與ex39.py中的代碼實(shí)現(xiàn)相同的功能。

代碼分析

這個 hashmap 只不過是"擁有鍵值對的有插槽的列表"，用幾分鐘時間分析一下我說的意思：

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

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

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

1. 把一個關(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)建一個新值。

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

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

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

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

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

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

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

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

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

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

三級列表

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

我要做的就是讓每個“bucket”中的插槽的值都是一個列表。這意味著我要給字典再增加第三級列表。這種hashmap仍然滿足字典的定義。我說過， "每一個key可以有對個value"的另一種說法就是"每一個key有一個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

什么時候選擇字典，什么時候選擇列表

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

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

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

附加題

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

常見問題

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

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

Q: 我怎樣使用字典？

當(dāng)你需要通過一個值來訪問另一個值的時候，使用字典。實(shí)際上，你可以把字典稱作“對照表”

Q: 我怎樣使用列表？

對任何需要有序的事情集合使用列表，你只需要通過他們的數(shù)值索引來訪問它們。

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

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