[CS 스터디 발표] 자료구조(Data Structure) - 4

Hash

가변길이 데이터를 해시 함수를 통해 고정길이 데이터로 바꾸는 것을 말한다.

 

Hash Table

Key, Value 로 데이터를 저장하는 자료구조이다. 해시 테이블에서는 내부적으로 배열을 사용하여 저장하고 키 값에 해시 함수를 적용해 인덱스를 만들고, 이를 활용하여 값을 조회하거나 저장한다.

 

Hash Collision

해시 함수를 통해 반환되는 값이 동일한 해시코드가 될 수 있는 경우 문제가 된다.

 

해결방법

1. 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식

2. 오픈 어드레싱 : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키 값에 저장되어있으면 다음 주소에 저장)

2-1. 선형 탐사

2-2. 제곱 탐사

2-3 이중해싱

Trie(트라이)

트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조다. 단순하게 하나씩 비교하면서 탐색하는 것보다 훨씬 효율적이다. 그러나 각 노드에서 자식들에 대한 포인터(pointer)를 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있다.