Python mảng kết hợp là gì?

Trong khoa học máy tính, một mảng kết hợp, bản đồ, bảng ký hiệu hoặc từ điển là một kiểu dữ liệu trừu tượng lưu trữ một tập hợp các cặp [khóa, giá trị], sao cho mỗi khóa có thể xuất hiện nhiều nhất một lần trong tập hợp. Về mặt toán học, một mảng kết hợp là một hàm có miền hữu hạn. Nó hỗ trợ các thao tác 'tra cứu', 'xóa' và 'chèn'

Vấn đề từ điển là vấn đề kinh điển của việc thiết kế các cấu trúc dữ liệu hiệu quả thực hiện các mảng kết hợp. Hai giải pháp chính cho vấn đề từ điển là bảng băm và cây tìm kiếm. Trong một số trường hợp, cũng có thể giải quyết vấn đề bằng cách sử dụng mảng được đánh địa chỉ trực tiếp, cây tìm kiếm nhị phân hoặc các cấu trúc chuyên biệt hơn khác

Nhiều ngôn ngữ lập trình bao gồm các mảng kết hợp như các kiểu dữ liệu nguyên thủy và chúng có sẵn trong các thư viện phần mềm cho nhiều ngôn ngữ khác. Bộ nhớ có thể định địa chỉ nội dung là một dạng hỗ trợ cấp phần cứng trực tiếp cho các mảng kết hợp

Mảng kết hợp có nhiều ứng dụng bao gồm các mẫu lập trình cơ bản như ghi nhớ và mẫu trang trí

Tên không xuất phát từ thuộc tính kết hợp được biết đến trong toán học. Thay vào đó, nó phát sinh từ thực tế là các giá trị được liên kết với các khóa. Nó không được nhầm lẫn với

Hoạt động [ chỉnh sửa ]

Trong một mảng kết hợp, liên kết giữa khóa và giá trị thường được gọi là "ánh xạ" và cùng một từ ánh xạ cũng có thể được sử dụng để chỉ quá trình tạo liên kết mới

Các hoạt động thường được xác định cho một mảng kết hợp là

• Chèn hoặc đặt. thêm một cặp [key,value]{\displaystyle [key,value]} mới vào bộ sưu tập, ánh xạ khóa tới giá trị mới của nó. Mọi ánh xạ hiện có đều bị ghi đè. Các đối số cho thao tác này là khóa và giá trị.
• Xóa hoặc xóa. xóa một cặp [key,value]{\displaystyle [key,value]} khỏi bộ sưu tập, hủy ánh xạ một khóa nhất định khỏi giá trị của nó. Đối số cho hoạt động này là chìa khóa.
• Tra cứu, tìm hoặc nhận. tìm giá trị [nếu có] được liên kết với một khóa đã cho. Đối số của thao tác này là khóa và giá trị được trả về từ thao tác. Nếu không tìm thấy giá trị nào, một số hàm tra cứu sẽ đưa ra một ngoại lệ, trong khi những hàm khác trả về giá trị mặc định [không, null, giá trị cụ thể được truyền cho hàm tạo,. ]

Ngoài ra, mảng kết hợp cũng có thể bao gồm các thao tác khác như xác định số lượng ánh xạ hoặc xây dựng một trình vòng lặp để lặp qua tất cả các ánh xạ. Thông thường, đối với một hoạt động như vậy, thứ tự trả về ánh xạ có thể được xác định theo triển khai

Multimap tổng quát hóa một mảng kết hợp bằng cách cho phép nhiều giá trị được liên kết với một khóa duy nhất. Bản đồ hai chiều là một kiểu dữ liệu trừu tượng có liên quan trong đó các ánh xạ hoạt động theo cả hai hướng. mỗi giá trị phải được liên kết với một khóa duy nhất và thao tác tra cứu thứ hai lấy một giá trị làm đối số và tra cứu khóa được liên kết với giá trị đó

Thuộc tính[sửa]

Các hoạt động của mảng kết hợp phải đáp ứng các thuộc tính khác nhau

• lookup[k, insert[j, v, D]] = if k == j then v else lookup[k, D]
• lookup[k, new[]] = fail, trong đó fail là một ngoại lệ hoặc giá trị mặc định
• remove[k, insert[j, v, D]] = if k == j then remove[k, D] else insert[j, v, remove[k, D]]

• {
      "Pride and Prejudice": "Alice",
      "The Brothers Karamazov": "Pat",
      "Wuthering Heights": "Alice"
  }
  

  0

trong đó

{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}

{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}

{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}

{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}

{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}

Ví dụ[sửa]

Giả sử rằng tập hợp các thư viện cho mượn được biểu diễn trong một cấu trúc dữ liệu. Mỗi cuốn sách trong thư viện chỉ có thể được mượn bởi một người bảo trợ thư viện tại một thời điểm. Tuy nhiên, một người bảo trợ có thể xem nhiều sách. Do đó, thông tin về cuốn sách nào được kiểm tra đối với người bảo trợ nào có thể được biểu thị bằng một mảng kết hợp, trong đó sách là khóa và người bảo trợ là giá trị. Sử dụng ký hiệu từ Python hoặc JSON, cấu trúc dữ liệu sẽ là

{
    "Pride and Prejudice": "Alice",
    "Wuthering Heights": "Alice",
    "Great Expectations": "John"
}

Thao tác tra cứu trên khóa "Kỳ vọng lớn" sẽ trả về "John". Nếu John trả lại sách của mình, điều đó sẽ gây ra thao tác xóa và nếu Pat kiểm tra sách, điều đó sẽ gây ra thao tác chèn, dẫn đến một trạng thái khác

{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}

Thực hiện[sửa]

Đối với các từ điển có số lượng ánh xạ rất nhỏ, có thể triển khai từ điển bằng danh sách liên kết, danh sách ánh xạ được liên kết. Với cách triển khai này, thời gian để thực hiện các thao tác từ điển cơ bản là tuyến tính trong tổng số ánh xạ;

Một kỹ thuật triển khai rất đơn giản khác, có thể sử dụng khi các phím bị giới hạn trong một phạm vi hẹp, đó là đánh địa chỉ trực tiếp vào một mảng. giá trị cho một khóa k đã cho được lưu trữ tại ô mảng A[k] hoặc nếu không có ánh xạ cho k thì ô này lưu trữ một giá trị trọng điểm đặc biệt cho biết không có ánh xạ. Cũng như đơn giản, kỹ thuật này nhanh. mỗi hoạt động từ điển mất thời gian liên tục. Tuy nhiên, yêu cầu về không gian cho cấu trúc này là kích thước của toàn bộ không gian phím, khiến nó không thực tế trừ khi không gian phím nhỏ

Hai cách tiếp cận chính để triển khai từ điển là bảng băm hoặc cây tìm kiếm

Triển khai bảng băm[sửa]

Biểu đồ này so sánh số lần bỏ lỡ bộ đệm CPU trung bình cần thiết để tra cứu các phần tử trong các bảng băm lớn [vượt xa kích thước của bộ đệm] bằng thăm dò chuỗi và tuyến tính. Thăm dò tuyến tính hoạt động tốt hơn do vị trí tham chiếu tốt hơn, mặc dù khi bảng đầy, hiệu suất của nó giảm đi đáng kể

Việc thực hiện mục đích chung được sử dụng thường xuyên nhất của một mảng kết hợp là với một bảng băm. một mảng được kết hợp với hàm băm tách từng khóa thành một "nhóm" riêng của mảng. Ý tưởng cơ bản đằng sau bảng băm là việc truy cập một phần tử của mảng thông qua chỉ mục của nó là một thao tác đơn giản, liên tục. Do đó, chi phí hoạt động trung bình của một thao tác đối với bảng băm chỉ là tính toán hàm băm của khóa, kết hợp với việc truy cập nhóm tương ứng trong mảng. Như vậy, các bảng băm thường hoạt động trong thời gian O[1] và vượt trội so với các lựa chọn thay thế trong hầu hết các trường hợp

Các bảng băm cần có khả năng xử lý các va chạm. khi hàm băm ánh xạ hai khóa khác nhau vào cùng một nhóm của mảng. Hai cách tiếp cận phổ biến nhất cho vấn đề này là chuỗi riêng biệt và địa chỉ mở. Trong chuỗi riêng biệt, mảng không lưu trữ giá trị mà lưu trữ một con trỏ tới vùng chứa khác, thường là danh sách liên kết, lưu trữ tất cả các giá trị khớp với hàm băm. Mặt khác, trong địa chỉ mở, nếu tìm thấy xung đột hàm băm, thì bảng sẽ tìm kiếm một vị trí trống trong một mảng để lưu trữ giá trị theo cách xác định, thường bằng cách xem vị trí ngay lập tức tiếp theo trong mảng

Địa chỉ mở có tỷ lệ bỏ lỡ bộ đệm thấp hơn so với chuỗi riêng biệt khi bảng gần như trống. Tuy nhiên, khi bảng trở nên chứa nhiều phần tử hơn, hiệu suất của địa chỉ mở sẽ giảm theo cấp số nhân. Ngoài ra, chuỗi riêng biệt sử dụng ít bộ nhớ hơn trong hầu hết các trường hợp, trừ khi các mục rất nhỏ [nhỏ hơn bốn lần kích thước của một con trỏ]

Triển khai cây[sửa]

Cây tìm kiếm nhị phân tự cân bằng[sửa | sửa mã nguồn]

Một cách tiếp cận phổ biến khác là triển khai một mảng kết hợp với cây tìm kiếm nhị phân tự cân bằng, chẳng hạn như cây AVL hoặc cây đỏ đen

So với bảng băm, các cấu trúc này có cả ưu điểm và nhược điểm. Hiệu suất trong trường hợp xấu nhất của cây tìm kiếm nhị phân tự cân bằng tốt hơn đáng kể so với hiệu suất của bảng băm, với độ phức tạp về thời gian trong ký hiệu O lớn của O[log n]. Điều này trái ngược với bảng băm, có hiệu suất trong trường hợp xấu nhất liên quan đến tất cả các phần tử chia sẻ một nhóm duy nhất, dẫn đến độ phức tạp về thời gian O[n]. Ngoài ra, giống như tất cả các cây tìm kiếm nhị phân, cây tìm kiếm nhị phân tự cân bằng giữ các phần tử của chúng theo thứ tự. Do đó, duyệt qua các phần tử của nó tuân theo mẫu từ nhỏ nhất đến lớn nhất, trong khi duyệt qua bảng băm có thể dẫn đến các phần tử theo thứ tự dường như ngẫu nhiên. Bởi vì chúng theo thứ tự, bản đồ dựa trên cây cũng có thể đáp ứng các truy vấn phạm vi [tìm tất cả các giá trị giữa hai giới hạn] trong đó bản đồ băm chỉ có thể tìm thấy các giá trị chính xác. Tuy nhiên, bảng băm có độ phức tạp thời gian trong trường hợp trung bình tốt hơn nhiều so với cây tìm kiếm nhị phân tự cân bằng O[1] và hiệu suất trong trường hợp xấu nhất của chúng rất khó xảy ra khi sử dụng hàm băm tốt

Điều đáng chú ý là cây tìm kiếm nhị phân tự cân bằng có thể được sử dụng để triển khai các nhóm cho bảng băm sử dụng chuỗi riêng biệt. Điều này cho phép tra cứu liên tục trong trường hợp trung bình, nhưng đảm bảo hiệu suất trong trường hợp xấu nhất là O[log n]. Tuy nhiên, điều này tạo ra sự phức tạp hơn trong việc triển khai và có thể gây ra hiệu suất thậm chí còn kém hơn đối với các bảng băm nhỏ hơn, trong đó thời gian dành cho việc chèn và cân bằng cây lớn hơn thời gian cần thiết để thực hiện tìm kiếm tuyến tính trên tất cả các phần tử của một liên kết.

Các cây khác[sửa]

Các mảng kết hợp cũng có thể được lưu trữ trong các cây tìm kiếm nhị phân không cân bằng hoặc trong các cấu trúc dữ liệu dành riêng cho một loại khóa cụ thể, chẳng hạn như cây cơ số, các lần thử, mảng Judy hoặc cây van Emde Boas, mặc dù khả năng của các phương thức triển khai này có thể so sánh với các bảng băm . Ưu điểm của các cấu trúc thay thế này đến từ khả năng xử lý các hoạt động ngoài các hoạt động cơ bản của mảng kết hợp, chẳng hạn như tìm ánh xạ có khóa gần nhất với khóa được truy vấn, khi truy vấn không có trong tập hợp ánh xạ

So sánh[sửa]

Đặt hàng từ điển[sửa]

Định nghĩa cơ bản của từ điển không bắt buộc phải đặt hàng. Để đảm bảo thứ tự liệt kê cố định, các phiên bản có thứ tự của mảng kết hợp thường được sử dụng. Có hai ý nghĩa của một từ điển có thứ tự

• Thứ tự liệt kê luôn xác định đối với một bộ khóa nhất định bằng cách sắp xếp. Đây là trường hợp triển khai dựa trên cây, một đại diện là vùng chứa

  {
      "Pride and Prejudice": "Alice",
      "The Brothers Karamazov": "Pat",
      "Wuthering Heights": "Alice"
  }
  

  2 của C++
• Thứ tự liệt kê không phụ thuộc vào khóa và thay vào đó dựa trên thứ tự chèn. Đây là trường hợp của "từ điển có thứ tự" trong. NET Framework, LinkedHashMap của Java và Python

Ý nghĩa thứ hai của từ điển có thứ tự thường gặp hơn. Chúng có thể được thực hiện bằng cách sử dụng danh sách liên kết, bằng cách phủ một danh sách liên kết đôi lên trên một từ điển thông thường hoặc bằng cách di chuyển dữ liệu thực tế ra khỏi mảng thưa thớt [không có thứ tự] và chuyển sang một mảng có thứ tự chèn dày đặc.

Hỗ trợ ngôn ngữ[sửa]

Mảng kết hợp có thể được triển khai trong bất kỳ ngôn ngữ lập trình nào dưới dạng gói và nhiều hệ thống ngôn ngữ cung cấp chúng như một phần của thư viện chuẩn của chúng. Trong một số ngôn ngữ, chúng không chỉ được tích hợp vào hệ thống tiêu chuẩn mà còn có cú pháp đặc biệt, thường sử dụng cách đăng ký giống như mảng

Hỗ trợ cú pháp tích hợp sẵn cho các mảng kết hợp được giới thiệu vào năm 1969 bởi SNOBOL4, dưới tên "bảng". TMG cung cấp các bảng có khóa chuỗi và giá trị số nguyên. MUMPS đã tạo các mảng kết hợp đa chiều, liên tục tùy chọn, cấu trúc dữ liệu chính của nó. SETL đã hỗ trợ chúng dưới dạng một triển khai có thể có của các tập hợp và bản đồ. Hầu hết các ngôn ngữ kịch bản hiện đại, bắt đầu với AWK và bao gồm Rexx, Perl, PHP, Tcl, JavaScript, Maple, Python, Ruby, Wolfram Language, Go và Lua, đều hỗ trợ các mảng kết hợp như một loại vùng chứa chính. Trong nhiều ngôn ngữ khác, chúng có sẵn dưới dạng hàm thư viện mà không cần cú pháp đặc biệt

Trong Smalltalk, Mục tiêu-C,. NET, Python, REALbasic, Swift, VBA và Delphi chúng được gọi là từ điển; . Trong PHP, tất cả các mảng có thể được kết hợp, ngoại trừ các khóa được giới hạn ở số nguyên và chuỗi. Trong JavaScript [xem thêm JSON], tất cả các đối tượng hoạt động như các mảng kết hợp với các khóa có giá trị chuỗi, trong khi các loại Map và WeakMap lấy các đối tượng tùy ý làm khóa. Trong Lua, chúng được sử dụng làm khối xây dựng cơ bản cho mọi cấu trúc dữ liệu. Trong Visual FoxPro, chúng được gọi là Bộ sưu tập. Ngôn ngữ D cũng có hỗ trợ cho các mảng kết hợp

Lưu trữ vĩnh viễn[sửa]

Nhiều chương trình sử dụng mảng kết hợp tại một số điểm sẽ cần lưu trữ dữ liệu đó ở dạng lâu dài hơn, chẳng hạn như trong tệp máy tính. Một giải pháp phổ biến cho vấn đề này là một khái niệm tổng quát được gọi là lưu trữ hoặc tuần tự hóa, tạo ra một biểu diễn văn bản hoặc nhị phân của các đối tượng ban đầu có thể được ghi trực tiếp vào một tệp. Điều này được thực hiện phổ biến nhất trong mô hình đối tượng cơ bản, như. Net hoặc Cocoa, bao gồm các chức năng tiêu chuẩn chuyển đổi dữ liệu nội bộ thành dạng văn bản. Chương trình có thể tạo một biểu diễn văn bản hoàn chỉnh của bất kỳ nhóm đối tượng nào bằng cách gọi các phương thức này, hầu như luôn được triển khai trong lớp mảng kết hợp cơ sở

Đối với các chương trình sử dụng tập dữ liệu rất lớn, loại lưu trữ tệp riêng lẻ này không phù hợp và cần có hệ thống quản lý cơ sở dữ liệu [DB]. Một số hệ thống DB vốn lưu trữ các mảng kết hợp bằng cách tuần tự hóa dữ liệu, sau đó lưu trữ dữ liệu được tuần tự hóa đó và khóa. Các mảng riêng lẻ sau đó có thể được tải hoặc lưu từ cơ sở dữ liệu bằng cách sử dụng khóa để tham chiếu đến chúng. Các kho lưu trữ khóa-giá trị này đã được sử dụng trong nhiều năm và có lịch sử lâu đời như cơ sở dữ liệu quan hệ [RDB] phổ biến hơn, nhưng việc thiếu tiêu chuẩn hóa, cùng với các lý do khác, đã hạn chế việc sử dụng chúng ở một số vai trò thích hợp nhất định. RDB được sử dụng cho các vai trò này trong hầu hết các trường hợp, mặc dù việc lưu các đối tượng vào RDB có thể phức tạp, một vấn đề được gọi là trở kháng quan hệ đối tượng không phù hợp

Sau c. Vào năm 2010, nhu cầu về cơ sở dữ liệu hiệu suất cao phù hợp với điện toán đám mây và phù hợp hơn với cấu trúc bên trong của các chương trình sử dụng chúng đã dẫn đến sự phục hưng của thị trường lưu trữ khóa-giá trị. Các hệ thống này có thể lưu trữ và truy xuất các mảng kết hợp theo kiểu gốc, điều này có thể cải thiện đáng kể hiệu suất trong các quy trình công việc liên quan đến web phổ biến

Mảng kết hợp có nghĩa là gì?

Python có mảng kết hợp không?

Các mảng kết hợp có giống như từ điển không?

Cấu trúc của một mảng kết hợp là gì?