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

Một mảng kết hợp, còn được gọi là bảng băm hoặc bản đồ băm, tương tự như một mảng tiêu chuẩn ngoại trừ chỉ số của mảng có thể là một chuỗi thay vì số nguyên.Trong nhiều ứng dụng cơ sở dữ liệu và trong các chương trình khác liên quan đến một lượng lớn dữ liệu, một mảng kết hợp là một yếu tố quan trọng trong việc giúp sắp xếp và truy cập thông tin một cách hiệu quả.Cốt lõi của một mảng kết hợp là một mảng tiêu chuẩn được lập chỉ mục với các số nguyên, như thường lệ.Một thuật toán đặc biệt được gọi là hàm băm chuyển đổi chỉ mục chuỗi thành một chỉ mục số nguyên để tìm giá trị.Đây là một chuyển đổi nhất quán, vì vậy chỉ số số nguyên thực tế không bao giờ cần được lưu trữ mà thay vào đó được tính toán từ chuỗi khi cầnmột mảng bình thường.Những gì thường sẽ được gọi là một chỉ mục mdash;vị trí số của một phần tử bên trong một mảng mdash;được gọi là chìa khóa.Dữ liệu được liên kết với khóa được gọi là giá trị.Điều này có nghĩa là, trong một mảng kết hợp, một khóa được liên kết với một giá trị, tương quan với một chỉ mục tham chiếu một phần tử trong một mảng tiêu chuẩn trong cấu trúc dữ liệu.

id của mỗi mảng kết hợp là hàm băm.Đây là một thuật toán được sử dụng để xác định chỉ số số của giá trị dựa trên khóa.Có một số loại hàm băm, một số được thiết kế để hoạt động trên các khóa là số nguyên và một số chức năng được thiết kế để hoạt động trên các phím là chuỗi.Trong trường hợp khóa số nguyên, phương pháp phổ biến là chia giá trị khóa cho kích thước của mảng và sử dụng phần còn lại của bộ phận để, hy vọng, nhận được giá trị chỉ mục duy nhất.Đối với các phím là chuỗi.Một số phương thức bao gồm thêm giá trị số của mỗi ký tự trong chuỗi và sau đó chia nó cho một số số hoặc chỉ sử dụng một vài ký tự đầu tiên của chuỗi để có được một số duy nhất.Có nhiều cách để lấy một số từ một chuỗi các ký tự. Khi xử lý một lượng lớn các cặp giá trị khóa trong một mảng kết hợp, một vấn đề có thể phát sinh được gọi là va chạm.Va chạm xảy ra khi chỉ số số nguyên xuất phát từ một khóa giống hệt với chỉ số số nguyên của khóa khác.Hai khóa này sau đó chỉ hiệu quả vào cùng một chỉ số trong mảng giá trị.Có nhiều giải pháp khác nhau để va chạm, chủ yếu là do nó có xác suất cao xảy ra trong hầu hết các ứng dụng thực tế.Vị trí, vị trí có thể chứa nhiều hơn một giá trị.Điều này được gọi là chuỗi và là một cách đơn giản để xử lý một vụ va chạm, mặc dù nó cũng có thể làm chậm thời gian cần thiết để lấy thông tin.Một phương pháp khác để xử lý va chạm được gọi là thăm dò tuyến tính.Khi xảy ra va chạm, thăm dò tuyến tính hoạt động bằng cách di chuyển qua mảng giá trị cho đến khi tìm thấy chỉ số không sử dụng.Giải pháp này có thể giúp giữ dữ liệu được phân phối đều trong mảng kết hợp, nhưng nó cũng có thể tăng lượng thời gian cần thiết để tra cứu một giá trị.