08. Hash Tables (Part 2 - Dynamic Hash)

서울대학교 데이터사이언스대학원 정형수 교수님의 "데이터사이언스 응용을 위한 빅데이터 및 지식 관리 시스템" 강의를 필기한 내용입니다.

• 목차

Dynamic hashing scheme §

• Static hash 의 경우에는 key count 를 이미 알고 있어야 한다.
• Dynamic hash 는 근데 이것을 알 수 없기 때문에 적절한 시점에 (on-demand) resize 해야 한다.
  • 왜냐면 그렇지 않으면 collision rate 가 높아지기 때문.
• 따라서 dynamic hash 에서는 어떤 mechanism 으로 resize 할지가 가장 중요한 주제이다.
  • Resize 를 했을 때 그에 맞는 mapping rule (hash func) 를 사용하는 것이 가장 좋겠지만 현실적으로는 힘들다
  • 그냥 바꿔버리면 모든 entry 의 배치가 바뀌기 때문에 이들을 전부 re-insert 해야 하기 때문.
    • 앞선 static hash 는 JOIN 에 많이 사용하고, 따라서 in-memory 상황을 가정하고 있기 떄문에 rehash 의 비용이 그렇게 크지 않을 수 있지만
    • Index 는 storage 에 있기 때문에 rehash 는 아주 많은 io 를 수반한다.
  • 따라서 hash func 는 그대로 두고 마지막의 modulus 만 조정하는 방식으로 resize 를 한다.

Chained hash §

• 이놈이 가장 기본적으로 생각할 수 있는 hash 방법이라고 생각하면 된다: collision 된 애들을 linked list 로 관리하자는 것
• 다만 bucket 이라는 단위로 linked list 를 구성하는데, 하나의 bucket 은 하나의 page 에 저장되는 array 라고 생각하면 된다.
• 즉, Chained hash 에서는 collision 된 놈을 bucket 에 담다가 bucket 의 공간이 부족해지면 새로운 bucket 을 만들어 연결해주게 된다.
  • bucket 안을 뒤지는 것은 in-memory 여서 아주 느리지는 않다고 한다.
    • 마치 linear probing 에서 in-cache linear search 에 의해 생각보다 성능이 나쁘지 않다는 것과 일맥상통하는 것.
• 근데 당연히 이 방법은 bucket 수가 적으면 상관없지만 연결되는 bucket 이 많아지면 그만큼 탐색에 io 가 심해진다.

Extendible hash §

• 이놈이 사실상 dynamic hash 에서는 SOTA 나 다름없는데
• 이름이 시사하는 것 처럼 이것은 적절한 시점마다 hash table 을 두 배씩 확장 (Extend) 하는 방법을 사용한다.
• 잗동 원리는
  • 일단, 가장 먼저의 entry point hash table 인 global table 이 있고, 이곳의 entry 는 bucket 을 가리키고 있는 구조이다.
  • 이때 global bitwidth 이 $n$ 이라면, global table size 는 $2^n$ 가 된다.
  • 그리고 key 를 hash 한 digest 에서 상위 global bitwidth ($n$) 개의 bit 를 보고 global table entry 로 들어가 연결된 bucket 으로 가게 되는 흐름이다.
  • 이 bucket 에도 local bitwidth ($l$) 가 있는데, 이 값은 해당 bucket 내에 있는 애들이 공통된 $l$ 개의 상위 digest bit 을 가진다는 것을 뜻한다.
    • 그리고 만약에 $n>l$ 이라면, local 에서는 상위 bit 를 적게 본다는 의미이기 때문에 여러개의 global table entry 가 이 bucket 을 가리키게 되고
    • 만약 $n=l$ 이라면, global bucket entry 하나만이 bucket 을 가리키고 있고, 이는 이놈이 바로 이전에 쪼개어졌다는 의미이다.
  • 만약 쪼개어진다면, 해당 bucket 이 두개가 되고 global table 의 크기도 두배가 되며 쪼개진 애를 가리키는 pointer 가 entry 에 각각 들어가게 된다.
• 감이 잘 안오면 다음의 예시로 보자.

• 일단 이게 resize 전의 모습이다.
• 보면 global table 의 bitwidth 가 2이기 때문에, 이놈은 4개의 entry 를 갖고 있고, global table 의 entry 로 접근하는 것은 digest 의 상위 2개의 bit 로 수행한다.
  • 0 으로 시작하는 애들이 모여있는 것이 첫번째 local bucket 이다.
    • 따라서 global table 에서도 0으로 시작하는 (0, 1) entry 들은 이 bucket 으로 연결되어 있고
    • 이 local bucket 에 명시된 bitwidth 도 1인 것을 볼 수 있다.
  • 그리고 10, 11 으로 시작하는 애들은 각각의 bucket 에 연결되어 있다.
    • 따라서 이 bucket 들의 경우에는 bitwidth 가 2로 적혀 있는 것을 볼 수 있다.
• 근데 C 가 INSERT 되면 두번째 bucket 에 대해 자리가 없기 떄문에 이놈을 reshuffling 해야 한다.
• 이때, resize 가 일어난다.

• 보면 이제는 global table 의 bitwidth 가 3이 되었고, digest 의 상위 3개의 bit 로 이 global table 의 entry 에 접근하게끔 바뀐 것을 볼 수 있다.
• 우선 안쪼개진 애들부터 보면
  • 0 으로 시작하는애들은 여전히 안쪼개어지고 남아 있다.
    • 따라서 global table 에서도 제일 위 bucket 을 가리키는 entry 가 2개에서 4개로 바뀐다.
  • 그리고 11 로 시작하는 애들도 안쪼개진다.
    • 그래서 이놈에 대한 bucket 을 가리키는 global table entry 가 1개에서 2개가 된다.
• 여기서 쪼개진 놈은 저 10 으로 시작하는 애들이다.
  • 이때는 상위 3bit 를 보게 되고, 따라서 100 에 대한 entry 와 101 에 대한 entry 가 별도의 bucket 에 연결되어 있는 것을 볼 수 있다.
  • 그리고 원래 10 에 있던 애들은 이 두개의 bucket 으로 나눠 들어간다.
  • C 도 101 entry 의 bucket 에 얌전히 들어가게 된 것을 볼 수 있다.

Hash function §

• Hash function 의 관점에서 보면, 이것을 다음과 같이 해석할 수 있다:
• Hash table 이 두배가 되었을 때 여기에의 배치를 결정하는 hash func 는 어떻게 바꾸는게 좋을까?
  • 일단 hash func 를 바꾼다는 것은 data distribution 이 달라진다는 것이기 때문에 hash func 를 바꾸면 어쩔 수 없이 reshuffling 이 수반된다.
    • 여기서 reshuffling 은 바뀐 hash func 에 맞게 데이터 배치를 다 바꾸는 것으로, 데이터를 re-insert 하는 식으로 진행된다.
  • 근데 전부에 대해 reshuffling 하지 말고, collision 이 일어난 곳에 대해서만 reshuffling 이 발생하게 해보자.
  • 우선 hash func 는 F(key) % (t_size) 의 형태를 띄고 있다.
    • F() 가 실질적으로 key 를 uniform distribution 하는 부분이고,
    • Modulus (%) 연산을 통해 table size 에 딱 맞도록 한다.
  • 근데 F() 를 바꾸면 어쩔 수 없이 전체 key 에 대한 distribution 이 바뀌어 전체를 reshuffling 해야 된다. 따라서 이 부분은 건들지 못한다.
  • 따라서 resize 마다 저 modulus 를 조정해서 collision 이 발생한 부분만 reshuffling 하자는 것이 extendible hash 의 아이디어이다.

Cons §

• 단점은 global table 의 크기가 exponential 하게 증가한다는 것이다.

Linear hash §

• 이 상황을 해결하기 위해 등장한 것이 linear hash
  • chained 에서는 global side 의 크기를 고정하고 bucket side 에서의 linked list 구조를 가져갔는데 이 때문에 computation 이 너무 오래걸렸다면
  • extendible 에서는 global side 의 사이즈를 바꾸고 bucket side 를 하나씩만 유지했더니 global table 이 너무나 커졌다
  • 그래서 이 둘 간의 타협점을 찾은 것이 linear hash 이다.
• 생각해 보면 doubling 에서 필요한 것은 table 에서의 entry 하나이다.
• 근데 이 entry 하나를 위해서 table 전체를 두배씩 늘리고 있었던 것.
• 따라서 바로 doubling 하지 말고 table entry 를 하나씩 늘려가는 선택을 하는게 linear hashing 의 아이디어이다.
• 근데 table entry 를 하나 늘렸을 때 여기에 무조건 overflow 된 애들이 담기는 것은 아니다.
  • 왜냐면 overflow 는 어느 bucket 에서건 발생할 수 있는데, 추가된 table entry 의 bucket 은 modulo 연산을 했을 때의 연산값이 해당 index 인 애들만 들어가기 때문.
  • 즉, 무조건 overflow 난 bucket 이 reshuffling 되는 것이 아니고 이 추가된 table entry 와 연관된 bucket 이 reshuffling 된다.
  • 이게 바로 아래 설명할 Split pointer 다.

Split pointer, Splitting §

• 일단 여기에서는 hash table entry 를 가리키는 split pointer 가 있다.
• Overflow 시에는 이놈이 가리키는 bucket 이 split 되며 entry 가 하나 추가되고 split pointer 가 한칸 내려간다.
  • Hash func 의 modulo 가 $n$ 일때
  • Split 될 때는 split pointer 가 가리키는 곳의 bucket 에서 $X\mathrm{mod}2n$ 가 새로 생긴 entry 의 index 가 되는 애들은 그쪽으로 보내는 식으로 진행된다.
• 주의할 것은 overflow 가 난 bucket 이 split 되는 것이 아니라 이 split pointer 가 가리키는 놈이 split 된다는 것이다.
• 그리고 이 split pointer 는 무작위로 결정되는 것이 아니다.
  • 현재 hash table 사이즈가 $s$ 이고, hash func modulo 가 $n$ ($n$ 은 2의 제곱승) 일 때,
  • Split pointer 는 $s\mathrm{mod}n$ 를 가리키게 된다.
  • 왜냐면
    • 만약 split pointer 가 hash table 에서 $i$ index 를 가리키고 있을 때, 여기에 들어있는 놈은 모두 $X\mathrm{mod}n=i$ 인 $X$ 다.
    • 근데 이게 split 되면 새로 생긴 entry 의 index 는 $s$ 가 되는데 (당연히 size 가 $s+1$ 이 됐으니까 마지막 index 는 $s$),
    • 이 $s$ 에 접근할 때는 $2n$ 으로 modular 를 해서 접근한다.
    • 따라서 원래 $i$ 에 있던 애들 ($X$) 이 $s$ 로 옮겨가므로 $X$ 는 $X\mathrm{mod}n=i$ 와 $X\mathrm{mod}2n=s$ 를 만족해야 한다.
    • 결국에는 $i=s\mathrm{mod}n$ 이 된다.
• 예시를 보자.

• 위 그림에서 보면 index 4 가 추가되기 위해서는 split pointer 는 0 (기존 table size 4 에 modulo 4 니까 $4\mathrm{mod}4=0$) 가 되어야 하고, 실제로 그렇게 가리키고 있는 것을 볼 수 있다.
• 여기서 17 를 insert 했을 때 overflow 가 난 상황이고, 따라서 저 index 4 가 추가되며 index 0 에 있던 bucket 이 split 된 결과가 위의 그림이다.

Finding, Deleting §

• 원소를 찾을 때는 우선 $n$ 으로 modular 를 해서 bucket 을 뒤지고, 만약에 거기 없으면 split 되어 옮겨졌다는 소리이기 때문에 $2n$ 으로 modular 를 해서 bucket 을 뒤지는 식이다.
  • 가령 위의 예시에서 20 을 찾으려면 일단 index 0 ($20\mathrm{mod}4=0$) 에 방문했다가, 거기 없으니까
  • Index 4 ($20\mathrm{mod}8=4$) 에 방문해서 찾을 수 있다.
• 원소를 삭제할 때는 그냥 bucket 에서 지워주면 되는데,
  • 하필이면 그놈이 table 의 마지막 entry 의 bucket 에 있던 마지막 원소여서 해당 bucket 이 비게 된다면, table entry 를 삭제하고 split pointer 를 하나 말아 올린다.

Discussion §

• 즉, split pointer 가 지나가기 전까지는 split 되지 않기 때문에 그 전까지는 chaining 된다고 할 수 있다.
  • 그래서 이것이 단점으로 작용해 disk based 에서는 잘 사용되지 않는다고 한다.