[실전 알고리즘] 0x15강 - 해시

 

 

안녕하세요, 이번 강의에서는 해시를 배워보겠습니다. 0x07강에서 덱을 배운 이후로 여러 알고리즘을 다루다가 되게 오랜만에 자료구조를 다시 배우는건데, 이번 강의로 시작해서 해시, 이진 검색 트리, 힙으로 이어지는 이 3개의 자료구조가 스택, 큐, 덱이랑 비교했을 때에는 난이도가 조금 있긴 합니다. 그래도 알아둘 필요가 있는 자료구조들이어서 같이 잘 익혀보도록 합시다.

 

이진 검색 트리랑 힙도 각 단원에서 언급을 할거긴 한데 목적에 따라 강의에서 소개할 내용을 좀 취사선택하셔도 됩니다. 만약 내가 지금 시간이 너무 촉박하다, 그냥 당장은 이론적인 지식 이런거 하나도 필요없고 그냥 코딩테스트만 신경쓸거다 하시면 충돌 회피랑 구현은 건너뛰고, 정의와 성질만 보고 STL 사용법을 익힌 후에 연습 문제만 살펴보고 끝내시면 됩니다. 길게 봤을 때에는 원리를 정확하게 아는 만큼 더 유용하게 쓸 수 있는건 맞는데 당장 코딩테스트가 급하면 대충만 익혀서 일단 코딩테스트를 넘기고 나중에 제대로 살펴봐도 괜찮습니다.

 

그렇게 시간에 쫓기는건 아니어서 제대로 배우실 분이라면 충돌 회피를 보는건 물론이고, 구현 파트도 꼼꼼하게 살펴보시면 좋겠습니다. 일단 삼성 SW 역량테스트 B형의 경우에는 STL을 허용하지 않아서 해시가 필요한 문제가 나오면 해시를 직접 짜야 합니다. 그래서 B형을 염두에 두시는 분들이라면 저 구현 파트를 꼭 숙달을 하셔야 합니다. 그게 아니라면 실제 문제를 풀 때에는 그냥 STL에 이미 구현되어 있는 해시를 쓰지 직접 해시를 짤 일이 없긴 합니다. 그렇긴 한데 직접 구현을 해보는게 해시 자료구조를 이해하는데에 도움이 될 수 있습니다.

 

해시에 대해 알아보기 전에 잠깐 치매 예방에 도움이 되는 기억력 퀴즈 한 번 풀고 가겠습니다. 위의 표는 각 사람이 가지고 있는 카드 번호를 의미합니다. 예를 들어서 카드 번호가 2621 6189 5198 5135인 사람은 Kim이란 뜻입니다. 여기서 카드 번호 목록을 임의로 섞어서 보여준 다음에 각각이 누구의 카드 번호인지 맞추는 문제를 낼 예정입니다.

 

사실 이런건 중고등학교때나 대학 교양 시험치기 직전에 달달 외우던 그런 감성인데 아무튼 한번 재미로 해봅시다. 잠시 멈추고 1분만 시간을 들여서 외워보고, 준비가 됐다면 다음으로 넘어가겠습니다. 대신 넘어간 이후에는 다시 돌려서 보면 안됩니다.

 

여기 이렇게 순서를 뒤섞어놨는데 매칭을 한 번 해봅시다. 사실 저는 단기 기억력이 별로 좋지 않아서 이런거 진짜 못합니다. 그래도 뭐 재미로 하는거니까 한번 매칭을 해보시고 다음 슬라이드에서 정답을 공개하겠습니다.

 

정답을 공개합니다. 몇개나 맞추셨나요? 다 맞추셨다면 박수 짝짝짝짝,,,

 

왜 갑자기 해시 자료구조 설명을 하다가 이런걸 물어보냐면, 지금 여기서 한게 해시 자료구조랑 아주 큰 관련이 있습니다. 한번 생각을 해봅시다. 이거 외우실 때 어떻게 외우셨나요? 카드 번호랑 이름을 매칭 시키려고 16자리를 다 기억하려고 한 사람은 없다고 봅니다. 마치 수헬리베붕탄질산이나 태정태세문단세처럼 전체를 외우려고 하는 것 보다는 그냥 일부만 가지고 있어도 이름이랑 매칭시키는데 아무런 문제가 없습니다. 맨 뒤의 숫자 1개로만 다 구분이 되면 사실 제일 좋았겠지만 지금 5가 2번 등장하기 때문에 그건 아쉽게 됐고, 대신 카드 번호의 뒷 4자리만 외운다치면 16자리를 다 외우는 것 보다야 그게 훨씬 낫습니다. 그래서 아마 여러분들도 앞 2글자나 뒤 2글자, 아니면 앞 4글자나 뒤 4글자 이렇게 일부의 정보만 기억을 했다가 매칭을 하려고 했을 것 같습니다. 지금 이게 해시 자료구조의 근본적인 원리입니다.

 

해시 자료구조는 키에 대응되는 값을 저장하는 자료구조입니다. 앞에서 우리가 본 예시에서는 카드 번호가 키고 사람의 이름이 값입니다. 우리는 여기서 새로운 카드 번호와 이름 쌍을 넣는다거나, 특정 카드 번호가 누구의 것인지를 찾는다거나 하는 일을 하고 싶습니다.

 

만약 가장 쉬운 방법으로 구현을 해본다고 치면, 그냥 배열에 모든 데이터를 다 넣어둔 다음 탐색을 하는 방법을 떠올릴 수 있습니다. 이렇게 하면 삽입은 제일 뒤에 추가하면 되니 O(1)일테고, 다만 특정 데이터를 지우는건 O(N)이고 또 특정 카드 번호가 누구의 것인지를 찾는 것도 배열의 원소들을 하나씩 살펴봐야 하니 O(N)입니다.

 

그런데 해시 자료구조에서는 insert, erase, find, update 등의 모든 연산이 전부 O(1)입니다. 보통 자료구조에서는 배열처럼 인덱스를 가지고 특정 원소를 O(1)에 찾을 수 있지만 중간에서 삽입/삭제가 일어날 경우 O(N), 혹은 연결 리스트처럼 삽입/삭제가 O(1)이지만 탐색이 O(N)이라던가 하는 식으로 특정 연산은 빠른 반면 특정 연산은 느린 것과 같은 상황이 나오기 마련인데 해시에서는 모든게 O(1)입니다. 과연 이게 어떻게 가능한걸까요?

 

사실 우리가 만약 공간의 크기가 무한한 컴퓨터를 가지고 있다면 배열을 이용해서 앞에서 예로 든 카드 번호와 이름의 매칭을 효율적으로 만들 수 있습니다. 0x03강 - 배열 단원에서 잘 써먹었던 아이디어인데, 각 카드 번호를 배열의 인덱스로 사용하는 테이블을 만들면 됩니다. 근데 문제는 카드 번호의 종류가 총 10¹⁶개로 좀 말도 안되게 많아서, 40PB의 용량을 필요로 합니다. 1TB 외장하드를 4만개 준비해야 다 담을 수 있습니다. 이건 현실적으로 불가능합니다.

 

그런데 비록 카드 번호의 종류가 총 10¹⁶개이긴 한데, 우리는 그 중에서 아주 일부의 카드 번호만 저장하려고 합니다. 그러면 우리가 마치 앞에서 기억력 퀴즈를 볼 때 굳이 카드 번호 전체를 외우는 대신에 뒷 4자리만 기억했던 것과 같이, 16자리 전체를 어떻게 하지 말고 그냥 뒷 4자리만 인덱스로 활용을 하는게 훨씬 합리적입니다. 이렇게 만들고 나면 insert, erase, find 모두 주어진 카드 번호의 뒷 4자리를 인덱스로 생각해서 대응되는 배열의 값을 보고 처리를 해줄 수가 있기 때문에 전부 O(1)에 처리가 가능합니다.

 

해시 자료구조에서는 해시 함수라는게 쓰입니다. 해시 함수는 마치 카드 번호 16자리에서 뒷 4자리만 배열의 인덱스로 쓴 것과 같이, 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수입니다. 비록 카드 번호의 예시에서는 데이터가 16자리로 정해져 있었지만 데이터가 16자리보다 더 길더라도 똑같이 뒷 4자리만 취하면 되니 임의 길이의 데이터를 고정된 길이의 데이터로 만든다는 정의가 크게 어색하지가 않죠.

 

이 해시 함수만 알고 나면 해시 자료구조를 이해하기 위한 모든 준비가 다 끝난건데, 해시 자료구조는 키에 대응하는 값을 저장하는 자료구조이니 키를 적당히 배열의 인덱스로 보내는 해시 함수를 하나 둬서 이렇게 테이블로 관리를 하는게 해시 자료구조입니다. 이 그림을 보면 왜 insert, erase, find 등과 같은 연산들이 전부 O(1)인지 이해할 수 있을 것 같습니다. 참고로 이러한 테이블을 해시 테이블이라고 합니다.

 

여기까지만 보면 해시는 그냥 키를 해시 함수에 넣어서 적당한 범위의 정수로 바꾸고 그걸 배열의 인덱스로 이용해 해시 테이블에서 값을 잘 처리해주면 끝입니다. 그렇게 어려울게 없어보이는데, 사실 이 충돌이라고 하는게 가장 큰 애로사항이고 이걸 잘 처리해주는게 해시의 성능에 가장 큰 영향을 줍니다. 과연 이 충돌이 뭔지 같이 살펴보겠습니다. 앞이랑 똑같이 카드 번호를 키로, 이름을 값으로 두겠습니다. 이 상황에서 카드 번호 0000 0000 0000 5135, 이름 Kim을 삽입하면 테이블의 5135번째 인덱스의 값을 Kim으로 나타내면 됩니다.

 

그런데 이 다음으로 카드 번호 9999 9999 9999 5135가 누구의 카드인지 묻는 질문이 들어왔다고 해보겠습니다. 그러면 뒷 4자리가 5135이니까 테이블의 5135번째 인덱스의 값을 보게 될거고, 거기에 Kim이라고 적혀있으니까 Kim이라고 답변을 합니다. 이 테이블을 보면 저기 적혀있는 Kim이 0000 0000 0000 5135에 대응되는 Kim인지, 9999 9999 9999 5135에 대응되는 Kim인지 알 방법이 없습니다.

 

즉 서로 다른 키가 같은 해시 값을 가지게 될 경우 지금처럼 동작이 이상하게 되어버립니다. 이러한 일을 충돌이라고 하고, 해시 함수를 적절하게 잘 잡아서 충돌이 발생하지 않게 할 수 없냐는 의문을 가질 수 있지만 해시 함수의 목적 자체가 원래 함수의 입력으로 주어지는 정의역의 공간이 너무 커서 이걸 바로 배열의 인덱스로 활용할 수는 없으니 범위를 줄이고자 하는데에 있습니다. 이를테면 원래 카드 번호의 종류는 10¹⁶개이지만 뒷 4자리만 활용해서 10⁴개로 줄인 것 처럼 말입니다. 그렇기 떄문에 충돌이 발생하는 것 자체는 달리 막을 방법이 없습니다. 하지만 똑똑한 사람들이 충돌이 발생했을 때의 회피 방안에 대해 많은 연구를 했습니다. 크게 Chaining과 Open Addressing으로 나뉘는데 Chaining을 먼저 살펴보겠습니다.

 

Chaining에서는 각 인덱스마다 연결 리스트를 하나씩 둡니다. 연결 리스트가 아니라 C++ vector같은 동적 배열을 써도 상관없습니다. 그리고 삽입이 발생하면 해당하는 인덱스의 연결 리스트에 값을 추가합니다.

 

이러면 충돌을 겁낼 필요가 없는데, 다음으로 (9999 9999 9999 5135, Choi)가 들어오면 연결 리스트에 추가를 해주면 됩니다.

 

Erase, find, update에 대해서도 그냥 똑같은 원리를 적용할 수 있습니다. 셋 다 굉장히 당연하게 방법이 감이 오긴 할텐데 그래도 erase만 한 번 보여드리면, 먼저 카드 번호 뒷 4자리를 가지고 인덱스 5135를 찾아갑니다. 해당 연결 리스트의 첫 번째 원소인 9999 9999 9999 5135를 확인해보면, 지우고 싶은 카드 번호랑 다르니까 다음껄로 이동합니다.

 

이동을 해보면 카드 번호가 일치합니다.

 

그렇기 때문에 해당 원소를 지우면 끝입니다. find, update는 그냥 마찬가지로 인덱스를 찾아서 거기 있는 원소들을 싹 순회하면 될테니 굳이 설명은 더 안하겠습니다. 이렇게 각 인덱스마다 연결 리스트를 둬서 충돌 회피를 하는 방법을 Chaining이라고 하고, 실제로 STL에 있는 해시 자료구조는 Chaining을 이용하고 있습니다. 그리고 또 한 가지 재밌는 점은 만약 운이 안좋아서 해시 값이 다 같았다고 해보겠습니다. 그러면 그냥 연결 리스트 1개에서 insert erase find update를 다 하는 상황이 됩니다. insert는 그냥 header에 매번 붙인다고 쳐서 O(1)이라고 해도 나머지 erase, find, update는 모든 원소를 다 순회해야 하니까 전부 O(N)이 됩니다. 그렇기 때문에 해시 자료구조는 이상적인 상황에서는 O(1)이지만 충돌이 빈번할수록 성능이 저하되고, 모든 키의 해시 값이 같은 최악의 상황에서는 O(N)이 됩니다. 이건 후술한 Open Addressing에서도 마찬가지입니다. 그렇기 때문에 해시에서는 각 키의 해시 값이 최대한 균등하게 퍼져야 성능이 좋아지고, 그러기 위해서는 주어진 데이터에 대한 좋은 해시 함수를 정해야 합니다.

 

두 번째 충돌 회피 방법은 Open addressing입니다. 각 인덱스마다 연결 리스트를 뒀던 Chaining과 다르게 Open addressing은 그냥 각 인덱스에 바로 (키, 값) 쌍을 씁니다. 그럼 과연 어떻게 충돌 회피를 하겠다는건지 같이 확인해보겠습니다. 먼저 (0000 0000 0000 3333, Kim)을 삽입하면 그냥 3333번지에 바로 내용을 채웁니다.

 

그 다음으로 (6278 5651 9104 3333, Lee)를 삽입할 때가 중요한데, 3333번지에 넣고 싶지만 해당 칸에는 비어있지가 않습니다.

 

그러면 그 다음 칸으로 가서 내용을 씁니다. 삽입하는 예시를 조금 더 진행해보겠습니다.

 

(7298 1127 6004 3334, Bae)를 삽입한다면 먼저 3334번지를 확인하는데 해당 칸은 비어있지가 않으니 다음 칸으로 넘어가서 3335번지에 내용을 씁니다.

 

다음으로 (3492 0658 8348 3333, Yang)을 삽입한다면 3333번지, 3334번지, 3335번지가 다 비어있지 않기 때문에 3336번지에 내용을 씁니다.

 

Insert 다음으로 find를 생각해보겠습니다. 3492 0658 8348 3333이 누구의 카드인지 찾고싶다고 하면 일단 3333번지의 값을 븝니다. 그런데 거기에 적힌 카드 번호는 0000 0000 0000 3333이라서 저희가 찾고자하는 카드와는 다릅니다. 그럼 여기서 탐색을 끝내야할까요?

 

그렇지는 않겠죠? 밀려서 더 오른쪽 칸에 써져있을 수도 있잖아요? 그렇기 때문에 다음 칸인 3334번지를 봅니다. 하지만 여기도 번호가 일치하지 않고

 

그 다음 칸인 3335번지도 일치하지 않습니다.

 

그런데 3336번지에서는 카드 번호가 일치하기 때문에 해당 카드 번호가 Yang의 카드임을 알 수 있습니다.

 

존재하지 않는 카드 번호를 찾는 상황도 한 번 살펴보겠습니다. 일단 3335번지를 보면 여기는 카드 번호가 다르고

 

그 다음 칸도 번호가 다르고

 

그 다음 칸을 보니 여기는 비어있습니다. 이렇게 빈 곳에 도달하면 찾고 싶은 5555 6666 7777 3335 번호가 저장이 안되어있다는걸 확신할 수 있습니다.

 

다음으로 Erase 명령을 생각해보겠습니다. 번호가 주어졌을 때 해당 번호를 지우는 상황을 생각해보면 일단 find에서와 같이 해당 번호를 찾아나서야 합니다. find랑 똑같이 하면 되니까 위치는 바로 찾았다고 해보겠습니다.

 

이 다음에 제거를 한다 치면 그냥 자연스럽게 안의 내용을 비워버리면 될 것 같습니다. 그런데 사실은 이렇게 하면 뭔가 심각한 일이 발생할 수 있다는게 감이 오면 좀 기쁠 것 같은데, find에서 하던 방식을 떠올려보겠습니다.

 

구체적으로, 이렇게 제거를 한 후에 7298 1127 6004 3334를 찾고자하면 어떻게 될까요? 일단 3334번지를 가보는데 해당 칸이 비어있으니까 분명 해당 카드 번호는 3335번지에 있음에도 불구하고, 그냥 7298 1127 6004 3334가 없다고 판단하게 됩니다.

 

그렇기 때문에 이 Open addressing 방식에서는 삭제를 할 때 그냥 값을 날려서 빈 칸을 만드는게 아니라, 해당 칸에 쓰레기 값을 두던가 아니면 별도의 배열을 두던가 해서 해당 칸이 빈 칸이 아니라 원래 값이 있었지만 제거된 상태임을 명시해줄 필요가 있습니다. 그리고 find, erase 등에서 탐색을 할 때에는 쓰레기 값이 들어있는 칸을 만났을 경우에는 빈 칸과 다르게 계속 탐색을 이어나가야 합니다. 또 Insert를 할 때에는 빈 공간을 찾아서 계속 다음 칸으로 이동을 하는데, 이 때 빈 칸이 아니라 dummy가 들어있는 칸을 마주했을 때에도 거기에 바로 삽입을 할 수 있습니다. 이 두 가지 방법 모두 실제 어떻게 구현을 하는지는 구현 챕터에서 다루겠습니다.

 

Open addressing 방식에서 마지막으로 할 얘기는 Probing입니다. 다들 프로브 아시나요? 제가 토스 유저여서 혼자서 왕국을 건설하는 프로브를 좋아하는데, 아무튼 프로브가 스타2에서는 탐사정으로 번역됐습니다. 그 프로브가 여기 Probing이랑 일맥상통합니다. 말 그대로 탐사를 한다는 뜻인데, 앞에서 충돌이 발생하면 오른쪽으로 한 칸 이동을 해서 그 칸을 확인했습니다. 이러한 방식을 Linear probing이라고 합니다.

 

Linear probing은 일단 구현이 간단하기도 하고, 또 Cache hit rate가 높습니다. 계속 인접한 영역의 배열 칸을 확인하니까 그렇습니다. 하지만 단점으로는 Clustering을 꼽을 수가 있습니다. Clustering이 뭔가 하면 보통 군집이라고 번역을 하던데, 지금 그림에서 주황색 영역이 뭉쳐 있습니다. 이렇게 데이터가 차있는 영역이 뭉쳐있는게 군집입니다. 그리고 해시 값이 저 주황색 영역에 걸리는 어떤 데이터가 추가로 삽입이 된다면 그림에 표시한 빨간색 영역에 값이 써지게 됩니다. 그러면 Cluster의 크기가 1 늘어나는 상황이고 이 Cluster가 커지면 커질수록 인덱스가 이 군집에 걸렸을 때 빈 칸을 찾을 때 까지 이동해야 하는 횟수가 늘어나서 성능을 저하시키게 됩니다. 그래서 Linear probing에서는 이 Clustering의 문제가 성능에 안 좋은 영향을 줍니다.

 

두 번째 방법은 Quadratic probing입니다. Quadratic probing은 충돌이 발생하면 오른쪽으로 1, 3, 5, ... 칸 이동하는 방법인데 왜 Quadratic이냐면 Quadratic이 제곱을 하는 그런 의미입니다. 현 위치 기준으로는 1, 3, 5, ... 칸 이동하는건데 처음 위치를 기준으로 생각해보면 1, 4, 9, ... 칸 이동하는거고 이 값 각각이 1의 제곱, 2의 제곱, 3의 제곱입니다. 그래서 이걸 Quadratic probing이라고 합니다.

 

Quadratic probing의 장점을 먼저 보면 Cache hit rate가 Linear probing 보다는 조금 안좋긴 하지만 그래도 그렇게 막 나쁘지는 않습니다. 그리고 Clustering도 어느 정도는 회피를 할 수 있습니다. 이게 어떤 의미냐면, 아까는 시작점이 아무 주황색 칸이든 걸려버리면 바로 Cluster의 크기가 1 증가했습니다. 그런데 이번에는 예를 들어서 중간의 어딘가에서 해시 충돌이 발생했다면 여기서는 시작점이 다르니까 점프하는 칸의 수가 달라서 Cluster에 포함되지 않습니다. 그래서 Clustering을 어느 정도는 회피할 수 있습니다. 다만 단점을 본다면, 물론 Linear probing에 비해서는 좀 개선이 됐지만 어쨌거나 시작점이 같다면, 즉 해시 값이 동일하다면 계속 똑같은 경로를 따라가기 때문에 여전히 Clustering이 발생합니다.

 

마지막 방법은 Double hashing입니다. Double hasing은 해시 함수를 하나 더 둬서 충돌이 발생했을 때 몇 칸 점프할지를 이 새로운 해시 함수의 값으로 계산하는 방식입니다. 카드 번호 예시에서 계속 뒷 4자리를 해시 함수로 써서 인덱스를 정했는데, 예를 들어 점프할 칸의 수는 앞 4자리로 정하는 방식입니다. 그래서 1234 2222 5555 5555는 1234칸씩 뛰고 3333 3000 3210 5555는 3333칸씩 뜁니다.

 

Double hashing의 장점으로 Clustering을 아주 효과적으로 회피할 수 있습니다. 1234 2222 5555 5555랑 3333 3000 3210 5555를 보면 뒷 4자리가 겹쳐서 충돌이 발생했지만 그 뒤로는 1234 2222 5555 5555는 1234칸씩 뛸거고 3333 3000 3210 5555는 3333칸씩 뛰어서 서로 같은 칸을 보는게 아니라 각자 갈 길을 가게 됩니다. 그렇지만 Cache hit rate가 극악으로 안 좋아지는게 단점입니다. 이렇게 Open addressing까지 설명이 다 끝났습니다.

 

이렇게 이론적으로 해시를 잘 알아보았지만 사실 엥간치 필요한건 다 있는 STL에 해시도 물론 구현이 이미 다 되어있습니다. 뒷쪽에서 실제로 해시를 구현해보긴 하겠지만 앞으로 문제를 풀 때 STL을 일부러 막아둔 아주 드문 경우를 빼면 직접 해시를 짤 일은 없습니다. 그냥 있는 STL을 가져다 쓰면 되니까 사용법을 익혀보겠습니다.

 

먼저 unordered_set은 이름에서 유추할 수 있듯 마치 집합과 같은 느낌의 STL입니다. 구체적으로 데이터를 unordered_set에 추가하고, 데이터가 unordered_set에 있는지 확인하고, 데이터를 unordered_set에서 지우고 이런 것들을 수행할 수 있습니다. 사실 레퍼런스를 보면 멤버함수들이 더 있긴한데 주로 쓰는 것만 소개를 드렸습니다. 이정도만 알아도 크게 사용에 문제는 없을거고 나중에 다른 사람들의 코드를 보다가 생소한 멤버 함수가 나오면 어떤 기능인가 직접 레퍼런스를 확인해보도록 합시다.

 

일단 vector나 list 같은 다른 STL처럼 unordered_set은 선언할 때 자료형도 같이 지정을 합니다. 지금은 int 자료형에 대한 unordered_set입니다. 먼저 insert는 말 그대로 삽입을 하는 함수입니다. 03번째 줄에서는 -10, 100 ,15를 삽입했습니다. 04번째 줄을 보면 이미 들어있는 -10을 다시 한 번 추가했습니다. 이러면 unordered_set은 중복을 허용하지 않기 때문에 그냥 아무 일도 생기지 않습니다. 다음으로 erase 함수는 인자로 값을 줄 경우 해당 값을 지웁니다. 만약 해당 값이 unordered_set 안에 들어있다면 지운 후 1을 반환하고, 그렇지 않다면 0을 반환합니다. iterator를 인자로 줄 수도 있는데 이건 설명을 생략하겠습니다. find 함수는 값을 찾아서 iterator를 반환하는 함수입니다. 그런데 만약 값이 없다면 s.end()를 반환합니다. 그렇기 때문에 07번째 줄의 코드와 같이 특정 값이 있는지 없는지를 판단할 때 저런식으로 코드를 작성할 수 있습니다. size 함수는 말 그대로 들어있는 값의 수이고, count 함수는 수가 몇 개 들어있는지 세는 함수입니다. 그런데 unordered_set은 중복을 허용하지 않는다고 했으니 사실 count 함수는 해당 값이 있을 경우 1, 없을 경우 0입니다. 마지막으로 range-based for loop를 이용해 값을 출력할 수 있습니다. 그리고 해시의 특성상 원소들이 크기 순서 혹은 삽입한 순서로 위치해있지 않습니다. 그래서 출력을 해보면 순서가 뒤죽박죽인데 이건 그냥 해시의 특성입니다. 0x03강 배열 단원에서도 언급했었지만 range-based for loop은 C++11부터 지원되긴 하는데 요즘은 C++11을 지원하지 않는 환경을 거의 찾아볼 수가 없어서 그냥 마음 편하게 저렇게 쓰시면 됩니다.

 

두 번째로는 unordered_multiset이 있습니다. multiset은 set이랑 거의 다 똑같은데 원소의 중복이 허용됩니다. 그래서 04번째 줄을 보면 알겠지만 이미 있는 원소를 또 insert 해도 multiset에 추가가 이루어집니다. multiset에서 정말 주의해야 하는게 erase입니다. 08번째 줄을 보시면 15를 erase할 때 하나만 지워지는게 아니라 모든 15가 다 지워지는걸 확인할 수 있습니다. 저도 16년인가 17년인가에 처음 이걸 배웠는데 당시 multiset에서 erase가 하나만 지우는줄 알고 맞왜틀을 한 적이 있습니다. 정말 까마득한 시절의 이야기입니다. 아무튼 erase를 하면 싹 다 지운다는걸 기억해주셔야 합니다. 아니면 여러분들도 옛날의 저처럼 맞왜틀을 하게 될 수 있습니다. 그러면 하나만 지우고 싶을 때에는 어떻게 코드를 써야하냐면 09번째 줄처럼 써야 합니다. 저렇게 쓰면 ms.find(-10)을 통해 -10이 들어있는 iterator를 erase의 인자로 넘겨줘서 하나만 딱 지웁니다. 또한 count 함수는 O(1)이 아닌 O(원소의 개수)만큼의 시간이 걸림에 유의하세요.

 

마지막은 unordered_map입니다. unordered_map은 저희가 카드 번호를 키로 사용해서 사람의 이름을 찾았듯, 키에 대응되는 값을 찾아주는 STL이고 보면 알겠지만 인터페이스를 되게 편하게 만들어놨습니다. 맨 처음 선언을 할 때 키의 자료형과 값의 자료형을 명시하고, find, erase랑 range-based for로 iteration 도는 것만 익히고 나면 그냥 마치 배열인데 인덱스가 0, 1, 2, 3, ... 이렇게 작은 범위 내의 정수로 제한되는게 아니라 string을 쓸 수도 있고, 아주 큰 정수나 음수도 담을 수 있는 느낌으로 쓸 수 있습니다. 코드는 한 번 살펴보시고, 07번째 줄을 보면 m["hi"] = -7; 이라고 했을 때 새로운 ("hi", -7)이 추가된게 아니라 기존에 있던 123이란 값을 덮어쓴 것에서 볼 수 있듯 지금은 중복 키가 허용이 안됩니다. 반면 unordered_multimap이라고 해서 중복 키를 허용하는 STL도 있습니다. 근데 저는 이 unordered_multimap을 유용하게 쓴 적이 진짜 단 한번도 없었어서 그냥 소개를 안드렸습니다. 아마 여러분들도 unordered_map은 많이 쓰더라도 unordered_multimap은 딱히 쓸 일이 없을 것으로 보입니다.

 

드디어 문제를 풀 시간입니다. 일단 BOJ 7785번: 회사에 있는 사람으로 시작해보겠습니다. 일단 이 문제를 해시를 안 쓰고 푸는 방법을 고민해보겠습니다. 지금까지 내용을 잘 따라왔는지 확인하는 차원에서 해시를 안 쓰고 어떻게 풀 수 있는지 잠깐 멈춰놓고 고민해보는 시간을 가져보겠습니다.

 

이 문제는 이분 탐색으로 해결이 가능한데, 일단 입력을 싹 다 받은 다음에 enter인 이름 리스트와 leave인 이름 리스트 각각을 정렬합니다. 이게 한 사람이 enter와 leave를 여러 번 번갈아 할 수 있어서 구현이 조금 까다로워지긴 하는데, 아무튼 우리는 정렬과 이분탐색을 이용하면 특정 사람에 대해 enter 횟수와 leave 횟수를 O(lg N)에 구할 수 있고, enter 횟수가 leave 횟수보다 많으면 그 사람은 아직 회사에 있음을 알 수 있습니다. 혹은 두 리스트를 합쳐서 정렬을 한 후에 enter는 +1, leave는 -1로 계산을 해서 처리를 할 수도 있겠습니다. 이건 이분탐색의 접근 방법이고 투 포인터도 가능합니다. 저도 사실 이분탐색이나 투 포인터로 이 문제를 풀어보지는 않았지만 생각했을 때 예외처리도 적당히 까다롭고 구현에서 실수할 수 있는 여지도 있어서 한번 구현을 해보시면 이분탐색과 투 포인터의 연습에 아주 큰 도움이 될 것으로 보입니다. 이건 여러분에게 맡기고, 저는 훨씬 더 간단한 해시를 이용해서 풀겠습니다. 그냥 unordered_set를 하나 정의하고 enter가 들어오면 insert, leave가 들어오면 erase를 하면 끝입니다. 답은 알아서 적절하게 sort해서 출력하면 됩니다. 그래서 방법 자체는 간단한데 아마 처음 unordered_set을 써보는거면 사용법이 안익숙해서 조금 애를 먹을 수는 있을 것 같습니다. 아무튼 제 코드를 같이 보겠습니다.

 

로직은 설명할게 딱히 없고, 마지막에 모아서 답 출력하는거를 19, 20, 21번째 줄을 보시면 좀 멋있게 했습니다. 마지막에 남아있는 이름들을 vector에 담을 때 iterator로 좀 깔끔하게 담았고 역순 정렬은 greater<string>() 이거를 sort의 3번째 인자로 넘겨서 처리했습니다.(코드)

 

두 번째로 unordered_map을 쓸 수 있는 문제를 풀겠습니다. BOJ 1620번: 나는야 포켓몬 마스터 이다솜 문제를 확인해보겠습니다. 일단 문제 설명이 길긴 한데 강의 보느라 지친 뇌를 달랜다는 생각으로 천천히 음미해보겠습니다. 결국 포켓몬 이름이 주어지면 번호를 답하고, 번호가 주어지면 이름을 답하는 문젠데 번호가 주어졌을 때 이름을 답하는건 그냥 배열을 쓰면 끝입니다. 포켓몬 이름이 주어졌을 때 번호를 답하는건 포켓몬 이름을 키로, 번호를 값으로 가지는 unordered_map을 만들어두면 해결이 가능합니다. 참고로 포켓몬 이름이 주어졌을 때 번호를 답하는건 unordered_map 대신 이분탐색으로도 해결이 가능하니 이분탐색 풀이를 고민해보시는 것도 추천드립니다. 다만 이번 단원이 해시 단원이기도 하고, 구현의 난이도도 unordered_map을 쓰는게 훨씬 낮기 때문에 저는 unordered_map만 써서 풀겠습니다. STL 사용법을 확인해가면서 한 번 직접 풀어보는걸 추천드립니다. 제 코드를 같이 확인해봅시다.

 

이 쪽도 딱히 설명할건 없어보입니다. 원래 to를 2로 쓰는게 진짜 안좋은 변수명이라고 어디선가에서 본 것 같은데 뭐 상관이 있나 싶습니다. 뜻만 통하면 되는거 아닐까요? 저는 마음껏 쓸테니 그 담배 피고 니들은 이런거 피지 마라 하는 것처럼 클린 코드를 지향하는 개발자라면 s2i, i2s 이런 변수명 쓰지 마시고 저처럼 나 혼자만 잘 알아보면 장땡 아니냐는 아주 나쁜 마인드를 가지고 있는 개발자라면 편하게 s2i, i2s를 씁시다. 아무튼 i2s는 번호를 키로, 이름을 값으로 둔 상황인데 이것도 unordered_map을 이용할 수 있지만 당연히 그냥 배열에서 인덱스로 가져오는 것 보다 unordered_map을 쓰는게 느릴테니 배열로 선언을 했습니다. 앞으로 여러분들도 굳이 unordered_map이 필요가 없고 그냥 키의 범위가 이를테면 0부터 몇백만 안쪽이어서 배열의 인덱스로 둬도 아무 문제가 없는 상황이면 unordered_map을 남발하는 대신 배열을 사용하는걸 추천드립니다. 그 뒤로는 그냥 입력 처리해서 i2s와 s2i를 채우고 쿼리가 들어오면 번호인지 이름인지 잘 구분해서 상황에 맞는 답을 출력하면 끝입니다. 이렇듯 뭔가 집합과 같은 식으로 원소를 추가하고 빼는 일이 빈번하거나, 문자열을 수에 대응시키는 것 처럼 키를 가지고 값을 알아내야 하는 일이 필요하다면 unordered_set, unordered_map을 활용할 수 있습니다. 물론 이것만 달랑 써서 풀리는 문제는 너무 쉬워서 잘 안나오긴 하겠지만 unordered_set, unordered_map이 풀이 중간에 필요하도록 문제를 만드는건 출제자의 입장에서 구현의 난이도를 적당히 올릴 수 있어서 자주 있을거라 unordered_set, unordered_map의 사용법은 충분히 익힐 필요가 있습니다.

 

이제 마지막 피날레는 구현으로 완성이 됩니다. 지금까지 배운 자료구조들, 뭐 연결 리스트, 스택, 큐, 덱 이런건 다 중간에 구현을 먼저 해봤는데 해시에서는 왜 제일 뒤로 뺐냐면 구현이 좀 어려워서 그렇습니다. 또 어차피 문제를 풀 때에는 STL을 계속 쓸거니까 구현을 굳이 안보고 넘어가도 되긴 하지만 구현을 해보면서 해시의 성질을 더 잘 이해할 수 있으니 일정이 너무 쫓기는게 아니라면 가능하면 구현을 보고 가면 좋겠습니다. 그런데 삼성 SW 역량테스트 B형을 치실 분들은 무조건 보셔야 합니다. 왜냐하면 거기서는 STL을 못 쓰기 때문에 이걸 직접 짜야 합니다.

 

Chaining이랑 Open addressing을 각각 구현해볼건데 둘 다 공통적으로 해시 테이블의 크기를 얼마로 할지 정해야 하고, 해시 함수도 정해야 합니다. 먼저 크기를 대체 얼마로 두는게 좋냐고 했을 때, 지금 우리는 일반적인 개발에서의 해시 자료구조를 구현하자는게 아니라 알고리즘 문제에서 써먹을 해시 자료구조를 구현하자는 상황입니다. 그러면 삽입의 최대 횟수를 알 수 있습니다. 뭐 예를 들어 전체 명령이 50만번이라고 하면 당연히 삽입이 최대 50만번 발생한다는걸 알 수 있습니다. 해시 테이블에서 원소의 개수 / 테이블의 크기를 load factor라고 하고, 삽입의 최대 횟수가 곧 해시 테이블에 들어있는 원소의 최대 개수를 의미합니다. load factor를 작게 유지하면 충돌이 덜 생겨서 각 연산이 거의 O(1)에 동작하겠지만, 반대로 cache hit rate가 줄어들고 메모리도 많이 차지한다는 단점이 있습니다. 반대로 load factor를 크게 유지하면 메모리는 적게 차지하지만 충돌이 많이 생겨서 성능에 악영향을 줄 수 있습니다.

 

Chaining과 Open addressing 각각에서 load factor를 얼마 이하로 두는게 좋냐 생각해볼 때. Chaining은 각 인덱스에 연결 리스트가 있는 방식이기 때문에 각 인덱스에 여러 원소가 있을 수 있습니다. 그렇기 때문에 충돌이 어느 정도는 발생하는걸 감수하더라도 공간의 효율성을 고려해서 load factor를 1 이하가 되게끔 합니다. 반면 Open addressing에서는 각 인덱스에 반드시 하나의 원소가 들어가야 하기 때문에 만약 load factor를 1 이하로 뒀다가는 해시 테이블이 거의 다 채워질쯤이 되어서는 빈 곳을 찾느라 삽입이 아주 느리게 이루어집니다. 그렇기 때문에 Open addressing에서는 load factor를 보통 0.75 이하 정도로 둡니다. 그렇기 때문에 Chaining에서는 테이블의 크기를 최대 삽입 횟수로, Open addressing에서는 최대 삽입 횟수 * 1.33 정도로 두면 되지만 실무 말고 저희가 문제를 푸는 상황에서는 사실 메모리가 굉장히 널널한 경우가 많기 때문에 저는 그냥 마음 편하게 테이블을 삽입의 최대 횟수의 한 2배 정도로 잡는걸 선호합니다. 극단적으로 테이블을 작게 잡아서 충돌이 너무 빈번하게 발생하게끔 하지 않는 한, 혹은 반대로 테이블의 크기를 5천만 이렇게 너무 크게 잡아서 cache hit rate를 극악으로 떨구는게 아닌 한 성능에 그렇게 큰 차이는 없으니까 2배에 너무 집착할 필요는 없고, 아무튼 테이블 크기는 적당히 잡아주면 됩니다. 그리고 테이블의 크기가 소수이면 좋은데 이건 해시 함수랑 관련이 있습니다. 그런데 사실 저희가 80만 주변의 소수, 아니면 100만 주변의 소수 뭐 이런걸 외우고 있지는 않습니다. 인터넷을 쓸 수 있다면 울프람 알파에서 prime near 1000000 이렇게 검색해서 소수를 얻을 수 있는데 만약 인터넷을 쓸 수 없는 환경이라면 검색도 불가능합니다. 이럴 때 소수 판별하는 알고리즘을 빠르게 짜서 소수를 얻어내는 방법도 있고 아니면 적당한 소수 하나를 그냥 기억하고 있는 것도 괜찮습니다. 이를테면 1000003이 소수입니다. 1000003은 그럭저럭 외우기 쉬워 보입니다. 그런데 소수를 쓰면 좋다는거지 소수를 꼭 써야한다는건 아닙니다. 그래서 그냥 소수를 신경쓰지 말고 테이블의 크기를 적당한 수로 잡아도 상관은 없습니다.

 

그 다음으로 해시 함수를 정해줘야 하는데, 테이블의 크기를 M이라고 하면 정수에 대한 해시 함수는 그냥 M으로 나눈 나머지로 정할 수 있습니다. 이렇게 하면 해시 함수의 결과가 0에서 M-1 사이의 값이 될테니 해시 테이블의 인덱스로 쓰기 딱 괜찮습니다. 그런데 왜 그냥 return x % M으로 안하고 저렇게 좀 괴상하게 썼냐면, x가 항상 0이상이라면 그냥 return x % M으로 써도 됩니다. 그런데 만약 해시에서 키에 음수가 들어올 수 있다면 x % M은 음수가 됩니다. 예를 들어서 -4 % 3은 C++에서 -1입니다. 이런 경우를 처리해주기 위해서 if문으로 x가 0보다 작은지 큰지에 따라 로직을 다르게 써도 되지만 저렇게 x % M에 M을 더하고 다시 M으로 나눠주는 방식으로 짜면 한 줄에 쓸 수 있습니다.

 

다음으로 문자열에 대한 해시 함수를 어떻게 만들지 생각해봐야 하는데, 우리는 어떤 형태든 상관없이 문자열을 입력받아서 0에서 M-1 사이의 값을 반환하는 해시 함수를 만들면 됩니다. 그러면 위와 같이 해시 함수를 만들면 어떨지 같이 고민을 해보겠습니다. 혹시 코드가 조금 안익숙한 분이 있을까봐 설명을 드리면, 만약 문자열이 "ab"라고 할 때 x에는 a와 b가 차례로 들어갑니다. 그리고 h += x; 를 하면 a의 아스키코드 값인 97과 b의 아스키코드 값인 98이 h에 더해져서 h는 195가 됩니다.

 

이렇게 해시 함수를 만들면 뭐 돌아는 가겠지만 좀 치명적인 문제가 있는데, 해시 함수의 값이 굉장히 한정적입니다. 예를 들어서 해시 함수의 키가 최대 100글자라고 해보겠습니다. 우리는 해시 함수의 결과가 0에서 M-1 사이에 좀 잘 흩뿌려져서 충돌이 별로 안생기길 원하는데 문자의 아스키코드 값이 128보다 작습니다. 그러면 100글자라고 했을 때 이 해시 함수의 결과는 12800보다 작습니다. 즉 0부터 1000002 사이에서 나오는게 아니라 0에서 12800 사이에서만 나오는거고, 충돌이 많이 날 수 밖에 없습니다.

 

그러면 이런 경우에 써먹기 좋은 해시 함수가 뭐가 있냐면, 마치 문자열을 진법으로 생각하는 방법입니다. 예를 들어서 10진수 123 = 1 × 10² + 2 × 10¹ + 3 × 10⁰ 인 것 처럼, 문자열을 대충 뭐 1000진법으로 생각을 하면 됩니다. 저기서 'a', 'b', 'c'는 아스키 코드 값을 의미합니다. 이러면 값이 금방 커지니까 0에서 M-1 사이에서 잘 퍼질 수 있습니다. 이러한 해시 함수를 롤링 해시라고 하고 관련해서 재밌는 성질들이 많긴한데, 또 이걸 구버전에서는 설명을 했었는데 지금 생각하니 좀 과한 것 같아서 자세한 설명은 생략하고 그냥 문자열에 대한 해시는 이 롤링 해시를 쓰겠습니다. 구현 방법은 위의 코드를 참고합시다. 보면 직접 a, 즉 1000의 0승, 1승, 2승, ... 을 다 저장하고 있을 필요가 없고 저렇게 아주 간단하게 처리가 가능합니다. 다른 a나 M을 써도 상관은 없다만 a × M이 int의 최댓값을 넘는다면 저렇게 짰을 때 int overflow가 날 수 있다는건 주의를 해야 합니다. 그러면 이제 해시 테이블의 크기도 정했고 해시 함수도 정했으니 해시 자료구조를 짜보겠습니다.

 

일단 Chaining 방식부터 구현을 해보겠습니다. 이 방식은 연결 리스트를 필요로 한다는 점이 조금 마음에 들지 않습니다. 연결 리스트 구현이 필요하다는 의미이기 때문입니다. 그렇긴 한데 해시 자체는 연결 리스트를 여러개 두고, 키를 가지고 적절한 연결 리스트로 찾아간 후 그 연결 리스트에서 삽입, 삭제, 변경 등을 하면 끝이라 연결 리스트 에 충분히 익숙하다는 가정 하에 생각할게 적어서 좋긴 합니다. 그러면 연결 리스트를 어떤 식으로 구현해야 하나 했을 때 야매 연결 리스트라고 우리가 믿고 있는 녀석이 있습니다. 제 구현은 야매 연결 리스트를 바탕으로 하고 있기 때문에 이걸 모르면 진행이 어렵습니다. 그렇기 때문에 야매 연결 리스트를 모르거나 좀 가물가물하다 싶으면 0x04강 - 연결 리스트를 다시 한 번 확인해보고 오는걸 추천드립니다.

 

야매 연결 리스트에서는 연결 리스트 하나에 pre, nxt 배열을 할당해서 포인터를 배제하고 어째저째 구현을 했는데 지금은 각 칸에 다 연결 리스트가 있어야 하니 연결 리스트를 M개 사용해야 합니다. 이런 상황에서 각 연결 리스트마다 pre, nxt 배열을 전부 따로 만들면 pre 배열도 M개 필요하고 nxt 배열도 M개 필요합니다. 이는 바람직하지가 않습니다. 운이 안 좋아서 한 쪽의 연결 리스트에 값이 다 몰리더라도 정상적으로 동작을 하게 하려면 각 pre, nxt 배열의 크기가 최대 삽입 횟수만큼이어야 하고, 예를 들어서 삽입이 최대 50만번 발생한다고 가정하면 크기가 50만인 배열을 pre에서 100만개, nxt에서 100만개 선언해야 합니다. 이건 메모리가 감당이 안 됩니다. 대신에 각 연결 리스트에서 pre, nxt를 공통으로 사용하도록 살짝 구조를 고쳐야 합니다. 어떤 느낌인지 예시를 보여드리겠습니다.

 

갑자기 표가 너무 많이 등장해서 좀 혼란스러울 수 있는데, 위에 pre, nxt는 말 그대로 야매 연결 리스트에 필요한 pre와 nxt 값을 나타냅니다.

 

그리고 칸이 저렇게 나뉜건 연결 리스트에서의 인덱스, 키, 값을 의미합니다. 예시로 적은 저 칸은 연결 리스트 상에서 5번째 인덱스이고 키는 mango, 값은 62임을 의미합니다. 이제 여기서 실제로 삽입을 해보겠습니다. 키가 apple, 값은 36인 원소를 추가하겠습니다.

 

apple의 해시 값이 3이라고 하면 해시 테이블의 3번째 연결 리스트에 삽입을 해야 합니다. 첫 원소니까 0번지로 두고, 0번지의 pre와 nxt 값은 -1이 됩니다.

 

다음으로 banana, 15를 삽입해보겠습니다. banana의 해시 값은 0이라고 하겠습니다. 그러면 0번지의 다음인 1번지로 두고, 해시 테이블의 0번째 연결 리스트에 삽입을 하고, pre와 nxt 값은 마찬가지로 -1로 둡니다.

 

다음으로 melon, 20이 삽입되고 melon의 해시 값도 0이어서 충돌이 발생했습니다. 해시 테이블의 0번째 연결 리스트에 삽입을 해야 하는데, 연결 리스트의 제일 앞에 삽입을 해도 되고 제일 뒤에 삽입을 해도 되고 중간에 삽입을 해도 되는데, 저는 제일 앞에 삽입을 하겠습니다. 다만 반드시 주의해야 하는건, 이전에 만약 melon이 있었다면 새로운 원소를 만드는 대신에 거기에 값을 덮어써야 합니다. 그래서 설령 삽입을 제일 앞에 하지만 0번째 연결 리스트의 모든 원소를 꼭 확인해야 합니다.

 

다음으로 banana, 52를 삽입하면 이미 banana가 있으니 새 원소를 추가하는 대신 banana가 있는 원소의 값을 변경합니다.

 

이 뒤로는 굳이 더 설명이 필요없을 것 같아서 적당히 건너뛰겠습니다. 연결 리스트를 익히고 왔다면 크게 어려울건 없겠지만 찝찝하면 한 번 pre, nxt 값을 눈여겨 보도록 합시다.

 

다음으로 제거는 딱 하나만 같이 보겠습니다. melon을 제거하고 싶다고 하면 일단 melon의 해시 값을 계산해서 해시 테이블의 0번째 연결 리스트를 확인합니다.

 

먼저 제일 앞에 있는 5번지의 값을 보면 키가 orange니까 melon이랑 달라서 패스합니다.

 

nxt를 타고 다음 원소로 가보면 키가 melon으로 일치합니다.

 

그러면 해당 원소를 제거하면 됩니다. 이 때 야매 연결 리스트를 다룰 때 이미 봤었지만 2번지의 pre, nxt를 굳이 바꿀 필요는 없고, 2번지의 pre인 5의 nxt와 2번지의 nxt인 1의 pre만 변경하면 됩니다.

 

이렇게 눈으로 볼 때는 뭐 대충 그런가보다, 크게 어렵지는 않네 싶을텐데 구현을 하려고 하면 은근 헷갈리고 실수도 많이 나옵니다 그래도 야매 연결 리스트는 알고 있으니까 나는 아예 밑바닥에서 짜보겠다 하시면 그렇게 하시고, 스켈레톤 코드를 받아놓고 진행하고 싶다 하면 코드를 드릴테니 간단하게 설명을 듣고 직접 짜보면 됩니다. 사실 스켈레톤 코드를 참고해서 푸는걸 추천드리긴 합니다.(코드)

 

스켈레톤 코드를 보면 대체 이게 뭐하는 코드인가 당황스러울 수도 있는데 찬찬히 같이 보겠습니다. 먼저 M은 테이블의 크기를 의미합니다. a는 해시 함수에서 사용할, 곱하는 값이고 MX는 최대 삽입 횟수입니다. 다음으로 head는 각 M개의 연결 리스트에 대해 시작 주소를 의미합니다. main 함수를 보면 알겠지만 처음에는 -1로 초기화가 되어 있습니다. 나중에 insert를 하거나 erase를 할 때 뭔가 적절하게 이 head의 값이 바뀌어야 합니다. pre, nxt는 연결 리스트에서 이전과 다음 원소를 의미하고 key, val은 키와 값 쌍을 저장할 배열입니다. unused는 야매 연결 리스트에서 사용할, 새 원소를 추가할 인덱스를 나타내기 위한 변수입니다.

 

find, insert, erase 함수는 각각 키를 이용해 값 찾기, (키, 값) 삽입, 키에 대응되는 원소 지우기 기능을 수행하는 함수인데 find 함수에서 그냥 키에 대응되는 값을 반환하는 대신 왜 저렇게 인덱스를 반환하게 했냐면 살짝 스포일러가 될 수도 있긴 하지만 find 함수를 저렇게 둬야 insert와 erase를 구현할 때 유용하게 써먹을 수 있습니다. 그러면 구현을 해보는 시간을 가져봅시다. test 함수를 통해 테스트를 해볼 수 있고 만약 올바르지 않게 동작할 경우 assert에 걸려서 프로그램이 중간에 중단됩니다. 만약 중단되지 않고 good!이 잘 출력됐다면 구현을 올바르게 했다고 볼 수 있습니다. 그리고 M이 너무 크면 해시 충돌이 잘 안 일어나서 작성한 코드가 충돌을 정말 제대로 처리하는지 확인할 수가 없으니 M을 101, 23, 아니면 아예 5 이렇게 줄였을 때에도 잘 동작하는지 확인해보고 실제로 저희가 앞에서 STL을 가지고 푼 연습 문제를 직접 만든 해시로 풀어서 제출해봐도 검증을 확실하게 할 수 있습니다. 다음 슬라이드부터 바로 코드를 소개할거니까 풀어보고 넘어오도록 합시다.

 

먼저 find 함수를 보면 입력받은 키 k의 해시 값을 구하고 그걸 토대로 연결 리스트의 시작 지점을 찾습니다. 그리고 계속 nxt로 이동하면서 키가 k인 원소를 찾으면 됩니다.

 

insert 함수에서는 우선 find 함수를 이용해서 키 k가 이미 해시 테이블에 있는지 확인합니다. 해시 테이블에 있다면 04, 05번째 줄 처럼 해당 인덱스에서 값만 교체하는걸로 끝납니다. 만약 없다면 unused번째에 키 k, 값 v를 넣고 head[h]를 unused로 만들어줄 예정입니다. 이 과정에서 기존에 head[h]에 다른 값이 있었다면 적절하게 nxt, pre를 바꿔줘야 합니다.

 

마지막으로 erase 함수에서는 일단 find 함수를 이용해서 키 k가 이미 해시 테이블에 있는지 확인하고, 만약 있다면 연결 리스트에서 하던 것 처럼 pre와 nxt를 적절하게 연결해주면 됩니다. 단 지우는 원소가 head일 경우에는 꼭 head[h]를 변경해줘야 합니다. 생각보다 그렇게 복잡하지는 않습니다. 아마 직접 짰다면 코드가 더 비효율적이거나 아니면 nxt, pre를 왔다갔다 하다가 뭔가 꼬여서 막 -1번지를 참조하고 이런 안타까운 일이 발생할 수 있겠지만 도전하는 당신이 아름답습니다. 혹시 직접 짜봤는데 잘 안됐다면 원소의 연결 상태를 그림으로 그려보던가 해서 무엇이 잘못된건지 잘 찾아보길 바라겠습니다.(코드)

 

두 번째로 Open addressing을 구현해보겠습니다. 이것도 마찬가지로 스켈레톤 코드를 참고하실 분은 그렇게 하시고, 아예 맨 바닥에서부터 해보겠다 하시면 그것도 좋습니다.(코드)

 

스켈레톤 코드를 보면 M과 a는 그대로고, EMPTY, OCCUPY, DUMMY는 각 칸의 상태를 나타내는 값입니다. EMPTY는 비어있다는 의미이고, OCCUPY는 칸에 값이 들어있다는 의미이고, DUMMY는 칸에 값이 있었다가 제거되었다는 의미입니다. DUMMY를 두지 않으면 나중에 탐색에서 문제가 될 수 있다는건 앞에서 Open addressing을 설명할 때 얘기했었습니다. status 배열은 단어 그대로 각 칸의 상태를 나타낼 배열입니다. main 함수의 시작을 보면 알겠지만 처음에는 status 배열이 EMPTY로 초기화가 되어 있어야 합니다. key, val은 키와 값 쌍을 담고 있는 배열이고 나머지 함수들은 Chaining과 똑같습니다. 마찬가지로 함수들을 하나씩 구현해보도록 합시다. 각 함수를 실행한 후 status 값을 잘 조정해야 하고 탐색을 할 때나 insert할 위치를 찾을 때 DUMMY를 어떻게 처리해야 하는지도 유의해야 합니다. 그리고 probing 방법을 3가지 배웠는데 저는 그냥 마음 편하게 Linear probing으로 구현했습니다.

 

먼저 find를 보면 인덱스를 키 k의 해시 값으로 찾고, EMPTY가 아닐 때까지 탐색을 이어나갑니다. DUMMY를 만나더라도 탐색을 이어나가야하는걸 주의하셔야 합니다. 그렇게 이동을 하다가 key[idx]가 k와 일치하는 곳을 찾아야 하는데, 단 status[idx]가 OCCUPY인지를 확인해야 합니다. 왜 이걸 확인해야 하냐면, 나중에 erase에서 key, val 배열의 값을 바꾸는 대신 status만 DUMMY로 바꿀 예정입니다. 그렇기 때문에 status가 OCCUPY인지 확인하지 않고 key[idx]가 k만 일치하는지만 본다면 실제로는 status가 DUMMY여서 제거된 원소인데도 불구하고 그 인덱스를 반환하는 일이 생길 수 있습니다. 만약 EMPTY에 도달했다면 k가 없음을 확신하고 -1을 반환하면 됩니다.

 

다음으로 insert를 보면 find 함수로 키 k가 있는 위치를 찾습니다. 있다면 그냥 val[idx]에 v를 쓰고 끝내면 되고, 없다면 새로 쓸 곳을 찾아헤매야 하는데 새로 쓸 곳은 status가 EMPTY이거나 DUMMY인 곳이면 됩니다. 그렇기 때문에 while문을 저렇게 쓰면 됩니다. EMPTY이거나 DUMMY인 곳을 찾으려면, status가 OCCUPY일 때 까지 계속 while문을 돌리면 됩니다.

 

마지막으로 erase는 아주 간단합니다. 그냥 find로 위치를 찾고, 있다면 status를 변경하는걸로 끝납니다. 이렇게 Open addressing이 완성되었고 코드를 보면 알겠지만 Open addressing이 Chaining 방식보다 구현이 간단해서 꼭 해시를 짜야한다면 저는 Open addressing 방식을 선호합니다. 해시 자료구조에 친숙해지자는 의미로는 두 방식 모두를 직접 구현해보시고, 실제로 직접 해시를 짜야할 일이 많은 상황이라면 두 개 중에서 편한 방식을 잘 익히면 됩니다. 제가 test 함수를 제공했지만 저 함수는 아주 작은 테스트 예시이기 때문에 직접 짠 해시 자료구조가 test 함수에서 잘 돌아간다는 것만으로 안심하지 마시고, 사용법도 익힐겸 강의에서 다룬 연습 문제를 직접 짠 해시 자료구조로 풀어서 제출해보시는걸 추천드립니다. 그리고 지금은 unordered_map처럼 키에 대응되는 값을 보관하는 자료구조를 만들었지만 val 배열을 빼면 그냥 unordered_set처럼 쓸 수 있게끔 만들 수도 있습니다. 이건 되게 간단해서 굳이 직접 코드를 보여드리지는 않겠습니다.(코드)

 

이렇게 해시 강의가 끝이 났습니다. 사실 제 강의에서는 해시를 굉장히 자세하게 설명을 드렸지만 해시 자료구조를 이해하지 않고 배열이 0, 1, 2, 3, ... 을 인덱스로 받아서 원소를 반환하는 자료구조인 것 처럼 해시는 문자열이나 아니면 음수같은 아무 값이나 다 인덱스로 받아서 원소를 반환하는 자료구조라고만 받아들이고 문제를 푸는 분들도 정말 많습니다. 당장 코딩 테스트에도 문자열을 받은 후 정수에 대응시켜야 하는 상황이 많아서 이 강의를 보기 전에도 STL unordered_set, unordered_map 혹은 이진 검색 트리인 STL set, map 자체는 아마 문제를 풀어보다가 어디선가 접해보신 분이 있을 것 같습니다. 하지만 해시 자료구조의 정확한 원리를 배우고 나면 성능이 보장되지 않는다는 의미가 무엇인지, 충돌이 무슨 뜻인지 등을 이해할 수 있기 때문에 그런걸 모른채로 그냥 가져다 쓰는 것 보다는 원리를 알고 쓰는게 더 바람직하고 또 원리를 알아야 적재적소에 해시를 활용할 수 있습니다. 그럼 고생 많으셨습니다.