해시 테이블 검색 한계를 뒤집은 학부생 연구

• Rutgers 학부생이던 Andrew Krapivin은 Tiny Pointers 논문을 계기로 새 해시 테이블을 고안했고, 기존 한계로 여겨지던 검색·삽입 성능을 넘어설 수 있음을 보임
• Krapivin, Martín Farach-Colton, William Kuszmaul은 2025년 1월 논문에서 특정 해시 테이블 범주에 대한 Yao의 40년 된 추측을 반박함
• 기존 추측은 테이블이 거의 가득 찬 정도를 나타내는 x에 대해 최악의 검색·삽입 시간이 x보다 나아질 수 없다고 봤지만, 새 구조는 (log x)²에 비례하는 시간을 달성함
• 연구진은 Yao가 다룬 인기 있는 해시 테이블 범주에서 (log x)²가 더 낮출 수 없는 최적 경계임도 보였고, 비탐욕적 해시 테이블에서는 평균 검색 시간이 x와 무관한 상수까지 가능함을 보임
• 당장 응용으로 이어지지 않더라도, 오래된 자료구조인 해시 테이블의 성능 한계를 다시 정리해 실무적 개선 가능성을 여는 이론적 기반이 됨

---

Tiny Pointers에서 시작된 새 해시 테이블

• Andrew Krapivin은 2021년 가을 Rutgers University 학부생 시절 Tiny Pointers 논문을 접했고, 2년 뒤 이를 자세히 읽으면서 더 작은 포인터를 만드는 방법을 떠올림
• 포인터가 가리킬 데이터를 더 잘 조직해야 했기 때문에, 일반적인 데이터 저장 방식인 해시 테이블이 연구 대상이 됨
• 실험 과정에서 Krapivin은 균일 탐사(uniform probing)에 의존하지 않는 새 해시 테이블을 만들었고, 특정 원소를 찾는 시간과 단계 수가 예상보다 적다는 점을 발견함
• Martín Farach-Colton은 처음에는 이 설계를 의심했지만, William Kuszmaul은 Krapivin의 구조가 단순히 흥미로운 해시 테이블을 넘어 40년 된 추측을 무너뜨리는 결과라고 판단함

해시 테이블의 성능 한계 문제

• 해시 테이블은 데이터를 저장하고 접근하는 자료구조이며, 기본적으로 세 가지 작업을 지원함
  • 원소를 검색(query) 함
  • 원소를 삭제함
  • 빈 슬롯에 원소를 삽입함
• 첫 해시 테이블은 1950년대 초반으로 거슬러 올라가며, 이후 컴퓨터 과학에서 계속 연구·사용되어 온 오래된 자료구조임
• 검색이나 삽입의 속도 한계는 보통 해시 테이블에서 빈 자리를 찾는 데 걸리는 시간과 연결됨
• 해시 테이블이 얼마나 가득 찼는지는 전체 비율로 표현할 수 있지만, 연구자들은 거의 가득 찬 표를 다룰 때 값 x를 사용함
  • x가 100이면 테이블은 99% 가득 참
  • x가 1,000이면 테이블은 99.9% 가득 참
• 특정 일반적 해시 테이블에서는 마지막 남은 빈 자리에 원소를 넣는 식의 최악 삽입 기대 시간이 x에 비례한다고 알려져 있었음

Yao의 1985년 추측과 반박

• Andrew Yao는 1985년 논문에서 특정 성질을 가진 해시 테이블에서 개별 원소나 빈 자리를 찾는 가장 좋은 방식이 가능한 위치를 무작위로 훑는 균일 탐사라고 봄
• 최악의 경우, 즉 마지막 남은 빈 자리를 찾는 상황에서는 x보다 나아질 수 없다는 추측이 40년 동안 대부분 참으로 받아들여짐
• Krapivin은 Yao의 추측을 모른 채 Tiny Pointers 관련 탐구를 진행했고, 균일 탐사에 의존하지 않는 새 해시 테이블을 만들었음
• Krapivin, Farach-Colton, Kuszmaul의 2025년 1월 논문은 이 새 해시 테이블에서 최악의 검색·삽입 시간이 (log x)²에 비례함을 보임
• 이 결과는 Yao의 추측과 직접 충돌하며, 연구진은 Yao가 다룬 인기 있는 해시 테이블 범주에서 (log x)²가 더 낮출 수 없는 최적 경계임도 증명함

평균 검색 시간에 대한 더 놀라운 결과

• Yao는 1985년에 최악의 검색 시간뿐 아니라 가능한 모든 검색에 걸친 평균 시간도 다뤘음
• 특정 성질을 가진 해시 테이블, 특히 새 원소를 첫 번째 가능한 위치에 넣어야 하는 탐욕적(greedy) 해시 테이블에서는 평균 시간이 log x보다 좋아질 수 없다고 증명함
• Farach-Colton, Krapivin, Kuszmaul은 같은 한계가 비탐욕적 해시 테이블에도 적용되는지 확인하려 했고, 반례를 통해 그렇지 않음을 보임
• 이 반례인 비탐욕적 해시 테이블은 평균 검색 시간이 log x보다 훨씬 좋고, 실제로는 x에 전혀 의존하지 않음
• 해시 테이블이 얼마나 가득 찼는지와 무관하게 상수 평균 검색 시간을 달성할 수 있다는 점은 연구진 자신에게도 예상 밖의 결과였음

오래된 자료구조에 대한 이론적 갱신

• Alex Conway는 해시 테이블이 가장 오래된 자료구조 중 하나이면서도 여전히 데이터를 저장하는 가장 효율적인 방법 중 하나라고 평가함
• Guy Blelloch는 이 결과가 고전적인 문제를 다루고 해결한다는 점에서 아름답다고 봄
• Sepehr Assadi는 연구진이 Yao의 추측을 반박했을 뿐 아니라, 그의 질문에 대한 최선의 답도 찾았다고 평가함
• Conway는 이 결과가 즉시 응용으로 이어지지 않더라도, 이런 자료구조를 더 잘 이해하는 일이 중요하다고 봄
• 해시 테이블의 이론적 한계를 다시 정리한 이번 결과는 나중에 실제 성능 개선으로 이어질 수 있는 기반이 됨

[GN⁺]

Hacker News 의견들

• Krapivin은 Yao의 추측을 몰랐기 때문에 이 돌파구를 만들었고, Balatro 개발자도 기존 덱 빌더들을 잘 몰랐기 때문에 수상작을 만들었다고 봄
  문제에 접근하는 가장 좋은 방법은 이전의 비슷한 시도 대부분을 모르거나 무시하는 것일지도 모르겠다는 생각이 듦
  지금 세상은 너무 연결되어 있어서, 앞선 사람들의 사고의 틀에 빠지지 않는 참신함을 보기 드물어졌고, 인터넷은 훌륭하지만 사고를 균질화한다는 점은 아쉬움

  • 이전 시도를 무시하는 게 좋은 경우는, 기존과 완전히 다른 방향의 새로운 해법이 실제로 있을 때뿐이라고 봄
    대개는 과거의 성공 사례를 무시하면 이미 불모지였던 땅에 다시 씨를 뿌리게 됨
  • 내 경험상 가장 좋은 접근은 먼저 선행 연구를 읽지 않고 문제를 풀어본 뒤, 그다음 선행 연구를 읽고, 거기에 맞춰 자기 접근을 개선하는 것임
    너무 일찍 선행 연구를 읽으면 기존 사고방식에 갇히고, 아예 읽지 않으면 스스로 떠올리지 못한 중요한 것을 놓치게 됨
    자기 접근이 기존 최첨단보다 못하더라도, 비교를 통해 왜 최첨단 접근이 더 나은지 중요한 통찰을 얻을 수 있음
  • Balatro 개발자는 덱 빌더를 알고 있었고 Luck be a Landlord에서 직접 영감을 받았지만, 장르가 얼마나 큰지는 몰랐다고 함
    개발자의 직접 인용에 따르면 Balatro에 가장 큰 영향을 준 것은 Luck be a Landlord였고, Northernlion의 플레이 영상을 몇 개 본 뒤 비판타지 테마의 점수 공격 로그라이크 개념이 마음에 들어 당시 만들던 카드 게임을 로그라이크로 바꿨다고 함
    그 시점부터 의도적으로 장르와 거리를 뒀고, 스스로 실수하며 설계 공간을 순진하게 탐색하고 싶었다고 함
    Slay the Spire와 비교를 많이 듣지만, Balatro를 설계할 때는 그 게임을 해보거나 영상을 본 적이 없었고 훨씬 나중에야 접했다고 함
    https://www.reddit.com/r/Games/comments/1bdtmlg/comment/kup7...
  • “사람들이 널 응원하고 있어.” 그녀가 미소 지으며 말했다
    “하지만 모두의 도움 없이는 절대 해내지 못했을 거예요.” [Milo]가 반박했다
    “그럴지도 모르지.” Reason이 엄숙하게 말했다. “하지만 넌 시도할 용기가 있었고, 네가 할 수 있는 일은 대개 네가 하려는 일에 달려 있단다.”
    King Azaz가 말했다. “그래서 네 모험에서 아주 중요한 한 가지는 네가 돌아오기 전까지 말할 수 없었단다.”
    “기억나요.” Milo가 열 eagerly 말했다. “이제 말해주세요.”
    “그건 불가능했어.” 왕이 Mathemagician을 보며 말했다
    “완전히 불가능했지.” Mathemagician이 왕을 보며 말했다
    “그러니까….” 벌레가 갑자기 어지러워하며 말했다
    “그래, 맞아.” 둘이 함께 말했다. “하지만 그때 말해줬다면 넌 가지 않았을지도 모르지… 그리고 네가 알게 됐듯이, 불가능하다는 걸 모르는 한 정말 많은 일이 가능하단다.”
    — The Phantom Tollbooth (1961)
  • 대학 때 들었던 교수는 첫 출판 논문이 숙제로 제출한 풀이에서 나온 사람이었는데, 우연히 어떤 문제의 경계에 관한 미해결 문제를 풀었다고 함
    내가 사정이 많아 그 수업을 낙제하고 다시 들으면서 한 가지 습관을 알게 됨
    매 학기 후반 과제 중 하나에서, 30문제쯤 되는 문제 세트 중 하나를 실제로는 미해결 문제인 형태로 내고, 마감 하루이틀 전에 “아, 실수였다”면서 수정본을 보냈음
    항상 딱 한 번만 그런 일이 있었던 걸 보면 우연은 아니었을 것 같음

• monort [0]가 영상 [1] 링크를 줘서 크게 도움이 됨
  영상을 한 번 본 기준의 빠른 요약인데, 이름은 퍼널 해싱임
  아이디어는 배열을 지수적으로 더 작은 하위 배열로 나누는 것임. 첫 덩어리는 n/m, 두 번째는 n/(m^2)처럼 줄여가며 단일 원소까지 내려감. 이를 A0, A1 등으로 부르면 |A0| = n/m, |A1| = n/(m^2)이고 총 k단계가 됨
  A0에 c번 삽입을 시도하고, 실패하면 A1에 c번 시도함. 그것도 실패하면 빈 슬롯을 찾을 때까지 “퍼널”을 따라 내려감
  \delta를 빈 슬롯의 비율이라고 부르는데, 이 값이 해시 테이블 생성 시 정해지는 매개변수인지 동적으로 갱신되는 값인지는 잘 모르겠음. c = log(1/d), k = log(1/d)로 두면 최악 시간 복잡도는 O(log^2(1/d))가 됨
  이 방식은 탐욕적이지 않아서 Yao의 결과를 우회한다고 이해했음. Yao의 결과는 탐욕적 삽입과 검색 정책에 대해 성립하고, 위 방식은 퍼널 아래로 연쇄적으로 내려가므로 비탐욕적임
  세부적으로 까다로운 부분이 많겠지만, 내가 이해한 아이디어는 이 정도임. 완전히 잘못 짚었다면 알려주면 좋겠음
  Chakraborty, Vinodchandran, Meel의 “Distinct Elements in Streams” 아이디어 [2]가 많이 떠오름
  [0] https://news.ycombinator.com/item?id=43007860
  [1] https://www.youtube.com/watch?v=ArQNyOU1hyE
  [2] https://arxiv.org/pdf/2301.10191

  • 실제로는 두 알고리즘, Funnel Hashing과 Elastic Hashing을 제안함
    Funnel Hashing은 “탐욕적”이고, 탐욕적 해시 메커니즘에 관한 Yao의 추측을 깸
    Elastic Hashing은 “비탐욕적”이며 탐욕적 알고리즘보다 더 나은 상각 시간을 제공함
  • Yao의 추측을 비탐욕적이라서 우회한다는 설명은 기사와 모순됨
    기사가 틀린 건지, 논문 이해가 잘못된 건지 모르겠지만, 기사 작성자가 모르는 부분을 짚은 건지 궁금함
  • 영상을 보면서 이해가 안 된 부분은, 아주 드물게 퍼널 끝까지 충돌이 나는 경우에 무슨 일이 생기느냐는 것임
    영상 14:41쯤의 “몇 개의 키를 잡기 위한 특별한 마지막 단계”와 관련된 듯한데, 그것도 고정 크기여야 한다면 가득 찰 수 있음. 그 경우에는 어떻게 해야 할까?
  • 메모리 제약 환경에 유용할 수 있는 꽤 깔끔한 아이디어임
    [뻔뻔한 홍보]: 해시 테이블에 관심 있다면 Dandelion Hashtable [0]도 볼 만함
    우리 차세대 데이터베이스에서 쓰고 있고 HPDC'24에 발표됐으며, 현재 실사용 기준 가장 빠른 인메모리 해시 테이블임
    제한된 캐시라인 체이닝으로 폐쇄 주소법을 개선해 일반 서버에서 초당 10억 건 이상의 인메모리 요청을 처리함
    [0] https://dandelion-datastore.com/#dlht
  • Funnel hashing은 탐욕적임

• 발명자의 발표: https://www.youtube.com/watch?v=ArQNyOU1hyE

  • 엄밀하지 않은 형태로는 이미 많은 사람이 떠올렸지만 특별하다고 생각하지 않았을 법한 것임
    제약에 치이고 자원이 부족할 때 하게 되는 자원 관리 꼼수 중 하나처럼 보임
    우선순위별로 나누는 건 자원 배분에서 흔한 접근이고, 이건 그 변형임
    사람들이 현장에서 해온 다른 “참호 속 꼼수” 중에 발명자 본인도 대단한 일인지 몰랐지만 널리 받아들여진 것을 뒤집는 게 얼마나 많을지 궁금함. “배달할 게 많을 때 보통 가장 빠른 경로를 그리는 영리한 방법을 알아냈는데…” 같은 식임
    물론 그걸 알아보고 형식화하고, 작업하고, 논문으로 내는 건 큰 노력임. 그 공로를 깎아내리려는 건 아님
  • 논문은 창작자의 발표 영상이 함께 있을 때 훨씬 이해하기 쉽다고 계속 확신하게 됨
    논문에는 그냥 동영상 발표가 포함됐으면 좋겠음
  • 영상이 기사보다 훨씬 나음
    다만 이 접근도 보조 배열을 통해 메모리를 더 할당하는데, 그냥 초과 할당해서 키 충돌 가능성을 낮추고 최악의 경우도 덜 나쁘게 만드는 것보다 어떻게 더 나은지는 조금 이상하게 느껴짐

• 논문 [1]을 훑어보니 핵심 차이는 해시 테이블 삽입 알고리즘이 처음 발견한 빈 슬롯을 탐욕적으로 채우지 않고, 그보다 더 멀리 탐색한다는 점으로 보임
  이를 영리한 탐사 순서와 결합해 테이블이 매우 가득 찬 상황에서도 빈 슬롯을 효율적으로 찾는다는 것을 증명함
  즉 해시 테이블이 덜 찼을 때의 삽입은 느려지지만, 마지막 남은 몇 개의 빈 슬롯이 어디 있는지 모른 채 탐색하는 최악의 상황을 피함
  [1]: https://arxiv.org/pdf/2501.02305
  흥미로운 이론 결과지만, 실제로는 필요한 것보다 큰 테이블을 할당하는 현재의 “요령”이 더 나은 해법일 것으로 예상함
  예를 들어 Rust의 hashbrown은 의도적으로 테이블의 1/8, 즉 12.5%를 비워두는데, 메모리는 조금 더 쓰지만 삽입과 조회를 높은 확률로 매우 빠르게 만듦

  • 내가 알고리즘을 잘못 읽었을 수도 있지만, 논문을 보면 핵심 개선은 배열을 버킷으로 나누고 테이블이 차는 정도에 따라 다른 버킷에 집중하는 비균일 전략으로 보임
    이 방식은 테이블이 덜 찼을 때도 평균 탐사 위치 수를 늘림
    그래도 이 전략 안에서는 처음 본 빈 슬롯에 항목을 배치함
    “슬롯 건너뛰기”는 해시 순서에서 앞쪽으로 점프하는 것과 관련됨
  • 일정 기간은 탐욕적 채우기를 쓰다가, 테이블이 가득 차기 시작하면 휴리스틱으로 더 정교한 채우기로 전환하는 하이브리드도 가능하지 않을까?

• ‘Tiny pointers’의 간단한 구현을 가진 사람이 있나? 내 머리는 증명보다 코드나 의사코드를 먼저 보는 쪽을 선호함

• 멋지다. 이런 식으로 테이블을 컨테이너화할 방법이 있을지 늘 궁금했음
  일반 테이블은 모든 걸 쑤셔 넣은 벌크선 같음. 컨테이너선처럼 더 잘 조직할 수 있다면 훨씬 더 많은 것을 더 효율적으로 싣고, 더 빠르게 내릴 수도 있을 것 같음

  • 쉬운 일임
    테이블 행을 문자열이나 JSON 같은 것으로 변환하고, 그 변수에 base16을 적용하면 해당 데이터의 base16 문자열이 됨
    해시 테이블을 만들고 그 base16 문자열에 대한 키 값을 설정하면 데이터를 담은 컨테이너가 생김
    이제 16진수 문자열을 디코드하기만 하면 base32 데이터를 얻을 수 있음

• 해시 테이블의 이론적 성질은 늘 마법에 가까울 정도로 인상적이었고, 이번 결과는 그걸 더 확장한 것임
  이상하게 느껴졌던 건, 직관적으로 데이터를 저장하는 가장 효율적인 방법처럼 보였던 트리보다 해시 테이블이 어떻게 그렇게 훨씬 나을 수 있느냐였음
  내가 깨달은 건 해시 테이블 이론이 고정 크기의 객체 집합을 다룬다는 점임. 이 고정된 집합에 대해 해시 함수를 만들고, 그걸 벡터 인덱스처럼 사용해 미리 할당된 벡터에 저장함. 그래서 삽입, 삭제, 조회를 O(1)에 가깝게 할 수 있는 처방이 나옴. 반면 여러 트리 구조는 특정 크기를 가정하지 않음
  문제는 크기를 미리 정해야 하고, 벡터가 거의 차면 삽입 같은 과정이 느려질 수 있다는 것임
  기사를 훑어보니 이번 결과는 그 느려지는 부분을 해결하는 것으로 보이고, 거의 가득 찬 테이블에도 빠른 삽입을 가능하게 함
  흥미롭고 영리하지만 실제로 큰 실용적 진전은 아닐 듯함. 실전에서는 테이블을 영리하게 채우는 방법을 고민하기보다 가정한 크기를 늘리면 된다고 봄
  이해가 맞는지 확인하려고 쓰는 것이니, 틀렸다면 고쳐줘도 좋음

  • 상수 시간 연산의 증명에는 테이블 크기를 조정하는 데 걸리는 시간도 포함됨
    크기 조정이 일어나는 삽입에서는 테이블 크기에 선형인 훨씬 큰 시간이 들지만, 그 시간은 이미 수행된 모든 삽입에 상각됨
    테이블이 너무 차기 시작할 때마다 충분히 크게 키우면 빈도가 점점 줄어들기 때문에 평균적으로는 여전히 상수 시간이 됨
  • 트리는 정렬되어 있어서 부분집합과 범위를 훑거나 검색하는 데 좋고, 해시맵은 키-값 조회처럼 특정 키를 찾아가는 데 더 좋음
  • 이건 변경을 사용하는 명령형 세계에서만 맞는 얘기일 것 같음
    함수형 세계에서는 여전히 트리가 더 적합할 가능성이 큼
  • 대략 말한 것처럼 테이블을 개념적으로 2차원 구조로 분할하고, 한 “행”을 약 75% 찰 때까지 채운 뒤 다음 행으로 넘어가는 아이디어로 보임
    논문을 완전히 이해할 시간은 없었지만, 이 방식으로 삽입이 일관되게 빠르다고 주장함. 전체 용량의 75%까지는 이해가 가는데, 모든 행이 75%에 도달했을 때는 다른 모드가 있는지도 모르겠음
    조회도 빠르다고 주장하지만, 조회가 어떻게 동작하는지나 왜 빠른지는 충분히 읽지 못했음
    거의 가득 찬 해시 테이블이 그래도 동작하면 정말 좋은 상황은 많음. 프로그램 실행 중에 항상 크기를 바꿀 수 있는 건 아니고, 어떤 환경에서는 메모리가 매우 중요함
    그래도 구현체를 보고 직접 다뤄보고 싶음. 일반적인 경우에 이게 “그만한 가치”가 있는지는 확신이 안 섬
    캐시 효율도 좋지 않을 가능성이 큼. 해시 테이블의 대부분이 그렇지만, 꽤 찬 테이블에서 선형 탐사로 읽는 경우만은 예외적으로 메모리에서 연속으로 꺼내 확인할 수 있음
    성능 관점에서 가치가 있는지는 아직 명확하지 않지만, 흥미로운 새 아이디어라 완전히 이해해보고 싶음

• “이 새 해시 테이블에서 최악의 질의와 삽입에 필요한 시간은 (log x)2에 비례하며, x보다 훨씬 빠르다”면서도 “팀의 결과가 즉각적인 응용으로 이어지지는 않을 수 있다”고 하는 부분이 이해가 안 됨
  왜 즉각적인 응용으로 이어지지 않을까? 실제 사용 사례 분석을 통해 순수 수학적 접근보다 해시 구현을 더 잘 조정할 수 있는 상황이라는 뜻인가?

  • 논문은 읽지 않았지만, 때로는 점근적 개선이 O() 분석에서 빠지는 큰 곱셈 상수 때문에 현실의 개선으로 이어지지 않음
    속도 향상을 보려면 데이터셋이 비현실적으로 커야 하는 경우가 있음
  • 최신 상태를 잘 따라가고 있지는 않지만 해시 테이블을 몇 번 구현해봤고, 보통 75%가 차면 확장했음
    그러면 x가 4보다 커지지 않으므로, O(x)를 O((log x)^2)로 개선해도 x가 그렇게 작을 때는 의미가 없음
    메모리 제약이 있는 일부 특수 응용에서는 x를 더 크게 두겠지만, 개인적으로는 그런 경우를 만나지 못했음
  • 실제 현장에서 균일 탐사 해시 테이블을 쓰는 사람은 거의 없을 것 같음
    매우 높은 적재율, 예를 들어 90% 초과가 필요할 때마다 쿠쿠 해싱이면 충분했고, 70~80% 이하에서는 선형 탐사가 매우 빠르고 충분히 좋았음
  • 실전에서는 해시 테이블에 공간을 조금 더 예약해 최악의 연산을 피함
    새 결과는 “좋은 경우”의 삽입이 느려지는 비용도 있음
  • 복잡도 분석과 실제 시스템 프로그래밍은 한동안 갈라지고 있었음
    논문에서 실무에 영향을 줄 만한 내용은 보이지 않음

• 이 결과는 해시 테이블이 거의 가득 찬 경우에만 중요해 보임
  그렇다면 테이블 크기를 10% 더 크게 잡거나, 크기 조정이 가능하다면 더 일찍 리사이즈하면 되는 것 아닐까?

  • 맞음. 대부분의 실제 해시 테이블이 그렇게 함
    해시 충돌 가능성이 너무 커지면 스스로 크기를 조정함
  • 현실에서는 선형 탐사의 표준 채움 비율이 75%이고, 이때 지역성도 가장 좋음
    테이블이 너무 차면 그냥 메모리를 두 배나 일정 배수로 더 할당하고 기존 항목을 복사함
    대부분의 비선형 탐사 테이블, 예를 들어 쿠쿠 해싱은 RAM이 전혀 “무작위”가 아니라는 사실 때문에 손해를 봄

• 이 구현이 있는 GitHub 저장소를 아는 사람이 있나?

  • 시도한 구현을 여기에 올려둠: https://github.com/sternma/optopenhash