해시함수
-
[자료구조] 해시 테이블Stage/Computer Science 2021. 6. 2. 08:44
학습 목표 해시 테이블의 원리와 구조를 설명할 수 있다. 왜? 연결리스트나 트리에서는 값을 검색할 때 O(n) 또는 O(log n)의 시간이 걸렸다. 이 시간을 조금 더 단축해서 거의 O(1)에 가깝게 할 수도 있을까? 이것을 가능하게 해주는 해시 테이블이라는 자료 구조에 대해서 알아보자. 1. 해시 테이블? 해시 테이블은 연결 리스트의 배열이다. 여러 값들을 바구니에 나눠 담는 상황을 생각해보자. 각 값들은 해시 함수라는 맞춤형 함수를 통해서 어떤 바구니에 들어갈지 결정이 된다. 각 바구니에 들어가있는 값이 여러 개라면 그 값들은 그 바구니에서 새롭게 정의되는 연결 리스트로 이어진다. 한 바구니에 1, 3, 4가 들어있다면 1, 3, 4는 연결 리스트로 이어진다. 이처럼 연결 리스트가 담긴 바구니가 여..