해시 테이블 [Hash table] Part 1 : 빠르게 자료 넣고 찾자
2016. 8. 3.
자료구조를 배우면서 가장 감명 깊게(?) 배웠던 자료구조가 바로 해시 테이블이라는 자료구조이다. 자료를 빠르고 효율적으로 저장하는 것이 자료구조를 연구하는 가장 큰 이유일 것이다. 자료구조의 효율은 자료구조를 이용하는 대표적인 행동인 "삽입", "검색", "삭제" 등의 시간 복잡도와 공간 복잡도를 계산하고 점근적 표기법을 이용하여 나타내면 된다. (주로 Big O 표기법을 사용한다) 자세한 사항은 여기를 통해 공부하기 바란다. 간단하게 말하면 Big O 안의 식의 미지수가 무한에 가까워질 때 즉, Big O 안에 있는 식의 극한값을 이용하여 효율을 나타내고 비교하게 된다. 보통 시간 복잡도를 이용하여 비교한다. 가장 짧은 시간이 걸리는 자료구조? 지난번에 배웠던 연결 리스트나 스택 같은 자료구조는 삽입하..