40년 된 해시 테이블에 대한 추측이 뒤집히다

40년 동안 컴퓨터 과학자들은 해시 테이블 검색 효율에 대한 1985년 앤드류 야오의 추측을 받아들여 왔습니다. 그러나 크라피빈과 그의 팀은 야오의 최악의 경우 한계를 훨씬 뛰어넘는 새로운 해시 테이블을 개발했습니다. 그들의 새로운 알고리즘은 훨씬 더 빠른 쿼리 및 삽입 시간을 달성하며, 놀랍게도 테이블의 채우기 비율에 관계없이 평균 쿼리 시간은 일정합니다. 이 획기적인 결과는 오랫동안 믿어져 온 가설을 뒤집을 뿐만 아니라 해시 테이블 최적화를 위한 새로운 길을 열어줍니다.