(자료구조) 해시 테이블

해시 테이블 (Hash table)

• 해시(Hash)란 키(key)와 값(value)이 한 쌍으로 구성된 데이터를 말한다.

• 해시 테이블은 배열처럼 인덱스(숫자로 된 키)를 부여해 해시 데이터를 저장한다.

• 하지만 들어오는 순서대로 인덱스를 배정하는 배열과 달리, 해시 테이블은 해시 함수를 통해 값에 대한 인덱스를 배정한다

• 해시 함수에 데이터의 키(key)가 인자로 들어가면 믹서기에 갈리듯이 숫자로 나오게 된다. 해시함수는 대표적으로 Modulo함수가 있다. 이렇게 나온 숫자는 데이터의 인덱스가 되는 것이다.
  

• 만약, 여러 데이터의 인덱스가 겹치게 되는 경우를 인덱스 충돌이라 부른다. 이를 해결하기 위해 보통 연결 리스트를 이용하며, 연쇄(체이닝) 구조로 연결해 들어오는 순서대로 연결해 저장한다.