Đặt phím Python

Bộ và từ điển là cấu trúc dữ liệu lý tưởng được sử dụng khi dữ liệu của bạn không có thứ tự nội tại, nhưng có một đối tượng duy nhất có thể được sử dụng để tham chiếu nó (đối tượng tham chiếu thường là một chuỗi, nhưng có thể là bất kỳ loại có thể băm nào). Đối tượng tham chiếu này được gọi là “khóa”, trong khi dữ liệu là “giá trị. ” Từ điển và bộ gần như giống hệt nhau, ngoại trừ bộ không thực sự chứa giá trị. một bộ chỉ đơn giản là một tập hợp các khóa duy nhất. Như tên ngụ ý, tập hợp rất hữu ích để thực hiện các thao tác tập hợp

Ghi chú

Loại có thể băm là loại thực hiện cả chức năng ma thuật

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Mặc dù chúng ta đã thấy trong chương trước rằng chúng ta bị hạn chế, nhiều nhất là, _______0_______9 thời gian tra cứu trên danh sách/bộ dữ liệu không có thứ tự nội tại (thông qua thao tác tìm kiếm), từ điển và bộ cung cấp cho chúng ta _______4_______0 tra cứu dựa trên chỉ mục tùy ý. Ngoài ra, như danh sách/bộ dữ liệu, từ điển và bộ có thời gian chèn

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

Tuy nhiên, có một chi phí để sử dụng từ điển và bộ. Đầu tiên, chúng thường chiếm dung lượng lớn hơn trong bộ nhớ. Ngoài ra, mặc dù độ phức tạp của việc chèn/tra cứu là

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

Hãy xem một ví dụ. Giả sử chúng tôi muốn lưu trữ thông tin liên hệ của mọi người trong danh bạ điện thoại. Chúng tôi muốn lưu trữ thông tin này ở dạng giúp dễ dàng trả lời câu hỏi, "Số điện thoại của John Doe là gì?" . Với danh sách, chúng tôi sẽ lưu trữ số điện thoại và tên theo thứ tự và quét qua toàn bộ danh sách để tìm số điện thoại mà chúng tôi yêu cầu, như minh họa trong

Ví dụ 4-1. tra cứu danh bạ điện thoại với một danh sách

def find_phonenumber(phonebook, name):
    for n, p in phonebook:
        if n == name:
            return p
    return None

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
]
print "John Doe's phone number is", find_phonenumber(phonebook, "John Doe")

Ghi chú

Chúng tôi cũng có thể làm điều này bằng cách sắp xếp danh sách và sử dụng mô-đun

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Tuy nhiên, với một từ điển, chúng ta có thể chỉ cần có “chỉ mục” là tên và “giá trị” là số điện thoại, như thể hiện trong. Điều này cho phép chúng tôi chỉ cần tra cứu giá trị chúng tôi cần và nhận tham chiếu trực tiếp đến giá trị đó, thay vì phải đọc mọi giá trị trong tập dữ liệu của chúng tôi

Ví dụ 4-2. Tra cứu danh bạ điện thoại bằng từ điển

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Đối với danh bạ điện thoại lớn, sự khác biệt giữa thời gian tra cứu

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Mẹo

Tạo một tập lệnh nhân đôi hiệu suất của phương pháp list-_______4_______3 so với từ điển để tìm một số trong danh bạ điện thoại. Quy mô thời gian như thế nào khi kích thước của danh bạ điện thoại tăng lên?

Mặt khác, nếu chúng tôi muốn trả lời câu hỏi, "Có bao nhiêu tên duy nhất trong danh bạ điện thoại của tôi?" . Nhớ lại rằng một tập hợp chỉ đơn giản là một tập hợp các khóa duy nhất—đây là thuộc tính chính xác mà chúng tôi muốn thực thi trong dữ liệu của mình. Điều này hoàn toàn trái ngược với cách tiếp cận dựa trên danh sách, trong đó thuộc tính đó cần được thực thi tách biệt khỏi cấu trúc dữ liệu bằng cách so sánh tất cả các tên với tất cả các tên khác. minh họa

Ví dụ 4-3. Tìm tên duy nhất với danh sách và tập hợp

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

Chúng tôi phải xem qua tất cả các mục trong danh bạ điện thoại của mình và do đó vòng lặp này có giá

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

Ở đây, chúng ta phải kiểm tra tên hiện tại với tất cả các tên duy nhất mà chúng ta đã thấy. Nếu đó là một tên duy nhất mới, chúng tôi sẽ thêm nó vào danh sách các tên duy nhất của chúng tôi. Sau đó, chúng tôi tiếp tục thông qua danh sách, thực hiện bước này cho mọi mục trong danh bạ điện thoại

Đối với phương thức set, thay vì lặp lại tất cả các tên duy nhất mà chúng ta đã thấy, chúng ta chỉ cần thêm tên hiện tại vào tập hợp các tên duy nhất của mình. Vì các bộ đảm bảo tính duy nhất của các khóa mà chúng chứa, nên nếu bạn cố gắng thêm một mục đã có trong bộ, thì mục đó sẽ không được thêm vào. Hơn nữa, chi phí hoạt động này

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

Vòng lặp bên trong của thuật toán danh sách lặp lại trên

>>> %timeit list_unique_names(large_phonebook)
1 loops, best of 3: 2.56 s per loop

>>> %timeit set_unique_names(large_phonebook)
100 loops, best of 3: 9.57 ms per loop

>>> %timeit list_unique_names(large_phonebook)
1 loops, best of 3: 2.56 s per loop

>>> %timeit set_unique_names(large_phonebook)
100 loops, best of 3: 9.57 ms per loop

>>> %timeit list_unique_names(large_phonebook)
1 loops, best of 3: 2.56 s per loop

>>> %timeit set_unique_names(large_phonebook)
100 loops, best of 3: 9.57 ms per loop

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Mặt khác, thuật toán tập hợp không có vòng lặp bên trong; . Do đó, đóng góp không liên tục duy nhất vào độ phức tạp của thuật toán này là vòng lặp qua danh bạ điện thoại, khiến thuật toán này hoạt động trong

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

Khi tính thời gian cho hai thuật toán này bằng cách sử dụng một

>>> %timeit list_unique_names(large_phonebook)
1 loops, best of 3: 2.56 s per loop

>>> %timeit set_unique_names(large_phonebook)
100 loops, best of 3: 9.57 ms per loop

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

>>> %timeit list_unique_names(large_phonebook)
1 loops, best of 3: 2.56 s per loop

>>> %timeit set_unique_names(large_phonebook)
100 loops, best of 3: 9.57 ms per loop

>>> %timeit list_unique_names(large_phonebook)
1 loops, best of 3: 2.56 s per loop

>>> %timeit set_unique_names(large_phonebook)
100 loops, best of 3: 9.57 ms per loop

Nói cách khác, thuật toán thiết lập đã cho chúng tôi tăng tốc 267 lần. Ngoài ra, khi kích thước của

>>> %timeit list_unique_names(large_phonebook)
1 loops, best of 3: 2.56 s per loop

>>> %timeit set_unique_names(large_phonebook)
100 loops, best of 3: 9.57 ms per loop

>>> %timeit list_unique_names(large_phonebook)
1 loops, best of 3: 2.56 s per loop

>>> %timeit set_unique_names(large_phonebook)
100 loops, best of 3: 9.57 ms per loop

Từ điển và Bộ hoạt động như thế nào?

Từ điển và bộ sử dụng bảng băm để đạt được tra cứu và chèn

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

Để tạo bảng băm từ đầu, chúng tôi bắt đầu với một số bộ nhớ được phân bổ, tương tự như những gì chúng tôi đã bắt đầu với mảng. Đối với một mảng, nếu chúng ta muốn chèn dữ liệu, chúng ta chỉ cần tìm nhóm nhỏ nhất chưa sử dụng và chèn dữ liệu của mình vào đó (và thay đổi kích thước nếu cần). Đối với các bảng băm, trước tiên chúng ta phải tìm ra vị trí của dữ liệu trong đoạn bộ nhớ liền kề này

Vị trí của dữ liệu mới phụ thuộc vào hai thuộc tính của dữ liệu chúng tôi đang chèn. giá trị băm của khóa và cách so sánh giá trị với các đối tượng khác. Điều này là do khi chúng ta chèn dữ liệu, khóa đầu tiên được băm và ẩn để nó biến thành một chỉ mục hiệu quả trong một mảng. [] Mặt nạ đảm bảo rằng giá trị băm, có thể lấy giá trị của bất kỳ số nguyên nào, phù hợp với số lượng nhóm được phân bổ. Vì vậy, nếu chúng tôi đã phân bổ 8 khối bộ nhớ và giá trị băm của chúng tôi là

def index_sequence(key, mask=0b111, PERTURB_SHIFT=5):
    perturb = hash(key) # 
    i = perturb & mask
    yield i
    while True:
        i = ((i << 2) + i + perturb + 1)
        perturb >>= PERTURB_SHIFT
        yield i & mask

def index_sequence(key, mask=0b111, PERTURB_SHIFT=5):
    perturb = hash(key) # 
    i = perturb & mask
    yield i
    while True:
        i = ((i << 2) + i + perturb + 1)
        perturb >>= PERTURB_SHIFT
        yield i & mask

def index_sequence(key, mask=0b111, PERTURB_SHIFT=5):
    perturb = hash(key) # 
    i = perturb & mask
    yield i
    while True:
        i = ((i << 2) + i + perturb + 1)
        perturb >>= PERTURB_SHIFT
        yield i & mask

def index_sequence(key, mask=0b111, PERTURB_SHIFT=5):
    perturb = hash(key) # 
    i = perturb & mask
    yield i
    while True:
        i = ((i << 2) + i + perturb + 1)
        perturb >>= PERTURB_SHIFT
        yield i & mask

def index_sequence(key, mask=0b111, PERTURB_SHIFT=5):
    perturb = hash(key) # 
    i = perturb & mask
    yield i
    while True:
        i = ((i << 2) + i + perturb + 1)
        perturb >>= PERTURB_SHIFT
        yield i & mask

Để tìm chỉ mục mới, chúng tôi tính toán chỉ mục mới bằng cách sử dụng một hàm tuyến tính đơn giản, một phương pháp được gọi là thăm dò. Cơ chế thăm dò của Python thêm phần đóng góp từ các bit bậc cao hơn của hàm băm ban đầu (hãy nhớ rằng đối với bảng có độ dài 8, chúng tôi chỉ xem xét 3 bit cuối cùng của hàm băm cho chỉ mục ban đầu, thông qua việc sử dụng giá trị mặt nạ là

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 4,
    City("San Francisco"): 3,
    City("New York"): 5,
    City("Barcelona"): 2,
}

Ví dụ 4-4. Trình tự tra cứu từ điển

def index_sequence(key, mask=0b111, PERTURB_SHIFT=5):
    perturb = hash(key) # 
    i = perturb & mask
    yield i
    while True:
        i = ((i << 2) + i + perturb + 1)
        perturb >>= PERTURB_SHIFT
        yield i & mask

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 4,
    City("San Francisco"): 3,
    City("New York"): 5,
    City("Barcelona"): 2,
}

Thăm dò này là một sửa đổi của phương pháp ngây thơ của “thăm dò tuyến tính. ” Trong thăm dò tuyến tính, chúng tôi chỉ đơn giản đưa ra các giá trị

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 4,
    City("San Francisco"): 3,
    City("New York"): 5,
    City("Barcelona"): 2,
}

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 4,
    City("San Francisco"): 3,
    City("New York"): 5,
    City("Barcelona"): 2,
}

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 4,
    City("San Francisco"): 3,
    City("New York"): 5,
    City("Barcelona"): 2,
}

Một quy trình tương tự được thực hiện khi chúng tôi đang thực hiện tra cứu trên một khóa cụ thể. khóa đã cho được chuyển đổi thành một chỉ mục và chỉ mục đó được kiểm tra. Nếu khóa trong chỉ mục đó khớp (hãy nhớ rằng chúng tôi cũng lưu trữ khóa gốc khi thực hiện thao tác chèn), thì chúng tôi có thể trả về giá trị đó. Nếu không, chúng tôi tiếp tục tạo các chỉ mục mới bằng cách sử dụng cùng một sơ đồ, cho đến khi chúng tôi tìm thấy dữ liệu hoặc chạm vào một thùng trống. Nếu chúng ta nhấn vào một thùng rỗng, chúng ta có thể kết luận rằng dữ liệu không tồn tại trong bảng

minh họa quá trình thêm một số dữ liệu vào bảng băm. Ở đây, chúng tôi đã chọn tạo một hàm băm chỉ sử dụng chữ cái đầu tiên của đầu vào. Chúng tôi thực hiện điều này bằng cách sử dụng hàm

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 4,
    City("San Francisco"): 3,
    City("New York"): 5,
    City("Barcelona"): 2,
}

Hình 4-1. Bảng băm kết quả từ việc chèn có va chạm

Việc chèn khóa “Barcelona” gây ra xung đột và một chỉ mục mới được tính toán bằng lược đồ trong. Từ điển này cũng có thể được tạo bằng Python bằng cách sử dụng mã trong

Ví dụ 4-5. Hàm băm tùy chỉnh

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 4,
    City("San Francisco"): 3,
    City("New York"): 5,
    City("Barcelona"): 2,
}

Trong trường hợp này, “Barcelona” và “Rome” gây ra xung đột hàm băm ( hiển thị kết quả của việc chèn này). Chúng tôi thấy điều này bởi vì đối với một từ điển có bốn phần tử, chúng tôi có giá trị mặt nạ là

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 4,
    City("San Francisco"): 3,
    City("New York"): 5,
    City("Barcelona"): 2,
}

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 4,
    City("San Francisco"): 3,
    City("New York"): 5,
    City("Barcelona"): 2,
}

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 4,
    City("San Francisco"): 3,
    City("New York"): 5,
    City("Barcelona"): 2,
}

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 4,
    City("San Francisco"): 3,
    City("New York"): 5,
    City("Barcelona"): 2,
}

Mẹo

Làm việc thông qua các vấn đề sau. Một cuộc thảo luận về va chạm băm sau

1. Tìm phần tử—Sử dụng từ điển được tạo trong , tra cứu trên khóa “Johannesburg” sẽ như thế nào?
2. Xóa một phần tử—Sử dụng từ điển được tạo trong , bạn sẽ xử lý việc xóa khóa “Rome” như thế nào?
3. Xung đột băm—Xem xét từ điển được tạo trong , bạn có thể mong đợi bao nhiêu xung đột băm nếu 500 thành phố, với tên tất cả bắt đầu bằng một chữ cái viết hoa, được thêm vào bảng băm?

Đối với 500 thành phố, sẽ có khoảng 474 phần tử từ điển xung đột với giá trị trước đó (500–26), với mỗi hàm băm có 500/26 = 19. 2 thành phố liên kết với nó. Đối với 1.000 thành phố, 974 phần tử sẽ xung đột và mỗi hàm băm sẽ có 1.000/26 = 38. 4 thành phố liên kết với nó. Điều này là do hàm băm chỉ đơn giản dựa trên giá trị số của chữ cái đầu tiên, chỉ có thể nhận giá trị từ

8, 32, 128, 512, 2048, 8192, 32768, 131072, 262144, ...

8, 32, 128, 512, 2048, 8192, 32768, 131072, 262144, ...

Khi một giá trị bị xóa khỏi bảng băm, chúng ta không thể chỉ ghi một

8, 32, 128, 512, 2048, 8192, 32768, 131072, 262144, ...

8, 32, 128, 512, 2048, 8192, 32768, 131072, 262144, ...

Khi nhiều mục được chèn vào bảng băm, bảng phải được thay đổi kích thước để phù hợp với nó. Có thể chỉ ra rằng một bảng không đầy quá hai phần ba sẽ tiết kiệm không gian tối ưu trong khi vẫn có giới hạn tốt về số lần va chạm mong đợi. Do đó, khi một bảng đạt đến điểm tới hạn này, nó sẽ phát triển. Để làm điều này, một bảng lớn hơn được phân bổ (i. e. , nhiều bộ chứa hơn trong bộ nhớ được dành riêng), mặt nạ được điều chỉnh để phù hợp với bảng mới và tất cả các phần tử của bảng cũ được chèn lại vào bảng mới. Điều này yêu cầu tính toán lại các chỉ số, vì mặt nạ đã thay đổi sẽ thay đổi chỉ mục kết quả. Do đó, việc thay đổi kích thước các bảng băm lớn có thể khá tốn kém. Tuy nhiên, vì chúng tôi chỉ thực hiện thao tác thay đổi kích thước này khi bảng quá nhỏ, trái ngược với mỗi lần chèn, nên chi phí phân bổ của một lần chèn vẫn là

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

Theo mặc định, kích thước nhỏ nhất của từ điển hoặc bộ là 8 (nghĩa là nếu bạn chỉ lưu trữ ba giá trị, Python vẫn sẽ phân bổ tám phần tử). Khi thay đổi kích thước, số lượng nhóm tăng gấp 4 lần cho đến khi chúng tôi đạt 50.000 phần tử, sau đó kích thước tăng gấp 2 lần. Điều này mang lại các kích thước có thể sau đây

8, 32, 128, 512, 2048, 8192, 32768, 131072, 262144, ...

Điều quan trọng cần lưu ý là việc thay đổi kích thước có thể xảy ra để làm cho bảng băm lớn hơn hoặc nhỏ hơn. Nghĩa là, nếu đủ nhiều phần tử của bảng băm bị xóa, bảng có thể được thu nhỏ kích thước. Tuy nhiên, thay đổi kích thước chỉ xảy ra trong quá trình chèn

Hàm băm và Entropy

Các đối tượng trong Python nói chung có thể băm được, vì chúng đã được tích hợp sẵn các hàm

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

8, 32, 128, 512, 2048, 8192, 32768, 131072, 262144, ...

8, 32, 128, 512, 2048, 8192, 32768, 131072, 262144, ...

Các lớp do người dùng định nghĩa cũng có các hàm so sánh và hàm băm mặc định. Hàm

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Điều này thường được chấp nhận, vì hai thể hiện của một lớp nói chung là khác nhau và không xung đột trong một bảng băm. Tuy nhiên, trong một số trường hợp, chúng tôi muốn sử dụng các đối tượng

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

Nếu chúng ta khởi tạo nhiều đối tượng

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
set([<__main__.Point at 0x1099bfc90>, <__main__.Point at 0x1099bfbd0>])
>>> Point(1,1) in set([p1, p2])
False

Chúng ta có thể khắc phục điều này bằng cách tạo một hàm băm tùy chỉnh dựa trên nội dung thực tế của đối tượng thay vì vị trí của đối tượng trong bộ nhớ. Hàm băm có thể tùy ý miễn là nó luôn cho cùng một kết quả cho cùng một đối tượng. (Cũng có những cân nhắc liên quan đến entropy của hàm băm, mà chúng ta sẽ thảo luận sau. ) Định nghĩa lại lớp

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

Điều này cho phép chúng tôi tạo các mục nhập trong một tập hợp hoặc từ điển được lập chỉ mục bởi các thuộc tính của đối tượng

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Như đã đề cập ở phần trước, nơi chúng ta đã thảo luận về xung đột băm, hàm băm được chọn tùy chỉnh nên cẩn thận để phân phối đồng đều các giá trị băm để tránh xung đột. Có nhiều xung đột sẽ làm giảm hiệu suất của bảng băm. nếu hầu hết các khóa có xung đột, thì chúng ta cần phải liên tục "thăm dò" các giá trị khác, đi bộ một cách hiệu quả một phần lớn tiềm năng của từ điển để tìm khóa được đề cập. Trong trường hợp xấu nhất, khi tất cả các khóa trong từ điển xung đột với nhau, hiệu suất tra cứu trong từ điển là

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

def set_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:             # 
        first_name, last_name = name.split(" ", 1)
        unique_names.add(first_name)                # 
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

print "Number of unique names from set method:", set_unique_names(phonebook)
print "Number of unique names from list method:", list_unique_names(phonebook)

Nếu chúng tôi biết rằng chúng tôi đang lưu trữ 5.000 giá trị trong một từ điển và chúng tôi cần tạo một hàm băm cho đối tượng mà chúng tôi muốn sử dụng làm khóa, thì chúng tôi phải lưu ý rằng từ điển sẽ được lưu trữ trong một bảng băm có kích thước 32.768 và

Ý tưởng về “hàm băm của tôi được phân phối tốt như thế nào” được gọi là entropy của hàm băm. Entropy, được định nghĩa là

trong đó

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
set([<__main__.Point at 0x1099bfc90>, <__main__.Point at 0x1099bfbd0>])
>>> Point(1,1) in set([p1, p2])
False

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 4,
    City("San Francisco"): 3,
    City("New York"): 5,
    City("Barcelona"): 2,
}

Đối với một từ điển lớn vô hạn, hàm băm được sử dụng cho số nguyên là lý tưởng. Điều này là do giá trị băm của một số nguyên đơn giản là chính số nguyên đó. Đối với một từ điển lớn vô hạn, giá trị mặt nạ là vô hạn và do đó chúng tôi xem xét tất cả các bit trong giá trị băm. Do đó, với hai số bất kỳ, chúng tôi có thể đảm bảo rằng giá trị băm của chúng sẽ không giống nhau

Tuy nhiên, nếu chúng tôi làm cho từ điển này trở nên hữu hạn, thì chúng tôi không thể có sự đảm bảo này nữa. Ví dụ: đối với từ điển có bốn thành phần, mặt nạ chúng tôi sử dụng là

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 4,
    City("San Francisco"): 3,
    City("New York"): 5,
    City("Barcelona"): 2,
}

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
set([<__main__.Point at 0x1099bfc90>, <__main__.Point at 0x1099bfbd0>])
>>> Point(1,1) in set([p1, p2])
False

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
set([<__main__.Point at 0x1099bfc90>, <__main__.Point at 0x1099bfbd0>])
>>> Point(1,1) in set([p1, p2])
False

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
set([<__main__.Point at 0x1099bfc90>, <__main__.Point at 0x1099bfbd0>])
>>> Point(1,1) in set([p1, p2])
False

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
set([<__main__.Point at 0x1099bfc90>, <__main__.Point at 0x1099bfbd0>])
>>> Point(1,1) in set([p1, p2])
False

Ghi chú

Để tìm mặt nạ cho một từ điển có số lượng phần tử tùy ý,

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
set([<__main__.Point at 0x1099bfc90>, <__main__.Point at 0x1099bfbd0>])
>>> Point(1,1) in set([p1, p2])
False

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

Không có hàm băm nào tốt nhất để sử dụng khi sử dụng từ điển hữu hạn. Tuy nhiên, biết trước phạm vi giá trị nào sẽ được sử dụng và độ lớn của từ điển sẽ giúp đưa ra lựa chọn tốt. Ví dụ: nếu chúng tôi đang lưu trữ tất cả 676 kết hợp của hai chữ cái viết thường làm khóa trong từ điển (aa, ab, ac, v.v. ), thì hàm băm tốt sẽ là hàm được hiển thị trong

Ví dụ 4-6. Hàm băm hai ký tự tối ưu

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Điều này không tạo ra xung đột băm đối với bất kỳ sự kết hợp nào của hai chữ cái viết thường, xem xét mặt nạ là

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

chỉ ra rất rõ ràng sự phân nhánh của việc có một hàm băm tồi đối với một lớp do người dùng định nghĩa—ở đây, chi phí của một hàm băm tồi (trên thực tế, đó là hàm băm tồi tệ nhất có thể. ) là 21. Tốc độ tra cứu chậm gấp 8 lần

Ví dụ 4-7. Sự khác biệt về thời gian giữa các hàm băm tốt và xấu

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Mẹo

1. Chỉ ra rằng đối với một từ điển vô hạn (và do đó là một mặt nạ vô hạn), sử dụng giá trị của một số nguyên làm hàm băm của nó không có xung đột
2. Chỉ ra rằng hàm băm được đưa ra là lý tưởng cho bảng băm có kích thước 1,024. Tại sao nó không lý tưởng cho các bảng băm nhỏ hơn?

Từ điển và không gian tên

Tra cứu từ điển rất nhanh; . Một khu vực mà điều này xuất hiện là trong quản lý không gian tên của Python, nơi sử dụng nhiều từ điển để thực hiện tra cứu của nó

Bất cứ khi nào một biến, hàm hoặc mô-đun được gọi trong Python, sẽ có một hệ thống phân cấp xác định nơi nó tìm kiếm các đối tượng này. Đầu tiên, Python nhìn vào bên trong mảng

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

Để làm cho điều này rõ ràng hơn, hãy xem một ví dụ đơn giản về cách gọi các hàm được xác định trong các phạm vi khác nhau (). Chúng ta có thể phân tách các chức năng bằng mô-đun

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Ví dụ 4-8. tra cứu không gian tên

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Ví dụ 4-9. Tra cứu không gian tên được tháo rời

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Hàm đầu tiên,

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Mặt khác,

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Cuối cùng,

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Mặc dù các hiệu ứng này là một kết quả thú vị của cách quản lý các không gian tên trong Python, nhưng

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Ví dụ 4-10. Ảnh hưởng của tra cứu không gian tên chậm trong vòng lặp

phonebook = {
    "John Doe": "555-555-5555",
    "Albert Einstein" : "212-555-5555",
}
print "John Doe's phone number is", phonebook["John Doe"]

Từ điển và bộ cung cấp một cách tuyệt vời để lưu trữ dữ liệu có thể được lập chỉ mục bằng một khóa. Cách khóa này được sử dụng, thông qua hàm băm, có thể ảnh hưởng lớn đến hiệu suất kết quả của cấu trúc dữ liệu. Hơn nữa, hiểu cách hoạt động của từ điển giúp bạn hiểu rõ hơn không chỉ về cách tổ chức dữ liệu mà còn về cách tổ chức mã của bạn, vì từ điển là một phần nội tại của chức năng nội bộ của Python

Trong chương tiếp theo, chúng ta sẽ khám phá các trình tạo, cho phép chúng ta cung cấp dữ liệu cho mã với nhiều quyền kiểm soát hơn đối với thứ tự và không phải lưu trữ toàn bộ tập dữ liệu trong bộ nhớ trước. Điều này cho phép chúng tôi vượt qua nhiều rào cản có thể gặp phải khi sử dụng bất kỳ cấu trúc dữ liệu nội tại nào của Python

Khóa được đặt trong Python là gì?

Bộ có thể được sử dụng làm khóa trong Python không?

Có thể đặt khóa từ điển không?