Làm cách nào để tra cứu băm từ điển Python hoạt động?

Question

Thuật toán tra cứu từ điển Python hoạt động bên trong như thế nào?

mydi['foo'] 

Nếu từ điển có 1.000.000 cụm từ, tìm kiếm cây được thực hiện? Tôi có mong đợi hiệu suất về độ dài của chuỗi khóa hay kích thước của từ điển không? Có thể nhồi nhét mọi thứ vào một từ điển cũng tốt bằng cách viết chỉ mục tìm kiếm cây cho các chuỗi có kích thước 5 triệu?

Answer 1

Dưới đây là một số mã giả gần hơn với những gì thực sự xảy ra. Hãy tưởng tượng từ điển có thuộc tính data chứa các cặp khóa, giá trị và size là số lượng ô được phân bổ.

def lookup(d, key): 
    perturb = j = hash(key) 
    while True: 
     cell = d.data[j % d.size] 
     if cell.key is EMPTY: 
      raise IndexError 
     if cell.key is not DELETED and (cell.key is key or cell.key == key): 
      return cell.value 
     j = (5 * j) + 1 + perturb 
     perturb >>= PERTURB 

Giá trị perturb đảm bảo rằng tất cả các bit của mã băm được cuối cùng được sử dụng khi giải quyết xung đột băm nhưng một khi nó đã bị chuyển hóa thành 0 các (5*j)+1 cuối cùng sẽ chạm vào tất cả các ô trong bảng.

size luôn lớn hơn số lượng ô thực tế được sử dụng để băm được đảm bảo cuối cùng sẽ nhấn vào ô trống khi khóa không tồn tại (và thường sẽ chạm nhanh). Ngoài ra còn có một giá trị đã xóa cho một khóa để biểu thị một ô không nên chấm dứt tìm kiếm nhưng hiện không được sử dụng.

Đối với câu hỏi của bạn về độ dài của chuỗi khóa, băm chuỗi sẽ xem xét tất cả các ký tự trong chuỗi, nhưng một chuỗi cũng có trường được sử dụng để lưu trữ băm được tính. Vì vậy, nếu bạn sử dụng các chuỗi khác nhau mỗi lần để thực hiện tra cứu, độ dài chuỗi có thể có vòng bi, nhưng nếu bạn có một bộ khóa cố định và sử dụng lại các chuỗi giống nhau thì hàm băm sẽ không được tính lại sau lần đầu tiên nó được sử dụng . Python nhận được lợi ích từ điều này vì hầu hết các tra cứu tên đều liên quan đến từ điển và một bản sao của mỗi biến hoặc tên thuộc tính được lưu trữ nội bộ, vì vậy mỗi khi bạn truy cập một thuộc tính x.y có tra cứu từ điển nhưng không gọi hàm băm.

Answer 2

Như bạn đã đề cập trong tiêu đề, dicts là bảng băm. Không tìm kiếm cây nào được sử dụng. Tìm kiếm một khóa là một hoạt động gần như liên tục thời gian, bất kể kích thước của dict.

Bạn có thể tìm thấy câu trả lời cho câu hỏi này hữu ích: tra cứu How are Python's Built In Dictionaries Implemented

Answer 3

Hash không sử dụng cây. Họ sử dụng một bảng băm, và họ mất thời gian tra cứu liên tục. Họ sẽ mất nhiều không gian hơn (trung bình tôi tin gấp đôi) như một cái cây, nhưng thời gian tra cứu và chèn sẽ thắng.

Để đơn giản hóa, hãy lấy md5 khóa của bạn và sửa số đó bằng số địa chỉ bạn có và đó là nơi bạn lưu hoặc tìm cách truy xuất khóa. Cho dù tập hợp lớn đến mức nào đi chăng nữa, nó sẽ luôn luôn mất cùng một khoảng thời gian miễn là bạn không có va chạm đáng kể, mà một băm tốt sẽ tránh được.

Answer 4

Dưới đây là một lời giải thích tốt: http://wiki.python.org/moin/DictionaryKeys

Mã giả từ trên cao liên kết:

def lookup(d, key): 
    '''dictionary lookup is done in three steps: 
     1. A hash value of the key is computed using a hash function. 

     2. The hash value addresses a location in d.data which is 
      supposed to be an array of "buckets" or "collision lists" 
      which contain the (key,value) pairs. 

     3. The collision list addressed by the hash value is searched 
      sequentially until a pair is found with pair[0] == key. The 
      return value of the lookup is then pair[1]. 
    ''' 
    h = hash(key)     # step 1 
    cl = d.data[h]     # step 2 
    for pair in cl:    # step 3 
     if key == pair[0]: 
      return pair[1] 
    else: 
     raise KeyError, "Key %s not found." % key 

Answer 5

Trả lời 1: làm việc nội bộ được giải thích trong video

trả lời này 2: Không, một tìm kiếm cây không được thực hiện nếu bạn có một triệu bản ghi trong từ điển.

Trả lời 3: Vì có thể có các va chạm chính, bạn sẽ mong đợi hiệu suất về kích thước của từ điển và không theo độ dài của chuỗi khóa.

Trả lời 4: Hãy xem từ điển dưới dạng mảng (vị trí bộ nhớ liền kề), nhưng có thể có các khối trong mảng không được sử dụng. Do đó, từ điển có xu hướng lãng phí rất nhiều không gian bộ nhớ so với cây. Nhưng, đối với các từ điển hiệu suất thời gian chạy tốt hơn có thể tốt hơn cây. Các va chạm chính đôi khi có thể làm suy giảm hiệu suất. Bạn nên đọc về Nhất quán Hashing.