해시테이블 (1) 썸네일형 리스트형 해시테이블 1. 해시 테이블 해시테이블은 해시맵이라고도 불리며, Key와 Value라는 두 가지 값을 함께 맵핑하여 데이터를 저장하는 자료구조이다. 이미 각 언어들은 내부적으로 해시테이블의 기능을 제공하고 있고 대표적으로 Python에는 딕셔너리가, Java에는 Map 컬렉션을 통해서 해당 기능을 제공하고 있다. 해시 테이블은 Key를 임의의 해시 함수에 입력하여 출력된 해시 값을 데이터가 저장되는 배열의 인덱스로 활용한다. 따라서, 특정 value에 접근하려 할 때 key를 통해서 해당 value에 바로 접근하는 것이 가능하기 때문에 $O(1)$의 시간복잡도를 가진다. 보통 배열로 미리 hash table의 크기만큼 공간을 만들어두고 사용하지만, 해시 테이블에서는 충돌이라는 이벤트가 자주 발생한다. 이 충돌을 가.. 이전 1 다음
