python 字典，可愛的字典

練習39.字典,可愛的字典

接下來我要教你另外一種讓你傷腦筋的容器型數據結構，因為一旦你學會這種容器，你將擁有超酷的能力。這是最有用的容器：字典(dictionary)。

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

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

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

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

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

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

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

在這段代碼中，我使用了數字，當我打印stuff的時候，你可以看到，不止有數字還有字符串作為字典的key。事實上，我可以使用任何東西，這么說并不準確，不過你先這么理解就行了。

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

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

一個字典實例

接下來我們要做一個練習，你必須非常仔細，我要求你將這個練習寫下來，然后試著弄懂它做了些什么。注意一下這個例子中是如何對應這些州和它們的縮寫，以及這些縮寫對應的州里的城市。 記住, "映射" 是字典中的關鍵概念.

# 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

你看到的結果

$ 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

字典能做什么

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

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

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

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

定義自己的字典類

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

為了使用Python中的dict保存數據，我打算把我的數據結構叫做hashmap,這是字典數據結構的另一個名字。你要把下面的代碼輸入一個叫做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 中，并讓這個文件運行起來：

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

你應該發(fā)現這段代碼跟我們在這節(jié)開始時寫的代碼幾乎相同，除了它使用了你新實現的HashMap。通讀代碼并且確信你明白這段代碼中的每一行是如何與ex39.py中的代碼實現相同的功能。

代碼分析

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

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

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

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

1. 把一個關鍵字轉換成整數使用哈希函數: 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 實現以下功能,如果key值存在，則替換原有的值，不存在則創(chuàng)建一個新值。

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

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

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

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

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

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

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

delete刪除一個key, 找到key對應的 bucket，并將其從列表中刪除。因為我選擇一個key只能對應一個value，當我找到一個相應的key的時候，我就可以停止繼續(xù)查找和刪除。如果我選擇允許一個key可以對應多個value的話，我的刪除操作也會慢一些，因為我要找到所有key對應的value，并將其刪除。

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

在所有的函數之后，我有一點點的測試代碼，可以確保他們正常工作。

三級列表

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

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

你應該看到的結果（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

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

如同我在練習38中提到的，列出有特定的特性，幫助你控制和組織需要放在表結構的東西。 字典也一樣，但是dict的特性是與列表不同的，因為他們是用鍵值對映射來工作的。當遇到下面情況的時候，可以使用字典：

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

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

附加題

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

常見問題

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

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

Q: 我怎樣使用字典？

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

Q: 我怎樣使用列表？

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

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

看看python中collections.OrderedDict這個數據結構。網上搜索相關的文檔。