Java: cấu trúc băm liên tục lớn?

Question

Tôi đang tìm cấu trúc băm liên tục trong java, một kho khóa-giá trị đơn giản, trong đó khóa là một chuỗi và giá trị duy nhất là một int. Giá trị của một khóa được tăng lên mỗi lần một khóa hiện có được thêm vào cửa hàng.

Tôi cần điều này là khá lớn - có thể là các khóa 500m - 1bn. Tôi đã đánh giá tokyo-cabinet http://fallabs.com/tokyocabinet/javadoc/ nhưng không chắc chắn nó sẽ mở rộng như thế nào - thời gian chèn dường như nhận được lâu hơn khi băm tăng lên.

Bất kỳ ý tưởng nào về điều gì có thể phù hợp?

Cảm ơn

Edit: Để giảm đĩa I/O Tôi sẽ được bộ nhớ đệm dữ liệu trong một HashMap trong bộ nhớ, sau đó cập nhật các hash dai dẳng trong một đi khi bộ nhớ cache để phát triển một kích thước nhất định.

Chỉnh sửa2: Một trong những lý do cho sự kiên trì là tôi có RAM giới hạn, 4GB, vì vậy tôi không thể phù hợp với một cấu trúc lớn vào bộ nhớ.

Answer 1

Tôi điều Megamap là những gì bạn đang tìm kiếm: http://megamap.sourceforge.net/. Đây là một mô tả ngắn về Megamap từ trang chủ của nó:

MegaMap là một thực hiện Java của một bản đồ (hoặc Hashtable) có thể lưu trữ một lượng vô biên của dữ liệu, chỉ bị giới hạn bởi số lượng không gian đĩa có sẵn . Các đối tượng được lưu trữ trên bản đồ là được lưu vào đĩa. Hiệu suất tốt là đạt được bằng bộ nhớ cache trong bộ nhớ. MegaMap có thể, cho tất cả các lý do thực tế , được coi là bản đồ triển khai với bộ nhớ không giới hạn không gian.

Answer 2

Sử dụng cơ sở dữ liệu không phải là băm. Ngay cả đối với một cơ sở dữ liệu 500M hàng đang nhận được khá lớn. Có bao nhiêu bản cập nhật bạn mong đợi mỗi giây?

Answer 3

Vì vậy, nếu tôi hiểu chính xác, Redis có thể là một tùy chọn. Bạn có thể phát hành các lệnh INCR [key] để tăng giá trị nguyên tử liên quan đến khóa đó một cách nguyên tử. Nếu khóa không tồn tại, nó được đặt thành 0 và sau đó tăng lên (kết quả là một). Theo số docs, INCR là hoạt động liên tục. Tốc độ là mục tiêu thiết kế chính cho Redis.

Redis có thể tự lưu vào tệp và bạn có thể kiểm soát các thông số về cách điều đó xảy ra.

Answer 4

Tôi nghĩ rằng Memcached là lựa chọn tốt cho trường hợp của bạn cùng với cơ sở dữ liệu phù hợp trong chương trình phụ trợ.

Answer 5

Bạn đã xem phiên bản Berkeley BD Java chưa? Họ có một Collections-compatible API (xem thêm Javadoc cho StoredMap).