MegaHash - Bảng băm tốc độ cao cho Node.JS được phát triển bằng C++

 (github.com)
7 điểm bởi xguru 2020-07-24 | 2 bình luận | Chia sẻ qua WhatsApp

  • Thay thế ES6 Maps bị giới hạn ở mức 16 triệu phần tử: có thể lưu trữ hơn 1 tỷ khóa

  • Được phát triển bằng C++ và bao gồm wrapper cho Node.js

→ Có thể đọc/ghi 500 nghìn khóa mỗi giây

→ Ít overhead bộ nhớ

→ Không được lưu trên V8 Heap

→ Hỗ trợ Buffer, chuỗi, số, boolean, object

  • Tương thích cơ bản với API của ES6 Map: get, set, has, ddelete, clear, length

  • Bên trong sử dụng kỹ thuật Separate Chaining: chỉ mục + danh sách liên kết

Bài viết liên quan

2 bình luận

 
kbumsik 2020-07-24

Hả, có lý do gì để dùng một Map lớn đến vậy không nhỉ?
 
xguru 2020-07-24

Trên thực tế, nếu đưa hơn 2^24 khóa vào Map trong Node.JS thì sẽ xảy ra lỗi heap.

Đây không phải là bug mà là một giới hạn được quy định trong triển khai, và có câu trả lời của một lập trình viên V8 về vấn đề này trên StackOverflow.

https://stackoverflow.com/a/54466812/166418

  • FixedArray dùng để lưu Map có kích thước tối đa là 1GB

  • Trên hệ thống 64-bit, 1GB / 8B = 2^30 / 2^3 = 2^27 ~= 134M, nên FixedArray có thể lưu tối đa 134 triệu phần tử

  • Map cần 3 phần tử cho mỗi entry (Key, value, next bucket link), và số lượng nạp tối đa bị giới hạn ở 50% để tránh va chạm bucket.

→ Vì dung lượng phải là lũy thừa của 2, nên từ phép tính 2^27 / (3 * 2), nếu làm tròn xuống về lũy thừa tiếp theo thì mức tối đa là 2^24