MegaHash - C++로 개발된 Node.JS용 빠른 Hash Table
(github.com)- 1600만개 제한인 ES6 Maps를 대체 : 10억개 이상의 키 저장 가능
- C++로 개발하고 Node.js 용 Wrapper 를 포함
ㅤ→ 초당 50만개 키 Read/Write 가능
ㅤ→ 메모리 오버헤드 적음
ㅤ→ V8 Heap에 저장되지 않음
ㅤ→ Buffer, 문자열, 숫자, 불린, 객체 지원가능
- ES6 Map API와 기본 호환 : get, set, has, ddelete, clear, length
- 내부적으로 Separate Chaining 기법을 사용 : 인덱스 + 링크드리스트 방식
실제로 Node.JS 에서 2^24 개 이상의 키를 Map에 넣으면 힙 에러가 발생합니다.
이는 버그가 아닌 구현상 정의된 제한으로, 여기에 대한 V8 개발자의 답변이 StackOverflow에 있습니다.
https://stackoverflow.com/a/54466812/166418
- Map 을 저장하는 FixedArray 는 최대 크기가 1GB
- 64비트 시스템에서 1GB / 8B = 2^30 / 2^3 = 2^27 ~= 134M 로 FixedArray 는 최대 1억3400만개 엘리먼트 저장 가능
- Map 은 엔트리당 3개의 엘리먼트(Key, value, next bucket link)가 필요하고, 최대 적재 갯수는 버켓 충돌을 피하기 위해서 50%로 제한.
ㅤ→ 용량이 제곱수로 되어야 하니 2^27 / (3 * 2) 계산에서 다음 제곱으로 내리면 2^24 가 최대치