요즘 코딩테스트를 준비하면서 여러 자료 구조들을 마주치곤 합니다. Hash Table도 그 중 하나인데요.
이러한 Hash Table이 기술 면접에서 자주 언급되는 개념이라고 생각되기도 하고, 한 번쯤 제대로 짚고 넘어가야 할 필요가 있다고 생각 되기에, 오늘은 이 Hash Table이라는 자료 구조에 대해 공부하고 이해한 내용을 공유하려고 합니다.
What is Hash Table
Hash Table(해시 테이블)은 기본적으로 key, value 형태로 데이터를 저장하는 자료 구조입니다. 이러한 형태를 이용해 주료 효율적으로 데이터 탐색과 저장을 위해 사용됩니다.
위 그림은 Hash Table의 기본적인 구조를 보여줍니다. 각각의 Key가 어떤 범주 내에 속해있는지를 Index를 통해 찾고 있는데요.
'Apple'이 속한 범주(종류, 유형)를 탐색한다고 했을 때, Hash Function의 입력은 'Apple' 출력은 3이 되고, 이에 따라서 Index가 3인 'Fruit'를 Table에서 찾게 됩니다.
여기서 Hash Function의 역할을 어느정도 유추할 수 있는데요. Hash Function은 위의 그림처럼, 임의 길이의 입력('Apple')을 받아 고정된 길이(0, 1, 2, 3 ...)의 출력을 내는 함수입니다.
Hash Table은 각각의 Key에 Hash Function을 적용하여 고유한 Index를 생성하고, Index 값을 활용해 데이터를 저장하고 검색하게 됩니다. 이러한 Hash Table은 데이터를 저장하고 검색할 때 내부적으로 배열을 사용하는데, 이 배열을 Bucket(버킷)이라고 표현합니다.
Hash Collision
임의 길이의 입력을 특정 길이의 출력으로 간소화하여 데이터를 저장하는 구조는 효율적이고 속도 측면에서도 좋아보입니다.
그러나, 만약 출력된 '특정 길이'를 바라보고 있는 값이 중복 된다면 어떻게 될까요? 즉, 같은 Key를 가진 값이 버킷에 존재하게 된다는 것인데요. 이러하 상황을 Hash Collision(해시 충돌)이라고 합니다.
이러한 Hash Collision 여러 번 발생하게 되면, 성능적인 측면에서 악영향을 끼칠 수 있습니다. 때문에 이 Hash Collision을 고려하여 Hash Function을 설계해야 합니다.
하지만, 그럼에도 충돌이 일어나는 경우에는 다양한 해결 방안을 통해 충돌을 해결할 수 있습니다.
Solution1. Seperate Chaning
첫번째로는, Seperate Chaning. 즉 분리 연결법입니다.
Seperate Chaning이라는 이름에서 어느정도 유추할 수 있듯이, Seperate Chaning은 동일한 Hash 값을 가진 모든 요소들을 Linked List(연결 리스트) 형태로 저장하는 방법입니다. 위의 Hash Collistion 예시에서도 Seperate Chaning을 이용하여 '15'와 '8'를 Index 1에 함께 저장하되, Linked List 형태로 각각의 데이터를 연결하고 있습니다.
이렇게 되면 우선 적으로 '15'를 삽입할 때, 인덱스 1에 '15'와 이 데이터를 저장하는 노드를 추가합니다. 그리고 '8'을 삽입할 때, 이미 인덱스 1에 '15'의 노드가 존재하기 때문에, 이 경우 새로운 노드를 생성하고, '15' 노드의 다음 노드로 연결합니다.
이렇게 된다면 최종적으로, Index 1에는 '15' 노드가 있고, 이 노드는 '8' 노드를 가리키는 포인터를 가지고 있게 됩니다.
Solution2. Open Addressing
두번째로는, Open Addressing(개방 주소법)입니다.
Open Addressing은 꽤나 단순한데요. 동일한 Index에 데이터가 있을 경우, 다음 Index로 이동하여 해당 Index가 비어있는 지의 여부를 검사하고, 비었다면 해당 Index에 데이터를 저장합니다.
위의 그림에서는 Index 152에 'Sandra Dee'라는 데이터를 저장하려 했지만, 이미 Index 152에는 'Jhon Smith'라는 데이터가 있기 때문에 비어있는 Index 153에 값을 다시 저장하고 있는 모습을 볼 수 있습니다.
글을 마치며
이번 글에서는 이렇게 Hash Table에 대해 간단히 알아보았습니다. Hash Table을 공부하면서 Binary Search Tree(이진 탐색 트리)라는 자료 구조도 함께 언급되는 모습을 자주 볼 수 있었는데요.
여러분이 글을 끝까지 보셨다면, Binary Search Tree 또한 공부하고 이해하여, 이 두 자료 구조의 차이를 명확히 해두는 것도 좋을 것 같습니다.
글 읽어주셔서 감사합니다 :)
도움이 된 글
https://preamtree.tistory.com/20
