TL;DR

  • hashbrown과 같은 원시 바이트를 해싱하는 84개 설정의 산술평균에서 MultiTable이 2.1배 처리량을 보이고, 네이티브 정수 키를 쓰는 hashbrown과 비교해도 1.9배 빠른 해시 테이블로 제시됨.
  • 부정 조회만 비교하면 hashbrown 대비 처리량이 각각 3.2배, 2.9배에 이르며, 물리적 적재율이 1에 가까워져도 조회 프로브 수에 급격한 증가 구간이 없음.
  • 요청된 용량에 맞춰 물리적 적재율을 최대 1까지 설정할 수 있으며, hashbrown은 4바이트 키·값에서 적재율 0.777에 도달하면 용량을 두 배로 늘림.
  • Apple M2 Pro에서 필터링 변형은 삽입·적중 조회·부정 조회를 포함한 84개 설정 모두에서 hashbrown보다 빠르며, 혼합 조회 처리량을 같게 맞추면 메모리를 최대 12% 덜 사용함.
  • 일반 변형은 hashbrown보다 18% 작고, 같은 메모리에서 키를 22% 더 많이 저장하며, 버킷 크기·물리적 적재율·실패 예산을 조정하고 재해싱 없이 확장할 수 있음.

연구 개요

  • Maksym Petkus가 안정형 해시 테이블인 MultiTable과 Rust 참조 구현을 제시함.
  • MultiTable은 같은 물리적 메모리 조건에서 Rust의 hashbrown 구현인 SwissTable보다 처리량이 높고, 설정 유연성이 큰 것으로 설명됨.
  • 논문 제목은 「MultiTable: 물리적 적재율이 1 이하인 모든 조건에서 더 빠른 해시 테이블」이며, arXiv 식별자는 arXiv:2609.39233임.
  • 논문은 2026년 9월 30일 제출됐으며, 컴퓨터 과학의 암호학·보안, 자료 구조·알고리즘과 조합론 및 확률 분야로 분류됨.
  • DOI: https://doi.org/10.48550/arXiv.2609.39233

처리량 비교

  • 84개 설정의 산술평균에서 양쪽이 동일한 원시 바이트를 해싱할 때 MultiTable 처리량은 hashbrown의 2.1배임.
  • hashbrown이 네이티브 정수 키를 사용해 가장 유리한 조건으로 비교하면 MultiTable은 1.9배의 처리량을 냄.
  • 부정 조회만 비교할 때 두 조건에서 각각 3.2배와 2.9배의 처리량을 보임.
  • 일반형과 필터링형 두 가지 MultiTable 변형을 구현했으며, Apple M2 Pro에서 같은 물리 메모리 기준으로 필터링형이 삽입·적중 조회·부정 조회의 84개 설정 모두에서 hashbrown을 앞섬.

적재율과 용량 확장

  • MultiTable은 요청 용량에 정확히 맞춰 물리적 적재율을 설정하며, 0.9999가 실제로 시연된 최대치이고 이론상 1을 포함한 모든 적재율에 도달함.
  • 4바이트 키와 값에서 hashbrown은 물리적 적재율 0.777에 도달하면 용량을 두 배로 늘림.
  • hashbrown의 경직된 용량 증가 단계가 만드는 평균 사례로 가정한 75% 포화 조건에서는, 물리적 적재율 0.97에 맞춘 MultiTable보다 hashbrown의 공간 사용량이 66% 더 큼.
  • 적재율이 1에 가까워져도 조회 프로브 횟수가 급격히 증가하는 구간이 없으며, 버킷 크기·물리적 적재율·실패 예산을 매개변수로 설정할 수 있고 재해싱 없이 테이블을 확장할 수 있음.

메모리 효율

  • 동일한 혼합 조회 처리량을 기준으로 4바이트 키·값 맵을 비교하면 필터링형 MultiTable은 hashbrown보다 메모리를 최대 12% 적게 사용함.
  • 일반형 MultiTable은 hashbrown보다 18% 작으며, 같은 메모리 안에 키를 22% 더 많이 저장함.