개발자라면 꼭 알아야할 Hash Table 의 모든 것! - 노마드 코더 Nomad Coders
- 해시 테이블은 자료구조 중 하나로, key:value 시스템을 사용하여 데이터를 정리(organization)한다.
- 해시 테이블과 배열(Array)의 비교
- key:value 쌍의 데이터를 배열에 저장한다면, 선형 검색(Linear search = full scan)을 통해 데이터를 찾을 수 있지만, 해당 방법은 시간이 오래 걸리는 방법이다.(데이터가 수십만 개라고 생각해보자). 시간복잡도 = O(n)
- 이럴 때, 해시 테이블을 사용하면 어떤 데이터를 검색하더라도 항상 빠른 검색이 가능하다. 시간복잡도 = O(1) - 해시 테이블도 배열의 구조를 이용하지만 Hash Function(해시 함수) 덕분에 빠른 검색이 가능하다.
- 해시 함수(Hash Function): 저장하고자하는 key 데이터를 숫자(Hash Code)로 바꾸는 역할. 숫자로 바뀐 key 데이터가 인덱스가 되는 것이다.
- 데이터를 검색할 때, key 데이터가 해시 함수를 통해 해시 테이블의 인덱스를 바로 특정할 수 있기 때문에 빠른 검색이 가능한 것이다.
- 해시 충돌(collision): 해시 함수에 집어넣은 데이터는 다르지만, 같은 결과 데이터(같은 인덱스를 가리킴)가 나오는 경우
- 충돌을 피하기 위해, 해당 인덱스의 value로 또 배열을 집어넣는 방법을 채택할 수 있다. value에 저장된 배열에 접근하여 선형 검색을 통해 찾고자 하는 데이터를 찾는 것이 가능하다.
- 위와 같은 이유 때문에 해시 테이블이 항상 상수 시간의 복잡도를 갖는 것은 아니지만, 평균적으로 여전히 상수 시간을 갖는다.
- 많은 프로그래밍 언어에서 이미 해시 테이블을 제공하고 있기에 이와 관련된 기능을 구현할 필요는 없지만, 구조와 원리에 대해서 파악하고 있는 것이 사용함에 있어서도 제대로 알고 사용할 수 있어 좋다.
안녕하세요.