* 해시 테이블
- 연결리스트와 트리구조에서 검색시간이 O(n)과 O(log n)이 걸렸다. 그러나 컴퓨터 공학자들은 이 시간을 더 단축시켜서 O(1)에 가깝게 만들기를 원했다.
- 위를 가능하게 해주는 구조 중 하나가 바로 해시 테이블이다.
- 해시테이블은 연결리스트를 원소로 가지는 배열이다.
- 이름표를 바구니에 담는다고 가정하자. 단순히 바구니 하나에 여러 이름표를 담으면 사람들이 찾는 데 오랜 시간이 걸릴 것이다.
- 그렇다면 바구니를 여러개로 한다면 어떨까. 이 때 바구니를 무슨 기준으로 나누는 것이 좋을까.
- 이 때의 기준이 해시 함수이다. 이름표이므로 해시함수를 이름의 가장 첫 글자로 시도해보자. 알파벳이라면 총 16개의 포인터들이 생기고, 그 알파벳은 각각 연결리스트를 가리키게 된다.
- 위와 같은 구조를 사용해서 검색시간을 비약적으로 줄일 수 있다.
- 즉 이론상 해시함수가 이상적이라면, 각 바구니에는 단 하나의 값만 담길 것이고, 검색시간은 O(1)이 된다.
- 그러나 최악의 해시함수를 사용해서 단 하나의 바구니에 모든 값이 담기면 O(n)이겠지만 일반적으로 최대한 많은 바구니를 만들도록 해시함수를 사용하므로 그럴일은 없다고 본다.
* 트라이
- 트라이(tries)는 트리형태의 자료구조이다.
- 트리형태와 다른 점은 각 노드가 배열로 이루어져있다는 것이다.
- 예를 들어 영어알파벳으로 이루어진 문자열 값인 이름을 저장한다면 노드 하나는 a부터 z까지를 갖고 있는 배열이된다.
- 각 배열의 요소는 다음 층의 노드를 가리킨다.
- Harry와 IU를 트라이에 저장한다면 루트 노드를 시작으로해서 각 알파벳을 따라가면서 노드를 이어준다.
- 위와 같은 트라이에서 값을 검색하는데 걸리는 시간은 문자열의 길이에 정비례한다. 왜냐하면 문자열의 각 문자를 보면서 트리를 하나하나 내려갈 것이기 때문이다.
- 일반적인 영어이름 길이가 n이라면 검색시간은 O(n)이라고 할 수 있다. 그러나 대부분의 이름은 그렇게 큰 숫자가 아닌 작은 값의 상수이므로 O(1)과 마찬가지로 본다.
참고
이 글은 하버드 대학교 David Malan 교수의 CS50 강의를 수강 후 정리하며 쓴 글입니다. 코드는 C언어로 작성되었으며, 개발환경은 CS50 IDE에 최적화되어 있습니다. 일부 라이브러리는 다른 환경에서 별도의 설정이 필요할 수 있습니다.
CS50 공식사이트
CS50
Introduction to the intellectual enterprises of computer science and the art of programming. This course teaches students how to think algorithmically and solve problems efficiently. Topics include abstraction, algorithms, data structures, encapsulation, r
cs50.harvard.edu
부스트코스
다 함께 배우고 성장하는 부스트코스
부스트코스(boostcourse)는 모두 함께 배우고 성장하는 비영리 SW 온라인 플랫폼입니다.
www.boostcourse.org
CS50 IDE
CS50 IDE
integrated development environment for students and teachers
ide.cs50.io
'Computer Science > Data Structure' 카테고리의 다른 글
| <자료구조> 우선순위 큐 (0) | 2021.04.11 |
|---|---|
| <자료구조> 트리구조 (0) | 2021.02.26 |
| <자료구조> 연결리스트와 노드 (0) | 2021.02.25 |
| <자료구조> 스택과 큐(2) (0) | 2020.11.22 |
| <자료구조> 스택과 큐(1) (0) | 2020.11.15 |
