해시 테이블이 뭘까?
해시 테이블은 키를 값에 매핑할 수 있는 구조인 연관 배열 추상 데이터 유형(associative array abstract data type)을 구현하는 데이터 구조를 말한다. 해시 테이블은 해시 함수를 사용하여 원하는 값을 찾을 수 있는 버킷 또는 슬롯의 배열로 인덱스를 계산한다.
검색하고자 하는 키값을 입력받아 함수를 돌려 그 함수에서 반환받은 해시코드를 배열의 인덱스로 환산해서 데이터에 접근하는 자료구조를 말한다. 입력데이터가 정확히 일치해야만 해시코드를 만드는 함수는 같은 해시코드를 만들어낸다.
전달하는 키값은 배열, 숫자, 파일 등 무관하다.
해시코드 자체가 배열의 인덱스로 사용되므로 검색속도가 빠르다.
해시 테이블은 어떻게 생겼을까?
해시 테이블에서의 충돌?
배열의 한 인덱스에 지나치게 많은 값들이 배정되는 경우 ‘충돌이 발생한다’고 말한다. 해시 테이블의 장점이 검색시간이 매우 빠르다는 것O(1)인데, 충돌이 발생하면 최대 O(n)만큼 늘어나게 된다. 따라서 해시 테이블에서 좋은 알고리즘은 입력 받은 키값을 바탕으로 해시코드를 얼마나 잘 분배하느냐에 따라 달려있다고 할 수 있다.
해시 함수는 다른 서로 다른 키 값으로 같은 해시 코드를 만들기도 하는데, 제공할 수 있는 키 값은 무한한데 반해서 해시코드는 정수 개수 만큼만 제공할 수 있기 때문이다. 따라서 어떤 키 값은 중복되는 해시 코드를 가질 수 밖에 없다.
다음으로는 해시코드는 서로 다른데 같은 배열의 인덱스에 배정되는 경우이다. 이 경우에도 위와 같은 결과가 나타나며 충돌이 발생하게 된다.
