40년 된 추측이 깨지다: 새로운 해시 테이블이 기대치를 뛰어넘다

케임브리지 대학교 대학원생 크라피빈과 뉴욕 대학교의 파라크-콜튼, 쿠즈마울은 컴퓨터 과학계의 오랜 믿음이었던 야오의 추측을 뒤엎었습니다. 그들이 개발한 새로운 해시 테이블은 최악의 경우 원소 검색 시간 복잡도가 (log x)²로, 이전 최적 해라고 여겨졌던 x보다 훨씬 빠릅니다. 이 획기적인 연구는 해시 테이블 설계의 고전적인 문제를 해결할 뿐만 아니라 데이터 저장 효율성을 극적으로 향상시켜 학계의 큰 주목을 받고 있습니다.