CS50 6. 자료구조(2) - 해시 테이블, 트라이, 큐/스택/딕셔너리

해시 테이블

• 해시 테이블은 ‘연결 리스트의 배열’
• 여러 값들을 몇 개의 바구니에 나눠 담는 상황을 생각해 보자.
• 각 값들은 ‘해시 함수’라는 맞춤형 함수를 통해서 어떤 바구니에 담기는 지가 결정된다.
• 각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결 리스트로 이어진다.
• 이와 같이 연결 리스트가 담긴 바구니가 여러개 있는 것이 ‘연결 리스트의 배열’, 즉 ‘해시 테이블’

쉬운 예로 아래 그림과 같이 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 ‘이름의 가장 첫 글자’인 경우를 생각해 보자.

그 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 각 포인터는 그 알파벳을 시작으로 하는 이름들을 저장하는 연결 리스트를 가리키게 된다.

 

• 만약 해시 함수가 이상적이라면, 각 바구니에는 단 하나의 값들만 담기게 될 것
• 따라서 검색 시간은 O(1)
• 하지만 최악의 상황에는 단 하나의 바구니에 모든 값들이 담겨서 O(n)이 될 수도 있다.
• 일반적으로는 최대한 많은 바구니를 만드는 해시 함수를 사용하기 때문에 거의 O(1)에 가깝다고 볼 수 있다.

 

트라이

• 트라이’는 기본적으로 ‘트리’ 형태의 자료 구조
• 특이한 점은 각 노드가 ‘배열’로 이루어져있다는 것입니다.
• 예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장한다고 한다면 이 노드는 a부터 z까지의 값을 가지는 배열
• 그리고 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z 배열)를 가리킨다. 

 

아래 그림과 같이 Hermione, Harry, Hagrid 세 문자열을 트라이에 저장해보면,

루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가면서 노드를 이어주면 된다.

 

 

• 위와 같은 트라이에서 값을 검색하는데 걸리는 시간은  ‘문자열의 길이’에 의해 한정
• 단순히 문자열의 각 문자를 보며 트리를 탐색해나가기만 하면 되기 때문
• 일반적인 영어 이름의 길이를 n이라고 했을 때, 검색 시간은 O(n)이 되지만, 대부분의 이름은 그리 크지 않은 상수값(예, 20자 이내)이기 때문에 O(1)이나 마찬가지라고 볼 수 있다.

 

그 외 자료구조

① 큐

• 큐는 메모리 구조에서 살펴봤듯이 값이 아래로 쌓이는 구조
• 값을 넣고 뺄 때 ‘선입 선출’ 또는 ‘FIFO’라는 방식을 따르게 된다. 가장 먼저 들어온 값이 가장 먼저 나가는 것
• 은행에서 줄을 설 때 가장 먼저 줄을 선 사람이 가장 먼저 업무를 처리하게 되는 것과 동일
• 배열이나 연결 리스트를 통해 구현 가능

 

② 스택

• 반면 스택은 역시 메모리 구조에서 살펴봤듯이 값이 위로 쌓이는 구조
• 따라서 값을 넣고 뺄 때 ‘후입 선출’ 또는 ‘LIFO’라는 방식을 따르게 된다. 가장 나중에 들어온 값이 가장 먼저 나가는 것
• 뷔페에서 접시를 쌓아 뒀을 때 사람들이 가장 위에 있는(즉, 가장 나중에 쌓인) 접시를 가장 먼저 들고 가는 것과 동일
• 역시 배열이나 연결 리스트를 통해 구현 가능

 

③ 딕셔너리

• 딕셔너리는 ‘키’와 ‘값’이라는 요소로 이루어져 있다.
• ‘키’에 해당하는 ‘값’을 저장하고 읽어오는 것. 마치 대학교에서 ‘학번’에 따라서 ‘학생’이 결정되는 것과 동일
• 일반적인 의미에서 ‘해시 테이블’과 동일한 개념이라고도 볼 수 있다.
• ‘키’를 어떻게 정의할 것인지가 중요