6: 자료구조-6(해시 테이블)

해시 테이블에서는 단어나 이름 같은 입력값이 들어온다면 그 단어에 포함된 문자를 보고 어디에 그 이름을 넣을지 결정하는 방식이 흔하게 사용됨

- 이름이 해시 테이블에 저장되며, 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 해시 함수는 ‘이름의 가장 첫 글자’인 경우, 각 포인터는 그 알파벳을 시작으로 하는 이름들을 저장하는 연결 리스트를 가리키게 됨

- 해시 테이블 -> 세로: 배열 / 가로: 연결 리스트

- 충돌: 어떤 값을 넣으려고 하는데 이미 무언가 들어가 있는 경우. / 최대한 충돌을 피해야 함!

인덱싱을 하는데 사용하는 배열 -> 해시 함수

Albus를 해시함수에 넣으면 0이 반환되어서 0번째 배열 즉 A에 해당하게 됨

Harry를 해시함수에 넣으면 7이 반환되어서 7번째 배열 즉 H에 해당하게 됨

만약 해시 함수가 이상적이라면, 배열의 연결 리스트에는 단 하나의 값들만 담기게 됨 따라서 검색 시간은 O(1)

그렇지 않은 경우, 최악의 상황에(모든 이름이 특정 알파벳으로 시작하는 경우)는 검색 시간이 O(n)이 될 수 있음

-> 평균적으로 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간 복잡도이지만 데이터의 충돌이 발생한 경우 O(n)까지 시간 복잡도가 증가할 수 있음

모두를 위한 컴퓨터 과학 (CS50 2019)

부스트코스 무료 강의

www.boostcourse.org

소소하게 매일