Hướng dẫn dùng hashtable python python
Bạn cần dictionary, map hay hash table (bảng băm) để implement một giải thuật trong chương trình của bạn? Vậy hãy tiếp tục đọc để thấy được thư viện chuẩn Python có thể giúp bạn những gì. Trong Python, dictionary (dict) là một cấu trúc dữ liệu quan trọng: Dict lưu một số tùy ý các đối tượng, mỗi đối tượng được xác định bởi một key duy nhất. Dict cũng thường được gọi là map, hashmap, lookup table hoặc associative array. Chúng cho phép tìm kiếm, thêm, xóa bất kỳ đối tượng nào gắn với một key cho trước một cách hiệu quả. Để đưa ra một lời giải thích thực tiễn hơn - danh bạ điện thoại là một ví dụ thực tế cho dict:
Python Dictionaries, Hashmaps, and Hash TablesKiểu dữ liệu trừu tượng dictionary là một trong những cấu trúc dữ liệu quan trọng và được sử dụng nhiều nhất trong khoa học máy tính. Bởi vì tính chất quan trọng này, Python đã cung cấp một bản thực thi mạnh mẽ về loại cấu trúc dữ liệu này. Python thậm chí còn cung cấp các cú pháp dễ hiểu (syntactic sugar) để làm việc với dict trong chương trình của bạn. Ví dụ, cú pháp ngoặc nhọn và dictionary comprehension cho phép bạn định nghĩa các dict một cách tiện lợi:
Dict trong Python được đánh index bởi các key có kiểu dữ liệu băm được (hashable). Một hashable object có giá trị băm không bao giờ thay đổi và nó có thể được so sánh với các đối tượng khác. Hơn nữa, các hashable object bằng nhau phải có cùng giá trị băm. Các kiểu dữ liệu không thay đổi được string và number có thể dùng làm key cho dictionary. Bạn cũng có thể sử dụng các tuple làm key chỉ cần chúng chỉ chứa các kiểu dữ liệu có thể băm. Built-in dict typeTrong hầu hết các trường hợp, built-in dict sẽ đáp ứng được nhu cầu của bạn. Dict được tối ưu mạnh mẽ và làm nền tảng cho rất nhiều phần khác của ngôn ngữ, ví dụ các class attribute và class variable trong stack frame (khung stack) đều được lưu trữ nội tại trong các dict. Các Python dict cung cấp đặc tính hiệu năng mà bạn mong muốn: độ phức tạp O(1) cho các thao tác tìm kiếm, insert, update và delete. Thú vị thay, Python cung cấp cho bạn một số bản thực thi dictionary chuyên dụng trong thư viện chuẩn của nó. Các dict chuyên dụng này dựa vào bản thực thi chuẩn nhưng thêm một số tính năng. collections.OrderedDict – Remember the insertion order of keysMột subclass dictionary nhớ được thứ tự insert của các key.
collections.defaultdict – Return default values for missing keysMột subclass dictionary chấp nhận kiểu giá trị mặc định (trong constructor của nó). Giá trị phù hợp sẽ được trả về nếu key yêu cầu không được tìm thấy trong đối tượng
collections.ChainMap – Search multiple dictionaries as a single mappingCấu trúc dữ liệu này nhóm nhiều dict thành một mapping đơn. Việc tìm kiếm sẽ duyệt theo thứ tự sắp xếp của các dict. Insert, update, delete chỉ ảnh hưởng đến dict đầu tiên được thêm vào chuỗi (chain).
types.MappingProxyType – A wrapper for making read-only dictionariesClass này được dùng để tạo ra các read-only dict.
Using Dictionaries in Python: Conclusion
|