해시 테이블

해시(Hash), x. 이 단어에 대한 정의는 없다—아무도 해시가 무엇인지 모른다.

앰브로즈 비어스(Ambrose Bierce), 확장판 악마의 사전(The Unabridged Devil’s Dictionary)

성장하는 가상 머신에 변수를 추가하기 전에, 변수 이름을 통해 값을 찾는 방법이 필요합니다. 나중에 클래스를 추가할 때도 인스턴스에 필드를 저장하는 방법이 필요할 것입니다. 이러한 문제들을 해결하기 위한 완벽한 데이터 구조는 해시 테이블입니다.

해시 테이블이라는 이름을 몰라도 아마 이미 해시 테이블이 무엇인지 알고 있을 것입니다. 자바 프로그래머라면 "HashMap"이라고 부릅니다. C# 및 파이썬 사용자는 "딕셔너리(dictionaries)"라고 부릅니다. C++에서는 "unordered map"입니다. 자바스크립트의 "객체(Objects)"와 루아(Lua)의 "테이블(tables)"은 내부적으로 해시 테이블이며, 이것이 유연성을 제공합니다.

언어에서 무엇이라고 부르든 해시 테이블은 키(keys) 집합을 값(values) 집합과 연결합니다. 각 키/값 쌍은 테이블의 엔트리(entry) 입니다. 키가 주어지면 해당 값을 찾을 수 있습니다. 새로운 키/값 쌍을 추가하고 키로 엔트리를 제거할 수 있습니다. 기존 키에 새 값을 추가하면 이전 엔트리가 대체됩니다.

해시 테이블이 많은 언어에 등장하는 이유는 그 강력함 때문입니다. 이러한 강력함의 대부분은 한 가지 지표에서 비롯됩니다. 키가 주어지면 해시 테이블은 해시 테이블에 있는 키의 수에 관계없이 상수 시간 내에 해당 값을 반환합니다.

생각해보면 꽤 놀라운 일입니다. 명함 더미가 있는데 특정 사람을 찾아달라고 요청했다고 상상해 보세요. 더미가 클수록 시간이 더 오래 걸릴 것입니다. 더미가 잘 정렬되어 있고 이진 탐색을 손으로 할 수 있는 손재주가 있다고 해도 여전히 O(log n)입니다. 하지만 해시 테이블을 사용하면 명함 더미에 10장의 명함이 있든 100만 장이 있든 그 명함을 찾는 데 동일한 시간이 걸립니다.

20 . 1버킷 배열

완전하고 빠른 해시 테이블은 몇 가지 움직이는 부품을 가집니다. 몇 가지 간단한 문제와 그 해결책을 통해 하나씩 소개하겠습니다. 궁극적으로 모든 이름 집합을 해당 값과 연결할 수 있는 데이터 구조를 구축할 것입니다.

지금은 Lox가 변수 이름에 훨씬 더 많은 제약이 있다고 상상해 보세요. 변수 이름이 단 하나의 소문자만 될 수 있다면 어떨까요? 변수 이름과 그 값의 집합을 어떻게 매우 효율적으로 표현할 수 있을까요?

가능한 변수가 26개(밑줄을 "글자"로 간주한다면 27개)밖에 없다면 답은 쉽습니다. 26개 요소를 가진 고정 크기 배열을 선언합니다. 전통을 따라 각 요소를 버킷(bucket)이라고 부르겠습니다. 각 버킷은 'a'가 인덱스 0부터 시작하는 변수를 나타냅니다. 배열의 특정 문자 인덱스에 값이 있다면, 해당 키는 그 값과 함께 존재하는 것입니다. 그렇지 않으면 버킷이 비어 있고 해당 키/값 쌍은 데이터 구조에 없습니다.

메모리 사용량은 훌륭합니다—하나의 적당한 크기의 배열이면 됩니다. 빈 버킷으로 인한 약간의 낭비가 있지만, 크지 않습니다. 연결 리스트나 트리 같은 것에서 얻게 될 노드 포인터, 패딩, 또는 기타 오버헤드가 없습니다.

성능은 훨씬 더 좋습니다. 변수 이름(해당 문자)이 주어지면, 'a'의 ASCII 값을 빼서 그 결과를 배열의 인덱스로 직접 사용할 수 있습니다. 그러면 기존 값을 찾거나 새 값을 해당 슬롯에 직접 저장할 수 있습니다. 이보다 빠를 수는 없습니다.

이것이 일종의 플라톤적 이상형 데이터 구조입니다. 번개처럼 빠르고, 매우 간단하며, 메모리에서 압축되어 있습니다. 더 복잡한 키에 대한 지원을 추가할수록 약간의 타협이 필요하겠지만, 이것이 우리가 목표로 하는 바입니다. 해시 함수, 동적 크기 조정, 충돌 해결을 추가하더라도 모든 해시 테이블의 핵심은 여전히 이것입니다—직접 인덱싱하는 연속적인 버킷 배열입니다.

20 . 1 . 1로드 팩터와 래핑된 키

Lox를 단일 문자 변수로 제한하면 구현자의 작업은 쉬워지겠지만, 26개의 저장 공간만 제공하는 언어로 프로그래밍하는 것은 아마 재미없을 것입니다. 제한을 약간 완화하여 변수를 최대 8자 길이까지 허용한다면 어떨까요?

8자는 모든 문자를 64비트 정수로 압축하기에 충분히 작으며, 문자열을 숫자로 쉽게 변환할 수 있습니다. 그런 다음 이를 배열 인덱스로 사용할 수 있습니다. 아니면 적어도, 295,148 페타바이트 배열을 어떻게든 할당할 수 있다면 말이죠. 메모리는 시간이 지남에 따라 저렴해졌지만, 그만큼 저렴해지지는 않았습니다. 설령 그렇게 큰 배열을 만들 수 있다고 해도, 그것은 엄청나게 낭비적일 것입니다. 사용자가 우리가 예상했던 것보다 훨씬 더 큰 Lox 프로그램을 작성하지 않는 한 거의 모든 버킷은 비어 있을 것입니다.

변수 키가 전체 64비트 숫자 범위를 포괄하더라도, 분명히 그렇게 큰 배열은 필요하지 않습니다. 대신, 필요한 엔트리에 충분한 용량을 가지면서도 터무니없이 크지 않은 배열을 할당합니다. 키 값을 배열 크기의 모듈로 연산하여 전체 64비트 키를 더 작은 범위로 매핑합니다. 이렇게 하면 더 큰 숫자 범위가 스스로 접혀서 더 작은 배열 요소 범위에 맞게 됩니다.

예를 들어, "bagel"을 저장하고 싶다고 가정해 봅시다. 8개 요소를 가진 배열을 할당하는데, 이는 "bagel"과 나중에 더 많은 것을 저장하기에 충분합니다. 키 문자열을 64비트 정수로 취급합니다. 인텔과 같은 리틀 엔디안(little-endian) 머신에서는 이 문자들을 64비트 워드에 압축하면 첫 글자인 'b'(ASCII 값 98)가 최하위 바이트에 위치합니다. 이 정수 값을 배열 크기(8)로 모듈로 연산하여 범위 내에 맞추고 버킷 인덱스 2를 얻습니다. 그리고 평소처럼 값을 저장합니다.

배열 크기를 모듈로 사용하면 키의 숫자 범위를 어떤 크기의 배열에도 맞게 매핑할 수 있습니다. 따라서 키 범위와 독립적으로 버킷 수를 제어할 수 있습니다. 이는 낭비 문제를 해결하지만, 새로운 문제를 야기합니다. 키 번호가 배열 크기로 나눴을 때 동일한 나머지를 가지는 두 변수는 모두 동일한 버킷에 저장됩니다. 키는 충돌(collide)할 수 있습니다. 예를 들어, "jam"을 추가하려고 하면, 그것도 버킷 2에 저장됩니다.

배열 크기를 조절하여 이를 어느 정도 제어할 수 있습니다. 배열이 클수록 동일한 버킷에 매핑되는 인덱스가 적어지고 충돌 발생 가능성이 줄어듭니다. 해시 테이블 구현자는 테이블의 로드 팩터(load factor)를 측정하여 이 충돌 가능성을 추적합니다. 로드 팩터는 엔트리 수에서 버킷 수를 나눈 값으로 정의됩니다. 따라서 5개의 엔트리와 16개 요소를 가진 배열이 있는 해시 테이블은 0.3125의 로드 팩터를 가집니다. 로드 팩터가 높을수록 충돌 가능성이 커집니다.

충돌을 완화하는 한 가지 방법은 배열의 크기를 조정하는 것입니다. 이전에 구현했던 동적 배열과 마찬가지로, 해시 테이블의 배열이 채워지면 재할당하고 확장합니다. 하지만 일반적인 동적 배열과는 달리, 배열이 완전히 채워질 때까지 기다리지 않을 것입니다. 대신, 원하는 로드 팩터를 선택하고 그 값을 초과할 때 배열을 확장합니다.

20 . 2충돌 해결

매우 낮은 로드 팩터를 사용하더라도 충돌은 여전히 발생할 수 있습니다. 생일 역설(birthday paradox)은 해시 테이블의 엔트리 수가 증가함에 따라 충돌 가능성이 매우 빠르게 증가한다는 것을 알려줍니다. 이를 줄이기 위해 큰 배열 크기를 선택할 수 있지만, 이는 지는 게임입니다. 해시 테이블에 100개의 항목을 저장하고 싶다고 가정해 봅시다. 충돌 확률을 여전히 꽤 높은 10% 미만으로 유지하려면 최소 47,015개 요소를 가진 배열이 필요합니다. 확률을 1% 미만으로 줄이려면 492,555개 요소가 있는 배열이 필요하며, 이는 사용 중인 각 버킷당 4,000개가 넘는 빈 버킷이 있다는 의미입니다.

낮은 로드 팩터는 충돌을 더 드물게 만들 수 있지만, 비둘기집 원리(pigeonhole principle)는 우리가 충돌을 완전히 제거할 수는 없다고 말합니다. 다섯 마리의 애완 비둘기와 네 개의 구멍이 있다면, 적어도 한 구멍에는 두 마리 이상의 비둘기가 들어가게 될 것입니다. 18,446,744,073,709,551,616개의 다른 변수 이름을 사용하면, 어떤 합리적인 크기의 배열이라도 잠재적으로 동일한 버킷에 여러 키가 들어갈 수 있습니다.

따라서 충돌이 발생하면 우아하게 처리해야 합니다. 프로그래밍 언어가 변수를 대부분의 경우에만 올바르게 찾을 수 있다면 사용자들은 좋아하지 않을 것입니다.

20 . 2 . 1개별 체이닝

충돌을 해결하는 기술은 크게 두 가지 범주로 나뉩니다. 첫 번째는 개별 체이닝(separate chaining)입니다. 각 버킷이 단일 엔트리를 포함하는 대신, 여러 엔트리의 컬렉션을 포함하도록 합니다. 고전적인 구현에서는 각 버킷이 엔트리들의 연결 리스트를 가리킵니다. 엔트리를 찾으려면 해당 버킷을 찾은 다음 일치하는 키를 가진 엔트리를 찾을 때까지 리스트를 따라갑니다.

모든 엔트리가 동일한 버킷에서 충돌하는 최악의 경우, 데이터 구조는 O(n) 탐색 시간을 가진 단일 정렬되지 않은 연결 리스트로 퇴보합니다. 실제로는 로드 팩터를 제어하고 엔트리가 버킷에 어떻게 분산되는지를 조정함으로써 이러한 상황을 피하기 쉽습니다. 일반적인 개별 체이닝 방식의 해시 테이블에서는 버킷에 한두 개 이상의 엔트리가 있는 경우는 드뭅니다.

개별 체이닝은 개념적으로 간단합니다—말 그대로 연결 리스트의 배열입니다. 대부분의 작업은 구현하기 쉽고, 삭제조차도(나중에 보겠지만) 고통스러울 수 있습니다. 하지만 현대 CPU에는 잘 맞지 않습니다. 포인터 오버헤드가 많고, 작은 연결 리스트 노드들이 메모리에 흩어지는 경향이 있어 캐시 사용에 좋지 않습니다.

20 . 2 . 2개방 주소 지정

다른 기술은 개방 주소 지정(open addressing) 또는 (혼란스럽게도) 폐쇄 해싱(closed hashing)이라고 불립니다. 이 기술에서는 모든 엔트리가 버킷 배열에 직접 위치하며, 버킷당 하나의 엔트리를 가집니다. 두 엔트리가 동일한 버킷에서 충돌하면, 대신 사용할 다른 빈 버킷을 찾습니다.

모든 엔트리를 하나의 크고 연속적인 배열에 저장하는 것은 메모리 표현을 단순하고 빠르게 유지하는 데 좋습니다. 하지만 해시 테이블의 모든 작업을 더 복잡하게 만듭니다. 엔트리를 삽입할 때, 해당 버킷이 가득 차서 다른 버킷을 찾아야 할 수 있습니다. 그 버킷 자체도 이미 점유되어 있을 수 있습니다. 이러한 사용 가능한 버킷을 찾는 과정을 탐색(probing)이라고 하며, 버킷을 검색하는 순서를 탐색 시퀀스(probe sequence)라고 합니다.

어떤 버킷을 탐색할지, 어떤 엔트리가 어떤 버킷에 들어갈지를 결정하는 알고리즘은 여러 가지가 있습니다. 미세한 조정조차도 성능에 큰 영향을 미칠 수 있기 때문에 이 분야에는 많은 연구가 있었습니다. 그리고 해시 테이블처럼 광범위하게 사용되는 데이터 구조에서는 이러한 성능 영향이 다양한 하드웨어 기능에 걸쳐 매우 많은 실제 프로그램에 영향을 미칩니다.

이 책에서 늘 그렇듯이, 효율적으로 작업을 수행하는 가장 간단한 방법을 선택할 것입니다. 그것은 바로 오래된 선형 탐색(linear probing)입니다. 엔트리를 찾을 때, 키가 매핑되는 첫 번째 버킷을 봅니다. 거기에 없으면 배열의 바로 다음 요소를 보고, 이런 식으로 계속합니다. 끝에 도달하면 다시 시작 부분으로 돌아갑니다.

선형 탐색의 좋은 점은 캐시 친화적(cache friendly)이라는 것입니다. 메모리 순서대로 배열을 직접 따라가기 때문에 CPU의 캐시 라인을 가득 채우고 효율적으로 유지합니다. 나쁜 점은 클러스터링(clustering)에 취약하다는 것입니다. 숫자적으로 유사한 키 값을 가진 엔트리가 많으면, 서로 옆에 많은 충돌하고 넘쳐나는 버킷이 생길 수 있습니다.

개별 체이닝과 비교할 때, 개방 주소 지정은 이해하기 더 어려울 수 있습니다. 저는 개방 주소 지정을 개별 체이닝과 비슷하지만 노드 "리스트"가 버킷 배열 자체를 통해 연결된 것으로 생각합니다. 노드들 사이의 링크를 포인터에 저장하는 대신, 연결은 버킷을 찾아보는 순서에 의해 암시적으로 계산됩니다.

까다로운 부분은 이러한 암시적 리스트 중 하나 이상이 서로 섞여 있을 수 있다는 것입니다. 모든 흥미로운 경우를 다루는 예제를 살펴보겠습니다. 지금은 값을 무시하고 키 집합에 대해서만 다루겠습니다. 8개의 빈 버킷으로 이루어진 배열에서 시작합니다.

"bagel"을 삽입하기로 결정합니다. 첫 글자 'b'(ASCII 값 98)를 배열 크기(8)로 모듈로 연산하면 버킷 2에 위치합니다.

다음으로 "jam"을 삽입합니다. 이것도 버킷 2에 들어가고 싶어 하지만(106 mod 8 = 2), 그 버킷은 이미 사용 중입니다. 다음 버킷으로 계속 탐색합니다. 그 버킷은 비어 있으므로 그곳에 넣습니다.

"fruit"을 삽입하면, 다행히도 버킷 6에 저장됩니다.

마찬가지로, "migas"는 선호하는 버킷 5에 들어갈 수 있습니다.

"eggs"를 삽입하려고 할 때, 이것도 버킷 5에 들어가고 싶어 합니다. 그 버킷은 꽉 차서 6으로 건너뜁니다. 버킷 6도 꽉 찼습니다. 여기에 있는 엔트리는 동일한 탐색 시퀀스의 일부가 아니라는 점에 유의하세요. "Fruit"는 선호하는 버킷 6에 있습니다. 그래서 5와 6 시퀀스가 충돌하여 서로 얽혀 있습니다. 우리는 이를 건너뛰고 마침내 "eggs"를 버킷 7에 넣습니다.

"nuts"에서도 비슷한 문제가 발생합니다. 원하는 대로 6에 들어갈 수 없습니다. 7에도 들어갈 수 없습니다. 그래서 계속 진행합니다. 하지만 배열의 끝에 도달했으므로 0으로 다시 래핑하여 그곳에 넣습니다.

실제로 인터리빙은 큰 문제가 되지 않습니다. 개별 체이닝에서도 동일한 버킷으로 축소될 수 있는 여러 키 때문에 각 엔트리의 키를 확인하기 위해 리스트를 따라가야 합니다. 개방 주소 지정에서는 동일한 검사를 수행해야 하며, 이는 "다른 원래 버킷에 속하는" 엔트리를 건너뛰는 경우도 포함합니다.

20 . 3해시 함수

이제 최대 8자 길이의 변수 이름을 저장할 수 있는 합리적으로 효율적인 테이블을 구축할 수 있지만, 이 제한은 여전히 불편합니다. 마지막 제약을 완화하려면 어떤 길이의 문자열이든 고정 크기 정수로 변환하는 방법이 필요합니다.

마침내 "해시 테이블"의 "해시" 부분에 도달했습니다. 해시 함수(hash function)는 일부 더 큰 데이터 덩어리를 "해시"하여 원래 데이터의 모든 비트에 따라 값이 달라지는 고정 크기 정수 해시 코드(hash code)를 생성합니다. 좋은 해시 함수는 세 가지 주요 목표를 가집니다:

• 결정적(deterministic)이어야 합니다. 동일한 입력은 항상 동일한 숫자로 해시되어야 합니다. 동일한 변수가 다른 시점에 다른 버킷에 저장된다면 찾기가 정말 어려워질 것입니다.

• 균등해야(uniform) 합니다. 일반적인 입력 집합이 주어졌을 때, 가능한 한 적은 뭉침이나 패턴으로 넓고 고르게 분포된 출력 숫자의 범위를 생성해야 합니다. 충돌과 클러스터링을 최소화하기 위해 전체 숫자 범위에 걸쳐 값을 분산시키기를 원합니다.

• 빨라야(fast) 합니다. 해시 테이블의 모든 작업은 먼저 키를 해시해야 합니다. 해싱이 느리다면, 기본 배열 저장소의 속도를 잠재적으로 상쇄시킬 수 있습니다.

세상에는 정말 많은 해시 함수가 있습니다. 일부는 오래되었고 아무도 더 이상 사용하지 않는 아키텍처에 최적화되어 있습니다. 일부는 빠르도록 설계되었고, 다른 일부는 암호학적으로 안전하도록 설계되었습니다. 일부는 특정 칩의 벡터 명령어와 캐시 크기를 활용하고, 다른 일부는 이식성을 극대화하는 것을 목표로 합니다.

해시 함수를 설계하고 평가하는 것이 마치 그들의 전문 분야인 사람들이 있습니다. 저는 그들을 존경하지만, 제가 그들 중 하나가 될 만큼 수학적으로 예리하지는 않습니다. 그래서 clox에서는 수년 동안 저에게 잘 작동했던 FNV-1a라는 간단하고 오래된 해시 함수를 선택했습니다. 여러분의 코드에서 다른 함수들을 시도해보고 차이가 있는지 확인해 보세요.

자, 버킷, 로드 팩터, 개방 주소 지정, 충돌 해결, 그리고 해시 함수에 대한 간략한 설명이었습니다. 너무 많은 텍스트와 실제 코드는 많지 않았네요. 여전히 모호하게 느껴진다고 해도 걱정하지 마세요. 코딩을 마친 후에는 모든 것이 제자리를 찾을 것입니다.

20 . 4해시 테이블 구축

균형 이진 탐색 트리와 같은 다른 고전적인 기술에 비해 해시 테이블의 가장 큰 장점은 실제 데이터 구조가 매우 간단하다는 것입니다. 우리의 해시 테이블은 새로운 모듈에 들어갑니다.

#ifndef clox_table_h
#define clox_table_h

#include "common.h"
#include "value.h"

typedef struct {
  int count;
  int capacity;
  Entry* entries;
} Table;

#endif

해시 테이블은 엔트리 배열입니다. 이전에 만든 동적 배열과 마찬가지로, 배열의 할당된 크기(capacity)와 현재 저장된 키/값 쌍의 수(count) 모두를 추적합니다. count와 capacity의 비율이 정확히 해시 테이블의 로드 팩터입니다.

각 엔트리는 다음과 같습니다:

#include "value.h"

typedef struct {
  ObjString* key;
  Value value;
} Entry;

typedef struct {

단순한 키/값 쌍입니다. 키는 항상 문자열이므로, Value로 감싸는 대신 ObjString 포인터를 직접 저장합니다. 이렇게 하면 조금 더 빠르고 작아집니다.

새로운 빈 해시 테이블을 생성하기 위해 생성자(constructor)와 유사한 함수를 선언합니다.

} Table;

void initTable(Table* table);

#endif

이를 정의하기 위한 새로운 구현 파일이 필요합니다. 겸사겸사, 모든 성가신 include를 먼저 처리합시다.

#include <stdlib.h>
#include <string.h>

#include "memory.h"
#include "object.h"
#include "table.h"
#include "value.h"

void initTable(Table* table) {
  table->count = 0;
  table->capacity = 0;
  table->entries = NULL;
}

동적 값 배열 타입과 마찬가지로, 해시 테이블은 초기에는 0 용량과 NULL 배열로 시작합니다. 필요할 때까지 아무것도 할당하지 않습니다. 결국 뭔가를 할당한다고 가정하면, 나중에 해제할 수도 있어야 합니다.

void initTable(Table* table);

void freeTable(Table* table);

#endif

그리고 그 훌륭한 구현:

void freeTable(Table* table) {
  FREE_ARRAY(Entry, table->entries, table->capacity);
  initTable(table);
}

다시 말하지만, 동적 배열과 똑같아 보입니다. 사실, 해시 테이블을 아이템을 삽입하는 방식이 정말 이상한 동적 배열이라고 생각할 수 있습니다. 여기서는 NULL을 확인할 필요가 없습니다. FREE_ARRAY()가 이미 이를 우아하게 처리하기 때문입니다.

20 . 4 . 1문자열 해싱

테이블에 엔트리를 넣기 전에, 우선 해싱해야 합니다. 엔트리가 배열 전체에 균일하게 분산되도록 하려면 키 문자열의 모든 비트를 고려하는 좋은 해시 함수가 필요합니다. 만약 처음 몇 문자만 본다면, 동일한 접두사를 공유하는 일련의 문자열들이 모두 동일한 버킷에서 충돌하게 될 것입니다.

반면에 전체 문자열을 걸쳐 해시를 계산하는 것은 다소 느립니다. 테이블에서 키를 찾을 때마다 문자열을 걸쳐야 한다면 해시 테이블의 성능 이점 일부를 잃게 될 것입니다. 그래서 명백한 방법을 사용할 것입니다: 캐싱입니다.

"object" 모듈의 ObjString에 다음을 추가합니다:

  char* chars;

  uint32_t hash;

};

각 ObjString은 해당 문자열의 해시 코드를 저장합니다. Lox에서 문자열은 불변이므로, 해시 코드를 한 번만 계산하고 나중에 무효화되지 않을 것이라고 확신할 수 있습니다. 이를 미리 캐싱하는 것은 일종의 이치에 맞습니다. 문자열을 할당하고 문자를 복사하는 것은 이미 O(n) 작업이므로, 문자열 해시를 O(n)으로 계산하기에 좋은 시기입니다.

문자열을 할당하는 내부 함수를 호출할 때마다, 해당 해시 코드를 전달합니다.

static ObjString* allocateString(char* chars, int length,
                                 uint32_t hash) {

  ObjString* string = ALLOCATE_OBJ(ObjString, OBJ_STRING);

이 함수는 단순히 해시를 구조체에 저장합니다.

  string->chars = chars;

  string->hash = hash;

  return string;
}

재미있는 부분은 호출하는 곳에 있습니다. allocateString()은 두 군데에서 호출됩니다. 하나는 문자열을 복사하는 함수이고, 다른 하나는 기존에 동적으로 할당된 문자열의 소유권을 가져오는 함수입니다. 첫 번째부터 시작합시다.

ObjString* copyString(const char* chars, int length) {

  uint32_t hash = hashString(chars, length);

  char* heapChars = ALLOCATE(char, length + 1);

여기에는 마법이 없습니다. 해시 코드를 계산한 다음 전달합니다.

  memcpy(heapChars, chars, length);
  heapChars[length] = '\0';

  return allocateString(heapChars, length, hash);

}

다른 문자열 함수도 비슷합니다.

ObjString* takeString(char* chars, int length) {

  uint32_t hash = hashString(chars, length);
  return allocateString(chars, length, hash);

}

흥미로운 코드는 여기에 있습니다:

static uint32_t hashString(const char* key, int length) {
  uint32_t hash = 2166136261u;
  for (int i = 0; i < length; i++) {
    hash ^= (uint8_t)key[i];
    hash *= 16777619;
  }
  return hash;
}

이것이 clox의 실제 "해시 함수"입니다. 이 알고리즘은 "FNV-1a"라고 불리며, 제가 아는 가장 짧고 괜찮은 해시 함수입니다. 모든 코드 라인을 보여주는 책에서는 간결함이 분명한 미덕입니다.

기본 아이디어는 꽤 간단하며, 많은 해시 함수가 동일한 패턴을 따릅니다. 일반적으로 신중하게 선택된 수학적 속성을 가진 상수 값으로 초기 해시 값을 시작합니다. 그런 다음 해시할 데이터를 탐색합니다. 각 바이트(또는 때로는 워드)에 대해 비트를 해시 값에 어떤 방식으로든 혼합한 다음, 결과 비트들을 섞어줍니다.

"혼합(mix)"하고 "섞는(scramble)" 것이 무엇을 의미하는지는 매우 정교해질 수 있습니다. 궁극적으로 기본 목표는 균일성(uniformity)입니다—결과 해시 값이 충돌과 클러스터링을 피하기 위해 숫자 범위 전체에 가능한 한 넓게 분산되기를 원합니다.

20 . 4 . 2엔트리 삽입

이제 문자열 객체가 해시 코드를 알게 되었으므로, 해시 테이블에 넣기 시작할 수 있습니다.

void freeTable(Table* table);

bool tableSet(Table* table, ObjString* key, Value value);

#endif

이 함수는 주어진 키/값 쌍을 주어진 해시 테이블에 추가합니다. 해당 키에 대한 엔트리가 이미 존재하면 새 값이 이전 값을 덮어씁니다. 이 함수는 새로운 엔트리가 추가되었으면 true를 반환합니다. 구현은 다음과 같습니다:

bool tableSet(Table* table, ObjString* key, Value value) {
  Entry* entry = findEntry(table->entries, table->capacity, key);
  bool isNewKey = entry->key == NULL;
  if (isNewKey) table->count++;

  entry->key = key;
  entry->value = value;
  return isNewKey;
}

흥미로운 로직의 대부분은 곧 다룰 findEntry()에 있습니다. 이 함수의 역할은 키를 받아서 배열의 어느 버킷에 엔트리가 들어가야 하는지를 알아내는 것입니다. 이는 해당 버킷의 포인터—배열에 있는 Entry의 주소—를 반환합니다.

버킷을 얻으면 삽입은 간단합니다. 해시 테이블의 크기를 업데이트하는데, 이미 존재하는 키의 값을 덮어쓴 경우 count를 증가시키지 않도록 주의합니다. 그런 다음 키와 값을 Entry의 해당 필드에 복사합니다.

하지만 여기 뭔가 빠진 게 있습니다. 아직 Entry 배열을 할당하지 않았습니다. 이런! 무엇이든 삽입하기 전에 배열이 있고 충분히 큰지 확인해야 합니다.

bool tableSet(Table* table, ObjString* key, Value value) {

  if (table->count + 1 > table->capacity * TABLE_MAX_LOAD) {
    int capacity = GROW_CAPACITY(table->capacity);
    adjustCapacity(table, capacity);
  }

  Entry* entry = findEntry(table->entries, table->capacity, key);

이것은 이전에 동적 배열을 확장하기 위해 작성했던 코드와 비슷합니다. 항목을 삽입할 충분한 용량이 없으면 배열을 재할당하고 확장합니다. GROW_CAPACITY() 매크로는 기존 용량을 가져와서 여러 번 확장하여 일련의 삽입 작업에서 분할 상환 상수 시간 성능을 보장합니다.

여기서 흥미로운 차이점은 TABLE_MAX_LOAD 상수입니다.

#include "value.h"

#define TABLE_MAX_LOAD 0.75

void initTable(Table* table) {

이것이 테이블의 로드 팩터를 관리하는 방식입니다. 용량이 완전히 찼을 때만 확장하지 않습니다. 대신, 배열이 최소 75% 가득 찼을 때 미리 배열을 확장합니다.

adjustCapacity()의 구현은 곧 살펴볼 것입니다. 먼저, 여러분이 궁금해 했던 findEntry() 함수를 살펴보겠습니다.

static Entry* findEntry(Entry* entries, int capacity,
                        ObjString* key) {
  uint32_t index = key->hash % capacity;
  for (;;) {
    Entry* entry = &entries[index];
    if (entry->key == NULL || entry->key == key) {
      return entry;
    }

    index = (index + 1) % capacity;
  }
}

이 함수는 해시 테이블의 진정한 핵심입니다. 키와 버킷 배열을 받아서 엔트리가 속해야 할 버킷을 찾아내는 역할을 합니다. 이 함수는 또한 선형 탐색과 충돌 처리가 작동하는 곳입니다. findEntry()는 해시 테이블에서 기존 엔트리를 찾고 새로운 엔트리를 어디에 삽입할지 결정하는 데 사용됩니다.

그럼에도 불구하고 크게 복잡한 부분은 없습니다. 먼저, 모듈로 연산을 사용하여 키의 해시 코드를 배열 범위 내의 인덱스로 매핑합니다. 이는 이상적으로 엔트리를 찾거나 배치할 수 있는 버킷 인덱스를 제공합니다.

확인해야 할 몇 가지 경우가 있습니다:

• 해당 배열 인덱스에 있는 Entry의 키가 NULL이면 버킷이 비어 있습니다. findEntry()를 사용하여 해시 테이블에서 무언가를 찾는 경우, 이는 해당 항목이 없다는 것을 의미합니다. 삽입하는 데 사용하는 경우, 새 엔트리를 추가할 위치를 찾았다는 의미입니다.

• 버킷에 있는 키가 우리가 찾고 있는 키와 같다면, 해당 키는 이미 테이블에 존재합니다. 조회 중이라면 좋습니다—우리가 찾던 키를 발견했습니다. 삽입 중이라면, 새 엔트리를 추가하는 대신 해당 키의 값을 대체하게 될 것입니다.

• 그렇지 않으면 버킷에 엔트리가 있지만 다른 키를 가지고 있습니다. 이것은 충돌입니다. 이 경우, 탐색을 시작합니다. 이것이 for 루프가 하는 일입니다. 엔트리가 이상적으로 들어갈 버킷에서 시작합니다. 그 버킷이 비어 있거나 동일한 키를 가지고 있다면, 우리는 작업을 마친 것입니다. 그렇지 않으면 다음 요소로 이동하고—이것이 "선형 탐색"의 선형(linear) 부분입니다—그곳을 확인합니다. 배열의 끝을 지나면 두 번째 모듈로 연산자가 우리를 시작 부분으로 다시 래핑합니다.

빈 버킷이나 찾고 있는 키와 동일한 키를 가진 버킷을 찾으면 루프를 종료합니다. 무한 루프에 대해 궁금할 수도 있습니다. 모든 버킷과 충돌한다면 어떨까요? 다행히도, 로드 팩터 덕분에 그런 일은 발생할 수 없습니다. 배열이 거의 가득 차면 즉시 확장하기 때문에 항상 빈 버킷이 있다는 것을 알고 있습니다.

루프 내에서 직접 반환하여 찾은 Entry에 대한 포인터를 반환하므로, 호출자는 여기에 무언가를 삽입하거나 읽을 수 있습니다. tableSet() 함수에서 이 과정을 처음 시작했는데, 반환된 버킷에 새 엔트리를 저장하면 작업이 완료됩니다.

20 . 4 . 3할당 및 크기 조정

해시 테이블에 엔트리를 넣기 전에, 실제로 저장할 공간이 필요합니다. 버킷 배열을 할당해야 합니다. 이 함수에서 이루어집니다:

static void adjustCapacity(Table* table, int capacity) {
  Entry* entries = ALLOCATE(Entry, capacity);
  for (int i = 0; i < capacity; i++) {
    entries[i].key = NULL;
    entries[i].value = NIL_VAL;
  }

  table->entries = entries;
  table->capacity = capacity;
}

capacity개의 엔트리를 가진 버킷 배열을 생성합니다. 배열을 할당한 후, 모든 요소를 빈 버킷으로 초기화하고 배열(및 그 용량)을 해시 테이블의 주 구조체에 저장합니다. 이 코드는 테이블에 첫 번째 엔트리를 삽입할 때와 배열의 첫 할당이 필요할 때 잘 작동합니다. 하지만 이미 배열이 있고 확장해야 할 때는 어떨까요?

이전에 동적 배열을 만들었을 때는 realloc()을 사용하고 C 표준 라이브러리가 모든 것을 복사하도록 할 수 있었습니다. 하지만 해시 테이블에는 그렇게 할 수 없습니다. 각 엔트리에 대한 버킷을 선택하기 위해 해시 키를 배열 크기로 모듈로 연산한다는 것을 기억하세요. 이는 배열 크기가 변경되면 엔트리가 다른 버킷에 저장될 수 있다는 것을 의미합니다.

새로운 버킷은 우리가 처리해야 할 새로운 충돌을 가질 수 있습니다. 따라서 모든 엔트리를 제자리에 놓는 가장 간단한 방법은 모든 엔트리를 새로운 빈 배열에 다시 삽입하여 테이블을 처음부터 다시 구축하는 것입니다.

    entries[i].value = NIL_VAL;
  }

  for (int i = 0; i < table->capacity; i++) {
    Entry* entry = &table->entries[i];
    if (entry->key == NULL) continue;

    Entry* dest = findEntry(entries, capacity, entry->key);
    dest->key = entry->key;
    dest->value = entry->value;
  }

  table->entries = entries;

우리는 이전 배열을 앞에서부터 뒤로 순회합니다. 비어 있지 않은 버킷을 찾을 때마다 해당 엔트리를 새 배열에 삽입합니다. findEntry()를 사용하는데, 현재 테이블에 저장된 배열 대신 새로운 배열을 전달합니다. (이것이 findEntry()가 전체 Table 구조체 대신 Entry 배열에 대한 포인터를 직접 받는 이유입니다. 이렇게 하면 새 배열과 용량을 구조체에 저장하기 전에 전달할 수 있습니다.)

이 작업이 완료되면 이전 배열의 메모리를 해제할 수 있습니다.

    dest->value = entry->value;
  }

  FREE_ARRAY(Entry, table->entries, table->capacity);

  table->entries = entries;

이것으로 원하는 만큼 많은 엔트리를 채울 수 있는 해시 테이블이 완성되었습니다. 기존 키 덮어쓰기를 처리하고, 필요한 경우 원하는 로드 용량을 유지하기 위해 자체적으로 확장됩니다.

겸사겸사, 한 해시 테이블의 모든 엔트리를 다른 해시 테이블로 복사하는 헬퍼 함수도 정의합시다.

bool tableSet(Table* table, ObjString* key, Value value);

void tableAddAll(Table* from, Table* to);

#endif

메서드 상속을 지원할 때까지는 필요하지 않겠지만, 해시 테이블 관련 지식이 새로운 지금 구현해두는 것도 나쁘지 않습니다.

void tableAddAll(Table* from, Table* to) {
  for (int i = 0; i < from->capacity; i++) {
    Entry* entry = &from->entries[i];
    if (entry->key != NULL) {
      tableSet(to, entry->key, entry->value);
    }
  }
}

이것에 대해 특별히 할 말은 많지 않습니다. 원본 해시 테이블의 버킷 배열을 순회합니다. 비어 있지 않은 버킷을 찾을 때마다 최근에 정의한 tableSet() 함수를 사용하여 엔트리를 대상 해시 테이블에 추가합니다.

20 . 4 . 4값 검색

이제 해시 테이블에 내용이 들어갔으니, 다시 내용을 꺼내봅시다. 키가 주어지면, 해당 값이 있다면 다음 함수로 찾을 수 있습니다:

void freeTable(Table* table);

bool tableGet(Table* table, ObjString* key, Value* value);

bool tableSet(Table* table, ObjString* key, Value value);

테이블과 키를 전달합니다. 해당 키를 가진 엔트리를 찾으면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 엔트리가 존재하면, value 출력 파라미터가 결과 값을 가리킵니다.

findEntry()가 이미 어려운 작업을 수행했으므로, 구현은 어렵지 않습니다.

bool tableGet(Table* table, ObjString* key, Value* value) {
  if (table->count == 0) return false;

  Entry* entry = findEntry(table->entries, table->capacity, key);
  if (entry->key == NULL) return false;

  *value = entry->value;
  return true;
}

테이블이 완전히 비어 있으면 엔트리를 찾을 수 없으므로, 먼저 이를 확인합니다. 이것은 단순히 최적화가 아니라—배열이 NULL일 때 버킷 배열에 접근하려고 시도하지 않도록 보장합니다. 그렇지 않으면, findEntry()가 마법을 부리도록 합니다. 이는 버킷에 대한 포인터를 반환합니다. 키가 NULL인지 확인하여 버킷이 비어 있으면, 해당 키를 가진 엔트리를 찾지 못한 것입니다. findEntry()가 비어 있지 않은 Entry를 반환하면, 그것이 우리가 찾는 것입니다. Entry의 값을 가져와 출력 파라미터에 복사하여 호출자가 가져갈 수 있도록 합니다. 식은 죽 먹기죠.

20 . 4 . 5엔트리 삭제

완전한 기능을 갖춘 해시 테이블이 지원해야 할 한 가지 근본적인 작업이 더 있습니다. 바로 엔트리 삭제입니다. 무언가를 추가할 수 있다면, 제거할 수도 있어야 하는 것이 당연해 보이죠? 하지만 해시 테이블에 대한 많은 튜토리얼이 이 부분을 생략한다는 사실에 놀랄 수도 있습니다.

저도 그 길을 택할 수도 있었습니다. 사실, clox에서는 VM의 아주 작은 예외적인 경우에만 삭제를 사용합니다. 하지만 해시 테이블을 완전히 구현하는 방법을 실제로 이해하고 싶다면, 이 부분이 중요하다고 느껴집니다. 그들이 이 부분을 간과하려는 마음에 공감할 수 있습니다. 보시다시피, 개방 주소 지정을 사용하는 해시 테이블에서 삭제하는 것은 까다롭습니다.

적어도 선언은 간단합니다.

bool tableSet(Table* table, ObjString* key, Value value);

bool tableDelete(Table* table, ObjString* key);

void tableAddAll(Table* from, Table* to);

명백한 접근 방식은 삽입을 반영하는 것입니다. findEntry()를 사용하여 엔트리의 버킷을 찾습니다. 그런 다음 버킷을 비웁니다. 완료!

충돌이 없는 경우에는 잘 작동합니다. 하지만 충돌이 발생한 경우, 엔트리가 있는 버킷은 하나 이상의 암시적 탐색 시퀀스의 일부일 수 있습니다. 예를 들어, 세 개의 키가 모두 선호하는 버킷 2를 가지는 해시 테이블이 있습니다:

탐색 시퀀스를 따라 엔트리를 찾을 때, 빈 버킷을 만나면 시퀀스의 끝에 도달했으며 엔트리가 없다는 것을 알게 된다는 것을 기억하세요. 마치 탐색 시퀀스가 엔트리 리스트이고 빈 엔트리가 그 리스트를 종결하는 것과 같습니다.

"biscuit"을 단순히 Entry를 지움으로써 삭제하면, 탐색 시퀀스가 중간에서 끊어져 뒤따르는 엔트리들이 고아 상태가 되어 도달할 수 없게 됩니다. 마치 연결 리스트에서 이전 노드의 포인터를 다음 노드로 다시 연결하지 않고 노드를 제거하는 것과 같습니다.

나중에 "jam"을 찾으려고 하면, "bagel"에서 시작하여 다음 빈 Entry에서 멈추고, 결국 찾지 못하게 될 것입니다.

이 문제를 해결하기 위해 대부분의 구현에서는 툼스톤(tombstones)이라고 불리는 트릭을 사용합니다. 삭제 시 엔트리를 지우는 대신, 특별한 감시 엔트리인 "툼스톤"으로 대체합니다. 조회 중에 탐색 시퀀스를 따르다가 툼스톤을 만나면, 이를 빈 슬롯처럼 취급하고 반복을 중단하지 않습니다. 대신, 계속 진행하여 엔트리 삭제가 암시적인 충돌 체인을 끊지 않고 그 뒤의 엔트리도 계속 찾을 수 있도록 합니다.

코드는 다음과 같습니다:

bool tableDelete(Table* table, ObjString* key) {
  if (table->count == 0) return false;

  // Find the entry.
  Entry* entry = findEntry(table->entries, table->capacity, key);
  if (entry->key == NULL) return false;

  // Place a tombstone in the entry.
  entry->key = NULL;
  entry->value = BOOL_VAL(true);
  return true;
}

먼저, 삭제하려는 엔트리가 포함된 버킷을 찾습니다. (찾지 못하면 삭제할 것이 없으므로 빠져나옵니다.) 엔트리를 툼스톤으로 대체합니다. clox에서는 NULL 키와 true 값을 사용하여 이를 나타내지만, 빈 버킷이나 유효한 엔트리와 혼동되지 않는 어떤 표현도 작동합니다.

엔트리를 삭제하는 데 필요한 것은 이것뿐입니다. 간단하고 빠릅니다. 하지만 다른 모든 작업도 툼스톤을 올바르게 처리해야 합니다. 툼스톤은 일종의 "절반" 엔트리입니다. 현재 엔트리의 특성 일부와 빈 엔트리의 특성 일부를 가집니다.

조회 중에 탐색 시퀀스를 따라가다가 툼스톤을 만나면, 이를 기록하고 계속 진행합니다.

  for (;;) {
    Entry* entry = &entries[index];

    if (entry->key == NULL) {
      if (IS_NIL(entry->value)) {
        // Empty entry.
        return tombstone != NULL ? tombstone : entry;
      } else {
        // We found a tombstone.
        if (tombstone == NULL) tombstone = entry;
      }
    } else if (entry->key == key) {
      // We found the key.
      return entry;
    }

    index = (index + 1) % capacity;

툼스톤을 처음 지나갈 때, 이 지역 변수에 저장합니다:

  uint32_t index = key->hash % capacity;

  Entry* tombstone = NULL;

  for (;;) {

만약 우리가 정말로 빈 엔트리에 도달하면, 키는 존재하지 않는 것입니다. 이 경우, 툼스톤을 지나쳤다면 나중에 나오는 빈 버킷 대신 그 버킷을 반환합니다. 노드를 삽입하기 위해 findEntry()를 호출하는 경우, 이를 통해 툼스톤 버킷을 빈 것으로 취급하고 새 엔트리에 재사용할 수 있습니다.

툼스톤 슬롯을 이렇게 자동으로 재사용하는 것은 버킷 배열에서 낭비되는 툼스톤의 수를 줄이는 데 도움이 됩니다. 삽입과 삭제가 혼합된 일반적인 사용 사례에서는 툼스톤 수가 잠시 증가하다가 안정화되는 경향이 있습니다.

그럼에도 불구하고, 많은 수의 삭제가 배열을 툼스톤으로 가득 채우지 않는다는 보장은 없습니다. 최악의 경우, 실제로 빈 버킷이 하나도 없을 수 있습니다. 이것은 좋지 않을 것입니다. 왜냐하면 findEntry()에서 무한 루프를 방지하는 유일한 방법은 결국 빈 버킷을 만나게 될 것이라는 가정이기 때문입니다.

따라서 툼스톤이 테이블의 로드 팩터 및 크기 조정과 어떻게 상호 작용하는지 신중하게 고려해야 합니다. 핵심 질문은, 로드 팩터를 계산할 때 툼스톤을 가득 찬 버킷처럼 취급해야 하는가, 아니면 빈 버킷처럼 취급해야 하는가입니다.

20 . 4 . 6툼스톤 세기

툼스톤을 가득 찬 버킷처럼 취급하면, 로드 팩터를 인위적으로 부풀려 필요 이상으로 큰 배열을 사용하게 될 수 있습니다. 재사용할 수 있는 툼스톤이 있지만, 사용되지 않은 것으로 취급되지 않으므로 배열을 조기에 확장하게 됩니다.

하지만 툼스톤을 빈 버킷처럼 취급하여 로드 팩터에 포함시키지 않는다면, 탐색을 종료할 실제 빈 버킷이 전혀 없을 위험이 있습니다. 무한 루프는 몇 개의 추가 배열 슬롯보다 훨씬 더 나쁜 문제이므로, 로드 팩터 계산 시 툼스톤을 가득 찬 버킷으로 간주합니다.

이것이 이전 코드에서 엔트리를 삭제할 때 count를 줄이지 않는 이유입니다. count는 더 이상 해시 테이블의 엔트리 수가 아니라, 엔트리 수와 툼스톤 수의 합입니다. 이는 삽입 시 새 엔트리가 완전히 빈 버킷에 들어갈 때만 count를 증가시킨다는 것을 의미합니다.

  bool isNewKey = entry->key == NULL;

  if (isNewKey && IS_NIL(entry->value)) table->count++;

  entry->key = key;

툼스톤을 새로운 엔트리로 교체하는 경우, 버킷은 이미 계산되었으므로 count는 변경되지 않습니다.

배열 크기를 조정할 때, 새 배열을 할당하고 기존 엔트리들을 모두 다시 삽입합니다. 이 과정에서 툼스톤은 복사하지 않습니다. 어차피 탐색 시퀀스를 재구축하기 때문에 아무런 가치도 추가하지 않으며, 조회 속도만 늦출 것입니다. 이는 크기 조정 중에 count가 변경될 수 있으므로 다시 계산해야 한다는 의미입니다. 따라서 count를 초기화합니다:

  }

  table->count = 0;

  for (int i = 0; i < table->capacity; i++) {

그런 다음 툼스톤이 아닌 엔트리를 찾을 때마다 count를 증가시킵니다.

    dest->value = entry->value;

    table->count++;

  }

이는 용량을 늘릴 때, 모든 툼스톤이 버려지기 때문에 결과적으로 더 큰 배열에 더 적은 엔트리가 있을 수 있다는 것을 의미합니다. 약간 낭비적이지만, 실질적인 큰 문제는 아닙니다.

엔트리 삭제를 지원하는 작업의 대부분이 findEntry()와 adjustCapacity()에 있다는 점이 흥미롭습니다. 실제 삭제 로직은 아주 간단하고 빠릅니다. 실제로 삭제는 드물게 발생하므로, 해시 테이블은 삭제 함수에서 가능한 많은 작업을 수행하고 다른 함수들은 더 빠르게 유지하도록 할 것이라고 기대할 수 있습니다. 툼스톤 접근 방식으로는 삭제는 빠르지만, 조회는 성능 저하를 겪습니다.

저는 몇 가지 다른 삭제 시나리오에서 이를 테스트하기 위해 약간의 벤치마킹을 했습니다. 툼스톤 방식이 영향을 받는 엔트리들을 다시 삽입하는 모든 작업을 삭제 중에 하는 것보다 전반적으로 더 빠르다는 것을 발견하고 놀랐습니다.

하지만 생각해보면, 툼스톤 방식은 엔트리를 완전히 삭제하는 작업을 다른 연산으로 미루는 것이 아니라, 삭제를 게으르게 만듭니다. 처음에는 엔트리를 툼스톤으로 바꾸는 최소한의 작업만 합니다. 이는 나중에 조회가 툼스톤을 건너뛰어야 할 때 성능 저하를 야기할 수 있습니다. 하지만 나중에 삽입되는 엔트리가 툼스톤 버킷을 재사용할 수도 있습니다. 이 재사용은 영향을 받는 모든 후속 엔트리를 재정렬하는 비용을 피하는 매우 효율적인 방법입니다. 탐색된 엔트리 체인에서 노드를 기본적으로 재활용하는 것입니다. 재미있는 트릭입니다.

20 . 5문자열 인터닝

거의 작동하는 해시 테이블을 만들었지만, 중심부에 치명적인 결함이 있습니다. 또한 아직 아무것도 사용하고 있지 않습니다. 이제 두 가지 모두를 해결하고, 그 과정에서 인터프리터에서 사용되는 고전적인 기술을 배울 때입니다.

해시 테이블이 완전히 작동하지 않는 이유는 findEntry()가 기존 키가 찾고 있는 키와 일치하는지 확인할 때 ==를 사용하여 두 문자열의 동등성을 비교하기 때문입니다. 이는 두 키가 메모리에서 정확히 동일한 문자열인 경우에만 true를 반환합니다. 동일한 문자를 가진 두 개의 별개 문자열은 같다고 간주되어야 하지만, 그렇지 않습니다.

지난 장에서 문자열을 추가했을 때, 문자열의 참 값 동등성을 얻기 위해 문자별 비교를 명시적으로 지원했음을 기억하세요. findEntry()에서도 그렇게 할 수 있지만, 그것은 느립니다.

대신, 문자열 인터닝(string interning)이라는 기술을 사용할 것입니다. 핵심 문제는 동일한 문자를 가진 다른 문자열이 메모리에 존재할 수 있다는 것입니다. 이들은 별개의 객체임에도 불구하고 동등한 값처럼 작동해야 합니다. 본질적으로 중복이며, 이를 감지하기 위해 모든 바이트를 비교해야 합니다.

문자열 인터닝은 중복 제거 과정입니다. 우리는 "인터닝된" 문자열 컬렉션을 생성합니다. 이 컬렉션에 있는 어떤 문자열도 다른 모든 문자열과 텍스트적으로 구별된다는 것이 보장됩니다. 문자열을 인터닝할 때, 컬렉션에서 일치하는 문자열을 찾습니다. 찾으면 원래 문자열을 사용합니다. 그렇지 않으면, 가지고 있는 문자열이 고유하므로 컬렉션에 추가합니다.

이러한 방식으로, 각 문자 시퀀스는 메모리에서 단 하나의 문자열로만 표현된다는 것을 알 수 있습니다. 이것은 값 동등성을 사소하게 만듭니다. 두 문자열이 메모리에서 동일한 주소를 가리키면, 명백히 같은 문자열이며 동등해야 합니다. 그리고 문자열이 고유하다는 것을 알기 때문에, 두 문자열이 다른 주소를 가리키면, 서로 다른 문자열임에 틀림없습니다.

따라서 포인터 동등성은 값 동등성과 정확히 일치합니다. 이는 결과적으로 findEntry()의 기존 ==가 올바르게 작동한다는 의미입니다. 적어도 모든 문자열을 인터닝하면 그렇게 될 것입니다. 모든 문자열을 안정적으로 중복 제거하려면, VM은 생성된 모든 문자열을 찾을 수 있어야 합니다. 이를 위해 모든 문자열을 저장할 해시 테이블을 제공합니다.

  Value* stackTop;

  Table strings;

  Obj* objects;

늘 그렇듯이, include가 필요합니다.

#include "chunk.h"

#include "table.h"

#include "value.h"

새 VM을 시작할 때, 문자열 테이블은 비어 있습니다.

  vm.objects = NULL;

  initTable(&vm.strings);

}

그리고 VM을 종료할 때는 테이블에서 사용된 모든 리소스를 정리합니다.

void freeVM() {

  freeTable(&vm.strings);

  freeObjects();

일부 언어는 문자열을 인터닝하기 위한 별도의 타입이나 명시적인 단계를 가지고 있습니다. clox의 경우, 모든 문자열을 자동으로 인터닝할 것입니다. 이는 새로운 고유 문자열을 생성할 때마다 테이블에 추가한다는 의미입니다.

  string->hash = hash;

  tableSet(&vm.strings, string, NIL_VAL);

  return string;

이것은 문자열이 고유하다고 가정하고 테이블에 문자열을 넣지만, 여기에 도달하기 전에 실제로 중복을 확인해야 합니다. allocateString()을 호출하는 두 개의 상위 레벨 함수에서 이 작업을 수행합니다. 여기 하나가 있습니다:

  uint32_t hash = hashString(chars, length);

  ObjString* interned = tableFindString(&vm.strings, chars, length,
                                        hash);
  if (interned != NULL) return interned;

  char* heapChars = ALLOCATE(char, length + 1);

새로운 LoxString으로 문자열을 복사할 때, 먼저 문자열 테이블에서 찾습니다. 찾으면 "복사"하는 대신 해당 문자열에 대한 참조를 반환합니다. 그렇지 않으면 아래로 내려가 새 문자열을 할당하고 문자열 테이블에 저장합니다.

문자열의 소유권을 가져오는 것은 약간 다릅니다.

  uint32_t hash = hashString(chars, length);

  ObjString* interned = tableFindString(&vm.strings, chars, length,
                                        hash);
  if (interned != NULL) {
    FREE_ARRAY(char, chars, length + 1);
    return interned;
  }

  return allocateString(chars, length, hash);

다시 한번, 먼저 문자열 테이블에서 문자열을 찾습니다. 찾으면, 반환하기 전에 전달된 문자열의 메모리를 해제합니다. 소유권이 이 함수로 전달되었고 더 이상 중복 문자열이 필요하지 않으므로, 우리가 그것을 해제해야 합니다.

작성해야 할 새로운 함수로 넘어가기 전에, include 하나가 더 있습니다.

#include "object.h"

#include "table.h"

#include "value.h"

테이블에서 문자열을 찾기 위해 일반적인 tableGet() 함수를 사용할 수 없습니다. 왜냐하면 그 함수는 findEntry()를 호출하는데, 이는 우리가 지금 해결하려는 중복 문자열 문제를 정확히 가지고 있기 때문입니다. 대신, 이 새로운 함수를 사용합니다:

void tableAddAll(Table* from, Table* to);

ObjString* tableFindString(Table* table, const char* chars,
                           int length, uint32_t hash);

#endif

구현은 다음과 같습니다:

ObjString* tableFindString(Table* table, const char* chars,
                           int length, uint32_t hash) {
  if (table->count == 0) return NULL;

  uint32_t index = hash % table->capacity;
  for (;;) {
    Entry* entry = &table->entries[index];
    if (entry->key == NULL) {
      // Stop if we find an empty non-tombstone entry.
      if (IS_NIL(entry->value)) return NULL;
    } else if (entry->key->length == length &&
        entry->key->hash == hash &&
        memcmp(entry->key->chars, chars, length) == 0) {
      // We found it.
      return entry->key;
    }

    index = (index + 1) % table->capacity;
  }
}

findEntry()를 복사해서 붙여넣은 것 같습니다. 많은 중복이 있지만, 몇 가지 중요한 차이점이 있습니다. 첫째, 찾으려는 키의 원시 문자 배열을 ObjString 대신 전달합니다. 이 함수를 호출할 시점에는 아직 ObjString을 생성하지 않았기 때문입니다.

둘째, 키를 찾았는지 확인할 때, 실제 문자열을 확인합니다. 먼저 길이와 해시가 일치하는지 확인합니다. 이들은 빠르게 확인할 수 있으며 같지 않다면 문자열은 확실히 동일하지 않습니다.

해시 충돌이 있다면, 실제 문자별 문자열 비교를 수행합니다. 이것은 VM에서 문자열의 텍스트 동등성을 실제로 테스트하는 유일한 곳입니다. 여기서 문자열 중복 제거를 위해 이 작업을 수행하며, 그 후 VM의 나머지 부분은 메모리의 다른 주소에 있는 두 문자열은 내용이 달라야 한다는 것을 당연하게 받아들일 수 있습니다.

사실, 이제 모든 문자열을 인터닝했으므로 바이트코드 인터프리터에서 이를 활용할 수 있습니다. 사용자가 두 객체(문자열인 경우)에 ==를 수행할 때, 더 이상 문자를 테스트할 필요가 없습니다.

    case VAL_NUMBER: return AS_NUMBER(a) == AS_NUMBER(b);

    case VAL_OBJ:    return AS_OBJ(a) == AS_OBJ(b);

    default:         return false; // Unreachable.

문자열을 인터닝하기 위해 문자열 생성 시 약간의 오버헤드를 추가했습니다. 하지만 그 대가로 런타임에 문자열의 동등성 연산이 훨씬 빨라졌습니다. 이것으로 변수, 인스턴스 또는 다른 키-값 쌍을 추적하는 데 사용할 수 있는 완전한 기능을 갖춘 해시 테이블을 완성했습니다.

또한 문자열의 동등성을 테스트하는 속도도 빨라졌습니다. 이는 사용자가 문자열에 ==를 사용할 때 좋습니다. 하지만 Lox와 같은 동적 타입 언어에서는 메서드 호출과 인스턴스 필드가 런타임에 이름으로 조회되기 때문에 훨씬 더 중요합니다. 문자열의 동등성 테스트가 느리다면, 메서드를 이름으로 조회하는 것도 느리다는 의미입니다. 그리고 객체 지향 언어에서 그것이 느리다면, 모든 것이 느려집니다.