Làm thế nào để lưu trữ một bảng băm trong một tập tin?

Question

Làm cách nào để lưu trữ bảng băm có chuỗi riêng biệt trong một tệp trên đĩa?

Tạo dữ liệu được lưu trữ trong bảng băm trong thời gian chạy là tốn kém, sẽ nhanh hơn khi tải HT từ đĩa ... nếu chỉ tôi có thể tìm ra cách thực hiện.

Chỉnh sửa: Tra cứu được thực hiện bằng HT được tải trong bộ nhớ. Tôi cần phải tìm một cách để lưu trữ hashtable (trong bộ nhớ) vào một tập tin trong một số định dạng nhị phân. Vì vậy, thời gian tới khi chương trình chạy nó chỉ có thể tải HT ra đĩa vào RAM.

Tôi đang sử dụng C++.

Answer 1

Bạn đang sử dụng ngôn ngữ nào? Phương pháp phổ biến là làm một số thứ tự sắp xếp nhị phân.

Ok, tôi thấy bạn đã chỉnh sửa để thêm ngôn ngữ. Đối với C++ có một vài tùy chọn. Tôi tin rằng cơ chế serialization Boost là khá tốt. Ngoài ra, trang cho thư viện tuần tự hóa của Boost cũng mô tả các lựa chọn thay thế. Dưới đây là liên kết:

http://www.boost.org/doc/libs/1_37_0/libs/serialization/doc/index.html

Answer 2

Giả sử C/C++: Sử dụng chỉ số mảng và cấu trúc kích thước cố định thay vì con trỏ và phân bổ chiều dài thay đổi. Bạn sẽ có thể viết trực tiếp() các cấu trúc dữ liệu để tập tin cho sau này đọc() ing.

Đối với mọi thứ cấp cao hơn: Nhiều API ngôn ngữ cao hơn có cơ sở tuần tự hóa. Java và Qt/C++ đều có các phương thức chạy nhanh ngay lập tức, vì vậy tôi biết những người khác cũng làm như vậy.

Answer 3

Có lẽ DBM có thể được sử dụng cho bạn.

Answer 4

Bạn chỉ có thể viết toàn bộ cấu trúc dữ liệu trực tiếp vào đĩa bằng cách sử dụng tuần tự hóa (ví dụ: in Java). Tuy nhiên, bạn có thể bị buộc phải đọc toàn bộ đối tượng vào bộ nhớ để truy cập vào các phần tử của nó. Nếu điều này là không thực tế, thì bạn có thể xem xét sử dụng tệp random access để lưu trữ các phần tử của bảng băm. Thay vì sử dụng một con trỏ để biểu diễn phần tử tiếp theo trong chuỗi, bạn sẽ chỉ sử dụng vị trí byte trong tệp.

Answer 5

Nếu triển khai bảng băm của bạn là tốt, hãy lưu trữ giá trị băm và dữ liệu của từng đối tượng - đặt đối tượng vào bảng không nên tốn kém cho hàm băm và không nối tiếp bảng hoặc chuỗi trực tiếp cho phép bạn thay đổi thực hiện chính xác giữa lưu và tải.

Answer 6

Tắt con trỏ cho chỉ mục.

Điều này hơi giống với việc xây dựng một DAWG trên đĩa, mà tôi đã thực hiện một lúc. Điều làm cho nó rất ngọt ngào đến nỗi nó có thể được nạp trực tiếp bằng mmap thay vì đọc tập tin. Nếu hash-không gian là dễ quản lý, nói 2 hoặc 2 mục, sau đó tôi nghĩ rằng tôi sẽ làm điều gì đó như thế này:

• Giữ một danh sách các chỉ số miễn phí. (nếu bảng trống, mỗi chỉ số chuỗi sẽ trỏ đến chỉ mục tiếp theo.)
• Khi cần chuỗi cần sử dụng không gian trống trong bảng.
• Nếu bạn cần phải đặt một cái gì đó trong một chỉ số đó là chiếm bởi một người ngồi xổm (tràn từ nơi khác):
  • kỷ lục chỉ số (chúng ta hãy gọi nó là N)
  • hoán đổi các yếu tố mới và người ngồi xổm
  • đặt các squatter trong một chỉ số miễn phí mới, (F).
  • theo chuỗi trên chỉ số băm của người ngồi xổm, để thay thế N với F.
• Nếu bạn hoàn toàn chạy ra khỏi chỉ số miễn phí, bạn có thể cần một bảng lớn hơn, nhưng bạn có thể đối phó lâu hơn một chút bằng cách sử dụng mremap để tạo thêm phòng sau bàn.

Điều này sẽ cho phép bạn chèn và sử dụng trực tiếp bảng mà không sửa đổi. (nhanh chóng đáng sợ nếu trong bộ nhớ cache của hệ điều hành!) nhưng bạn phải làm việc với các chỉ mục thay vì con trỏ. Thật là ma quái khi có megabyte có sẵn trong syscall-round-time-time, và vẫn có nó chiếm ít hơn trong bộ nhớ vật lý, vì phân trang.