Thực hiện một bảng địa chỉ trực tiếp

Question

tôi đã được đưa ra như việc học tập của Introduction to Algorithms tập thể dục 11.1-3 mà đi như sau:

Đề nghị làm thế nào để thực hiện một bảng trực tiếp truy cập, trong đó các phím của các yếu tố được lưu trữ không cần phải phân biệt và các yếu tố có thể có dữ liệu vệ tinh. Tất cả ba hoạt động từ điển (Chèn, Xóa và Tìm kiếm) sẽ chạy trong thời gian O (1). Đừng quên rằng Xóa mất như một đối số một con trỏ đến một đối tượng sẽ bị xóa, không phải là một khóa.

Vâng, Chèn là không có vấn đề, vì nó chỉ đơn giản có nghĩa là tạo ra một danh sách liên kết tại vị trí thích hợp trong bảng (nếu nó chưa tồn tại) và thêm yếu tố vào nó. Tìm kiếm, được cung cấp một khóa, có thể trả về bất kỳ phần tử nào khớp với khóa, vì vậy nó chỉ đơn giản có nghĩa là chúng ta cần trả về phần đầu của danh sách khớp trong bảng.

Vấn đề của tôi là với thao tác Xóa. Nếu tôi sửa đổi đối tượng để thêm vào nó một con trỏ đến nút của nó trong danh sách liên kết, thì tôi có thể xóa trong O (1), nhưng tôi không chắc mình có được phép thay đổi đối tượng hay không. Có cách nào để làm điều này mà không thay đổi đối tượng nhất định?

Answer 1

Bảng băm sẽ hoạt động cho bạn đến một điểm nhất định. Một khi bạn bắt đầu có collsions, sau đó nó trở thành O (1 + k/n) trong đó k là số lượng các phím và n là kích thước bảng của bạn. Nếu bạn thay đổi kích thước băm và tái băm, bạn có thể thoát khỏi điều này. Không biết nếu điều đó sẽ ảnh hưởng đến xếp hạng hiệu quả của bạn vì nó không xảy ra trong quá trình chèn, xóa hoặc tìm kiếm.

Xóa bằng cách không thay đổi đối tượng có thể đạt được bằng cách chỉ cần đặt con trỏ tham chiếu băm thành rỗng. Không thay đổi trực tiếp đối tượng được thực hiện, nhưng thay đổi đối với vùng chứa đối tượng được tạo.

Tôi nghĩ rằng đối với hầu hết các hạn chế mà bạn đang đưa ra, một bảng băm có thể được triển khai theo những cách nhất định để giải quyết chúng. Có thêm thông tin tại http://en.wikipedia.org/wiki/Hash_table#Performance_analysis về cách triển khai bảng băm.

Answer 2

Đây có phải là câu hỏi từ sách Cormen không? Như tôi đã hiểu, từ việc đọc các đoạn trước trong cuốn sách đó, đối tượng mà bạn lưu trữ trong bảng truy cập trực tiếp là đối tượng 'của bạn'. Vì vậy, bạn có thể, như bạn đề xuất, lưu trữ con trỏ đến các danh sách được liên kết kép trong bảng với mỗi phần tử danh sách có một con trỏ đến đối tượng của người dùng. Sau đó, từ điển hoạt động TÌM KIẾM trả về một phần tử danh sách và người dùng phải sử dụng một bước nữa để có được đối tượng của mình. Tương tự, thao tác DELETE lấy một con trỏ tới một phần tử danh sách.

Điều đó có hợp lý không? Tôi không muốn làm hỏng bài tập về nhà của bạn!

Answer 3

Tôi nghĩ bạn có thể sử dụng dữ liệu vệ tinh để ánh xạ dưới dạng khóa phụ. Sau đó, nó là một loại bảng băm 2 cấp. Quan tâm đến hoạt động DELETE, lúc đầu chúng tôi sử dụng khóa chính. Và khi có các khóa chính trùng lặp, chúng tôi sử dụng các khóa phụ để nhận đối tượng. Do đó tổng thời gian vẫn là O (1).

Answer 4

Phần quan trọng nhất .. "thực hiện một bảng trực tiếp truy cập, trong đó các phím của các yếu tố được lưu trữ không cần phải phân biệt" và "hoạt động điển trong thời gian O (1) thời gian.

Việc chèn cũng không thể thực hiện được trong thời gian O (1) nếu các phần tử bằng nhau (như Q nói rằng các phần tử không cần phải phân biệt).

Đối với phần xóa, bạn phải lấy chìa khóa cũng như đối tượng để tiếp cận với một đối tượng cụ thể và giả sử một khóa dữ liệu vệ tinh, để tiếp cận đối tượng cụ thể.

Tôi nghĩ chỉ có trên 2 ý tưởng hợp lý cho thời gian O (1).

Answer 5

Chúng tôi có thể sử dụng danh sách liên kết kép ở mọi chỉ số của bảng địa chỉ trực tiếp. Khe j sẽ chứa một con trỏ tới đầu danh sách, chứa tất cả các phần tử có khóa-giá trị j và nếu không có vùng phần tử j chứa NIL. INSERT-chèn x ở đầu danh sách sẽ chỉ mất O (1) lần. TÌM KIẾM-Nó có thể trả về bất kỳ phần tử nào khớp với khóa đã cho và do đó trả về phần đầu của danh sách sẽ chỉ mất thời gian O (1). DELETE- Như chúng ta đã sử dụng danh sách liên kết kép, chúng ta có thể xóa một phần tử trong thời gian O (1) bằng cách sử dụng con trỏ tới các nút trước đó và tiếp theo.