cs50 6강 해시 테이블과 트라이

해시 테이블이란

해시 테이블을 한마디로 정의하자면, 연결리스트를 배열화한 것이다.
해시테이블을 구현할때 염두해두어야하는 것 중 하나는 키 값을 어떻게 정할 것인가이다.
만약 키 값을 잘못잡게 된다면 탐색시 굳이 자료를 걸러낸 정성이 무의미할 정도로 거지같은 시간복잡도를 가지게 될 수도 있다.

구성

해시 테이블은 기본적으로 key와 value를 가진 자료구조이다.
이 자료구조가 map이나 set과 다른 것은 자신의 고유의 인덱스 값을 설정가능하다는 데에 있다.

구현시 유의사항

서로 다른 키가 같은 해시값을 가지게 된다면 충돌이 발생할 수 있다.
또한 모든 해시값에 대한 배열을 생성하기 때문에 대용량 데이터 처리시 메모리의 사용량이 지나치게 증가할 수 있다.

트라이

트라이는 기본적으로 트리와 같이 구성되어 있으나, 각 노드가 배열의 형태를 가지고 있다.
즉 알파벳 문자를 저장할 때에는 a-z까지 가지고 있는 배열 안에 또 다른 배열을 집어넣는 형태가 되는 것이다.

장점

해시 함수를 구현하지 않아도 되기 때문에 개발자의 입장에서 편하다.
또한 문자열을 검색한다고 한다면, 특정 배열만을 딱 뒤적거리면 되기 때문에 간결한 탐색이 가능하다.

단점

모든 노드가 배열이므로 메모리를 지나치게 많이 먹을 수 있다.

기본 자료 구조

stack

접시 쌓기와 유사하다.
가장 늦게 들어온 값이 가장 일찍 나가는 구조이며, stack과 큐는 모두 양방향을 작동시키기엔 어렵기에 그런 경우 데크를 사용하는 것이 정신에 이롭다.

대표적 사용처

괄호를 파싱할 때에 사용하면 유용하다.
그 이유는 괄호의 경우 문자열의 끝까지 본 뒤에 제대로된 괄호인지 검색하지 않을 시 괄호가 괄호를 품고있는 형태에 대해서는 탐색하기 어렵기 때문이다.
그래서 맨 뒤에 값부터 검사가 가능한 stack는 괄호 탐색에 유용하다.

queue

스택과 반대다.
즉 빨리 들어온 자료는 빨리 나갈 수 있다.

code

이 둘을 구현한 코드는 이미 내 블로그에 올라와있으므로 링크만 첨부후 끝내기로 한다.
직접 구현해보기

딕셔너리

키와 값으로 이루어진 자료구조들이다.
대표적으로 map과 같은 것들인데, 이러한 자료구조에서는 key를 어떤 기준으로 산정할 것인가가 중요하다.
또한 key의 중복 여부에 따라 map이냐 set이냐를 선택할 수도 있다.(정렬 여부에 따라서는 unordered)