# 해시 테이블 내 검색 속도 향상을 입증한 학부생 연구

> Clean Markdown view of GeekNews topic #19168. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=19168](https://news.hada.io/topic?id=19168)
- GeekNews Markdown: [https://news.hada.io/topic/19168.md](https://news.hada.io/topic/19168.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2025-02-11T09:51:21+09:00
- Updated: 2025-02-11T09:51:21+09:00
- Original source: [quantamagazine.org](https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/)
- Points: 5
- Comments: 1

## Summary

Rutgers University의 학부생 Andrew Krapivin은 기존보다 더 빠르게 작동하는 새로운 종류의 해시 테이블을 발명하여 40년 된 데이터 과학의 추측을 뒤엎는 결과를 가져왔습니다. 그의 연구는 Yao의 추측을 반박하며, 최악의 경우 쿼리와 삽입에 필요한 시간이 (log x)²에 비례함을 증명했습니다. 또한, 비탐욕적 해시 테이블에서 평균 쿼리 시간이 x에 의존하지 않는다는 것을 보여주어 해시 테이블의 충만도와 상관없이 일정한 평균 쿼리 시간을 달성할 수 있음을 밝혔습니다.

## Topic Body

### 소개
- 2021년 가을, Rutgers University의 학부생 Andrew Krapivin은 그의 인생을 바꿀 논문을 접하게 됨.
- 이 논문은 컴퓨터 메모리에서 정보를 가리키는 '작은 포인터'에 관한 것이었음.
- Krapivin은 포인터를 더 작게 만들어 메모리 소비를 줄이는 방법을 고안함.

### 새로운 해시 테이블의 발견
- Krapivin은 데이터를 저장하는 일반적인 방법인 해시 테이블을 사용하여 실험을 진행함.
- 실험 중, Krapivin은 기존보다 더 빠르게 작동하는 새로운 종류의 해시 테이블을 발명하게 됨.
- 이 발견은 40년 된 데이터 과학의 추측을 뒤엎는 결과를 가져옴.

### 해시 테이블의 중요성
- 해시 테이블은 컴퓨터 과학에서 가장 오래된 데이터 구조 중 하나로, 데이터 저장의 효율성을 제공함.
- 해시 테이블은 요소를 검색, 삭제, 삽입하는 세 가지 기능을 수행할 수 있도록 설계됨.

### Yao의 추측과 그 반박
- 1985년, 컴퓨터 과학자 Andrew Yao는 특정 속성을 가진 해시 테이블에서 최악의 경우 요소를 찾는 방법에 대한 추측을 제시함.
- Krapivin의 새로운 해시 테이블은 Yao의 추측을 반박하며, 최악의 경우 쿼리와 삽입에 필요한 시간이 (log x)²에 비례함을 증명함.

### 평균 쿼리 시간에 대한 새로운 발견
- Krapivin과 그의 팀은 비탐욕적 해시 테이블에서 평균 쿼리 시간이 x에 의존하지 않는다는 것을 보여줌.
- 이는 해시 테이블의 충만도와 상관없이 일정한 평균 쿼리 시간을 달성할 수 있음을 의미함.

### 결론
- 이 연구는 해시 테이블에 대한 이해를 깊게 하며, 실질적인 응용으로 이어질 가능성이 있음.
- 데이터 구조에 대한 이러한 이해는 미래의 실용적인 개선을 위한 기반이 될 수 있음.

## Comments



### Comment 34393

- Author: neo
- Created: 2025-02-11T09:51:21+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=43002511) 
* Krapivin이 Yao의 추측을 모른 채로 돌파구를 마련했음
  - Balatro의 개발자는 기존 덱 빌더를 모른 채로 수상 경력의 덱 빌더 게임을 만들었음
  - 문제 접근의 최선의 방법은 이전의 유사한 노력들을 모른 채로 하거나 무시하는 것일 수 있음
  - 현재 세계는 너무 상호 연결되어 있어, 이전의 사고의 틀에 빠지기 쉬움
  - 인터넷은 훌륭하지만, 사고의 세계를 동질화시키는 경향이 있음

* 멋진 결과지만, 컴퓨터 과학 추측이라고 불려야 할 것 같음

* 이 구현을 가진 GitHub 저장소를 아는 사람이 있는지 궁금함

* 멋지지만, 이 글의 "유명인화" 스타일이 약간 불편함
  - 대학 환경에서 다양한 포즈를 취한 젊은이의 사진을 여러 장 볼 필요가 있었는지 의문임
  - 컴퓨터 성공의 생존자를 미화하여 더 많은 참여를 유도하기 위한 La La Land의 버전이 필요한 것 같음

* 새로운 해시 테이블에서 최악의 경우 쿼리와 삽입에 필요한 시간이 (log x)²에 비례함
  - 팀의 결과가 즉각적인 응용으로 이어지지 않을 수 있음
  - 왜 즉각적인 응용으로 이어지지 않는지 이해가 안 됨
  - 실제 사용 사례 분석이 순수한 수학적 접근보다 해시 구현을 더 잘 조정할 수 있는 상황인지 궁금함

* 이 기사를 읽는 것은 Monty-Hall 문제의 설명을 읽는 것과 같음
  - 결론이 상식을 거스르는 것 같지만 증명 가능함
  - 해시 테이블의 충만도와 상관없이 일정한 평균 쿼리 시간을 달성할 수 있다는 사실은 저자들조차도 예상하지 못했음

* 최근의 좋은 테스트임
  - 깊은 연구가 이 결과를 복사하지 않고 나올 수 있는지 보자
  - gpt4, Gemini 2, Claude는 운이 없었음
  - 인간 주도의 컴퓨터 과학은 여전히 안전함

* 'Tiny pointers'의 간단한 구현을 가진 사람이 있는지 궁금함
  - 내 마음은 증명보다 코드/의사 코드가 먼저임

* <i>Scooby Doo</i>의 악당이 항상 말했듯이:
  - <i>"그리고 그 성가신 아이들이 아니었다면, 난 성공했을 텐데!"</i>

* 논문을 대충 읽어보니, 그들이 사용한 주요 차이점은 해시 테이블 삽입 알고리즘이 첫 번째 빈 슬롯을 탐욕적으로 채우는 대신 더 멀리 탐색한다는 것임
  - 테이블이 매우 가득 차 있어도 빈 슬롯을 효율적으로 찾는 증명 가능한 탐색 순서를 결합함
  - 해시 테이블이 덜 가득 찼을 때 삽입이 느려지지만, 마지막 남은 빈 슬롯을 찾지 못하는 최악의 시나리오를 피할 수 있음

* 흥미로운 이론적 결과지만, 실제로는 필요한 것보다 더 큰 테이블을 할당하는 현재의 '트릭'이 더 나은 해결책일 것 같음
  - 예를 들어, Rust의 hashbrown은 테이블의 1/8(12.5%)을 비워두어 메모리를 조금 더 사용하지만 삽입/조회가 매우 빠름