약 70년 전, Hans Peter Luhn이라는 IBM 엔지니어가 조용히 컴퓨터 과학의 방향을 바꾸었습니다. Luhn은 이미 천의 실 수를 측정할 수 있는 장치에 대한 특허와 부엌에 있는 재료로 어떤 혼합 음료를 만들 수 있는지 결정하는 가이드에 대한 특허를 포함하여 여러 특허를 보유하고 있습니다. 그러나 1953년 IBM 내부 문서에서 그는 현재 거의 모든 계산 시스템에 내장되어 있는 정보를 저장하고 검색하는 새로운 기술인 해시 테이블을 제안했습니다.

해시 테이블은 데이터 구조의 주요 클래스입니다. 이는 대규모 데이터베이스의 정보에 액세스하고 변경하는 데 특히 편리한 방법을 제공합니다. 하지만 이 기술에는 피할 수 없는 절충안이 따릅니다.

1957에서 종이 에 게시 IBM 연구 및 개발 저널, W. Wesley Peterson은 해시 테이블이 제기하는 주요 기술적 과제를 확인했습니다. 즉, 속도가 빨라야 하며, 이는 필요한 정보를 신속하게 검색할 수 있음을 의미합니다. 하지만 가능한 한 적은 메모리를 사용하여 컴팩트해야 합니다. 이러한 두 가지 목표는 근본적으로 상충됩니다. 해시 테이블에 더 많은 메모리가 있으면 데이터베이스 액세스 및 수정이 더 빠르게 수행될 수 있습니다. 공간을 적게 사용하는 해시 테이블에서는 작업 속도가 느려집니다. Peterson이 이 과제를 제시한 이후로 연구자들은 시간과 공간 사이의 최상의 균형을 찾으려고 노력해 왔습니다.

이제 컴퓨터 과학자들은 최적의 절충안을 찾았음을 수학적으로 증명했습니다. 해결책은 다음에서 나왔습니다. 쌍 최근의 서류 그것은 서로를 보완했습니다. "이 논문은 가능한 최선의 시공간 상충관계에 대한 오랜 미해결 문제를 해결하여 앞으로 수년 동안 상당한 영향을 미칠 것으로 예상되는 매우 놀라운 결과를 산출했습니다."라고 말했습니다. 마이클 미첸마허, 하버드 대학교의 컴퓨터 과학자로 두 연구 모두에 참여하지 않았습니다.

“확실히 큰 일이라고 말하고 싶습니다.”라고 덧붙였습니다. 라스무스 파그, 코펜하겐 대학의 컴퓨터 과학자. “많은 사람들이 이 문제를 해결하기 위해 노력하면서 공간을 얼마나 절약하면서 시간 효율적인 작업을 수행할 수 있는지 알아보려고 노력했습니다. 이것이 제가 해결하고 싶었던 문제입니다.”

해시 만들기

해시 테이블은 오늘날 가장 오래되고, 단순하고, 빠르고, 가장 널리 사용되는 데이터 구조 중 하나입니다. 이는 세 가지 기본 작업, 즉 데이터베이스에 새 항목을 추가하는 삽입; 항목에 액세스하거나 항목이 존재하는지 확인하는 쿼리 삭제. 해시 테이블은 특정 프로그램이 실행되는 동안에만 존재하는 일시적일 수도 있고, 컴퓨터 운영 체제의 영구적인 부분일 수도 있습니다. Chrome이나 Safari와 같은 웹 브라우저에는 다양한 종류의 데이터를 추적하기 위한 여러 개의 내장 해시 테이블이 있을 수 있습니다.

해시 테이블의 항목은 항목(정보 자체)이 정보를 식별하는 키에 연결된 쌍으로 저장됩니다. 해시 테이블의 쿼리 알고리즘에 키를 연결하면 항목으로 직접 이동됩니다. 이는 그다지 이상하게 들리지 않을 수도 있지만 대규모 데이터베이스의 경우 시간을 크게 절약할 수 있습니다.

극도로 단순화된 예를 들어보려면 600,000개 이상의 단어에 대한 정의가 있는 Oxford English Dictionary를 생각해 보세요. 디지털 버전이 해시 테이블에 의존하는 경우 주어진 단어를 키로 사용하고 바로 정의로 진행할 수 있습니다. 해시 테이블이 없으면 사전은 제거 프로세스를 사용하여 결국 요청된 정의에 수렴하는 훨씬 느린 검색 메커니즘에 의존할 가능성이 높습니다. 해시 테이블은 일정한 시간(보통 XNUMX초 미만) 내에 모든 단어를 찾을 수 있지만, 사전에 있는 단어 수가 증가하면 다른 방법을 사용하는 검색 시간도 늘어날 수 있습니다. 해시 테이블은 또 다른 장점도 제공합니다. 사전을 동적으로 유지할 수 있어 새 단어를 쉽게 삽입하고 오래된 단어를 삭제할 수 있습니다.

연구자들은 속도를 최대화하고 메모리를 최소화하기 위해 해시 테이블을 구축하는 데 수십 년을 보냈습니다. 20세기에는 솔루션이 시간이나 공간이라는 한 가지 측면에서만 상당한 이점을 제공하는 경향이 있었습니다. 그러다가 2003년에 연구자들은 보여 시간과 공간 모두에서 동시에 효율성을 크게 향상시키는 것이 이론적으로 가능하다는 것입니다. 그러나 연구자들이 둘 사이의 이상적인 균형을 찾는 데는 20년이 더 걸릴 것입니다.

데이터 셔플

해당 목표를 향한 첫 번째 주요 단계는 2022년에 이루어졌습니다. 주요 컴퓨터 과학 컨퍼런스 로마에서. 그곳에서 한 팀은 지금까지 생각된 최고의 시간 및 공간 효율성 조합을 제공할 수 있는 새로운 기능을 갖춘 해시 테이블을 제안했습니다. 논문(알파벳순으로 나열)의 첫 번째 저자는 Stony Brook University의 Michael Bender이므로 일반적으로 Bender et al.이라고 합니다. 해시 테이블. 팀은 작동하는 해시 테이블을 구축하려고 시도하지는 않았지만 원칙적으로 그들이 설명한 기능으로 구축될 수 있음을 입증했습니다.

그들이 생각해낸 해시 테이블을 평가하기 위해 그룹은 한 축에 작업(삽입 또는 삭제)당 시간을 표시하고 다른 축에 메모리가 차지하는 공간을 표시하는 그래프인 절충 곡선을 생성했습니다. 하지만 이 그래프는 특별한 방식으로 공간을 정의합니다. 즉, 해시 테이블은 구성 방식 때문에 특정 항목 집합을 저장하는 데 필요한 최소한의 메모리보다 더 많은 메모리가 필요합니다. 컴퓨터 과학자들은 이러한 추가 공간을 "낭비된 비트"라고 부릅니다. 실제로는 낭비되지 않고 어느 정도 필요한 부분임에도 불구하고 말입니다. 절충 곡선의 공간 축은 키당 낭비되는 비트 수를 측정합니다.

연구자들은 트레이드오프 곡선을 분석함으로써 주어진 공간을 사용하는 해시 테이블에 대해 가능한 가장 빠른 시간을 알아낼 수 있습니다. 또한 질문을 뒤집어 주어진 작업 시간 동안 가능한 가장 작은 공간을 알아낼 수도 있습니다. 일반적으로 한 변수의 작은 변화는 다른 변수의 작은 변화로 이어진다고 말했습니다. 윌리엄 쿠스마울, 하버드의 이론적인 컴퓨터 과학자이자 2022년 논문의 공동 저자입니다. "시간을 두 배로 늘리면 키당 낭비되는 비트 수가 절반으로 줄어들 것입니다."

그러나 그들이 디자인한 해시 테이블의 경우는 그렇지 않습니다. Kuszmaul은 “시간을 조금만 늘리면 키당 낭비되는 비트가 기하급수적으로 감소합니다.”라고 말했습니다. 트레이드오프 곡선은 너무 가파르기 때문에 말 그대로 차트에서 벗어났습니다.

팀은 해시 테이블을 두 부분으로 구성했습니다. 여기에는 항목이 전혀 낭비되지 않고 저장되는 기본 데이터 구조와 쿼리 요청이 찾고 있는 항목을 찾는 데 도움이 되는 보조 데이터 구조가 있습니다. 그룹이 보조 데이터 구조라는 개념을 발명하지는 않았지만 초효율적인 해시 테이블을 가능하게 하는 중요한 발견을 했습니다. 구조의 전체 메모리 효율성은 기본 구조가 저장된 항목을 어떻게 배열하는지에 따라 달라집니다.

기본 아이디어는 기본 구조의 모든 항목에 선호하는 저장 위치(가장 좋은 위치, 두 번째로 좋은 위치, 세 번째로 좋은 위치 등)가 있다는 것입니다. 항목이 가장 좋은 위치에 있으면 숫자 1이 추가되고 해당 숫자는 보조 데이터 구조에 저장됩니다. 쿼리에 대한 응답으로 보조 구조는 기본 구조에서 항목의 정확한 위치를 나타내는 숫자 1만 제공합니다.

항목이 100번째로 좋은 위치에 있으면 보조 데이터 구조에 숫자 100이 추가됩니다. 그리고 시스템은 이진수를 사용하기 때문에 숫자 100을 1100100으로 나타냅니다. 물론 숫자 1100100을 저장하려면 1보다 더 많은 메모리가 필요합니다. — 항목이 가장 좋은 위치에 있을 때 항목에 할당된 번호입니다. 예를 들어 백만 개의 항목을 저장하는 경우 이와 같은 차이가 중요해집니다.

따라서 팀은 기본 데이터 구조의 항목을 더 선호하는 위치로 지속적으로 이동하면 쿼리 시간을 늘리지 않고도 보조 구조에서 소비하는 메모리를 크게 줄일 수 있다는 것을 깨달았습니다.

Pagh는 "이 작업 전에는 정보를 이동하여 데이터 구조를 더 압축할 수 있다는 것을 아무도 깨닫지 못했습니다."라고 말했습니다. "그것이 Bender 논문의 큰 통찰력이었습니다."

저자는 자신의 발명이 가장 효율적인 해시 테이블에 대한 새로운 상한선을 설정했음을 보여주었습니다. 이는 시간 및 공간 효율성 측면에서 지금까지 고안된 최고의 데이터 구조임을 의미합니다. 하지만 다른 누군가가 더 잘할 수도 있다는 가능성은 여전히 ​​남아 있었습니다.

성공할 의무

내년에는 다음 팀이 이끄는 팀이 유화청Princeton University의 컴퓨터 과학자인 는 Bender 팀의 해시 테이블을 개선하려고 노력했습니다. “우리는 정말 열심히 일했지만 할 수 없었습니다.”라고 말했습니다. 저우 렌페이, 베이징 칭화대학교 학생이자 Yu 팀의 일원입니다. "그때 우리는 그들의 상한선이 하한선이기도 하다고 의심했습니다." 이는 달성할 수 있는 최고 수준입니다. "상한값이 하한값과 같을 때 게임이 종료되고 답을 얻게 됩니다." 당신이 아무리 영리하더라도 해시 테이블이 이보다 더 나은 결과를 가져올 수는 없습니다.

Yu의 팀은 첫 번째 원칙에서 하한을 계산하여 그 직감이 올바른지 알아내기 위해 새로운 전략을 사용했습니다. 첫째, 그들은 삽입이나 삭제를 수행하려면 해시 테이블(또는 실제로 모든 데이터 구조)이 컴퓨터의 메모리에 여러 번 액세스해야 한다고 추론했습니다. 공간 효율적인 해시 테이블에 필요한 최소 횟수를 알아낼 수 있다면 여기에 액세스당 필요한 시간(상수)을 곱하여 런타임에 대한 하한을 제공할 수 있습니다.

하지만 그들이 해시 테이블에 대해 아무것도 몰랐다면(공간 효율적이라는 점을 제외하고) 연구자들은 메모리에 액세스하는 데 필요한 최소 횟수를 어떻게 알아낼 수 있었을까요? 그들은 두 당사자 간에 정보를 전달하는 데 얼마나 많은 비트가 필요한지 연구하는 통신 복잡성 이론이라는 겉보기에 관련이 없어 보이는 분야를 사용하여 순전히 이론에서 파생했습니다. 결국 팀은 성공했습니다. 그들은 데이터 구조가 작업당 메모리에 몇 번이나 액세스해야 하는지 알아냈습니다.

이것이 그들의 주요 성과였습니다. 그런 다음 공간 효율적인 해시 테이블에 대한 런타임 하한을 설정할 수 있었습니다. 그리고 그들은 그것이 Bender 해시 테이블과 정확히 일치한다는 것을 알았습니다. “우리는 [처음에는] 개선될 수 있다고 생각했습니다.”라고 Zhou는 말했습니다. “우리가 틀렸다는 것이 밝혀졌습니다.” 이는 결국 피터슨의 문제가 마침내 해결되었음을 의미했습니다.

Kuszmaul은 수십 년 된 질문에 답하는 것 외에도 Yu 증명의 놀라운 점은 일반성이라고 말했습니다. "그 하한은 아직 발명되지 않은 데이터 구조를 포함하여 가능한 모든 데이터 구조에 적용됩니다." 이는 어떤 데이터 저장 방법도 메모리와 속도 측면에서 Bender 해시 테이블을 능가할 수 없다는 것을 의미합니다.

미래를 향한 해싱

새로운 해시 테이블의 전례 없는 효율성에도 불구하고 누구도 조만간 이를 구축하려고 시도하지 않을 것입니다. 구성하기가 너무 복잡합니다. “이론적으로 빠른 알고리즘이 실제로는 반드시 빠른 것은 아닙니다.”라고 Zhou는 말했습니다.

이론가들이 일정한 요인을 무시하는 경향이 있기 때문에 이론과 실제 사이의 그러한 격차가 오랫동안 지속되는 것은 드문 일이 아니라고 Kuszmaul은 말했습니다. 작업을 수행하는 데 걸리는 시간은 일반적으로 숫자로 곱해지며, 이론적 관점에서는 정확한 값이 중요하지 않을 수 있는 일부 상수입니다. "그러나 실제로는 상수가 정말 중요합니다."라고 그는 말했습니다. "실제 세계에서는 10배가 게임 종료입니다."

실제 해시 테이블은 이론적 이상에는 크게 미치지 못하더라도 여전히 중요한 측면에서 개선되고 있습니다. 예를 들어, 다음과 같은 새로운 해시 테이블이 있습니다. 빙산HTBender, Kuszmaul 등이 만든 는 이전 제품보다 훨씬 뛰어납니다. Kuszmaul에 따르면 현재 사용 가능한 가장 공간 효율적인 해시 테이블보다 2배 빠르며 가장 빠른 해시 테이블보다 3배 적은 공간을 사용합니다.

Mitzenmacher는 2023년 결과가 곧 또 다른 종류의 이점을 제공할 수 있기를 바라고 있습니다. "새로운 하한값을 얻을 때마다, 특히 일부 새로운 기술이 포함된 하한값을 얻을 때마다 관련 문제에 대해 이를 사용할 수 있다는 희망이 항상 있습니다."

컴퓨터 과학자는 어렵고 오래된 문제를 해결했다는 사실에서 오는 지적 만족감도 있다고 말했습니다. 피오트르 인디크 매사추세츠 공과대학의. "특정 데이터 구조를 개선할 수 없다고 확신하면 연구 노력에 집중하는 데 도움이 될 수 있습니다." 마지막으로, 데이터 연구자들은 Peterson의 도전에서 관심을 돌리고 이론적인 컴퓨터 과학의 새로운 문제에 초점을 맞출 수 있습니다.