자료구조 _ Hash table

Hash table은 무엇인가요?

해시테이블은 효율적인 탐색(빠른 탐색)을 위한 자료구조로 키-값 쌍의 데이터를 입력받습니다.

hash function h에 key값을 입력으로 넣어 h(k)를 위치로 지정하여 키-값 쌍을 저장합니다.

저장, 삭제, 검색의 시간복잡도는 모두 O(1)입니다.

 

 

 

좀 더 자세히 알아볼까요~

Direct-address Table을 먼저 알아봅시다.

직접 주소화 테이블이란? 키를 인덱스로 설정하여 저장하는 방식입니다.

직접 주소화 테이블의 단점은 키에 따라 빈공간이 생기고 공간을 낭비하게 됩니다.

또한 인덱스에 다양한 자료형의 키를 저장할 수 없습니다.

 

이러한 단점들을 보완하기 위해 해시 테이블을 사용합니다.

 

 

 

해시 테이블

해시 테이블은 hash function h를 이용, (키, 값)을 인덱스:h(k)에 저장합니다.

이 때, “키 k값을 갖는 원소가 위치 h(k)에 hash된다.”, “h(k)는 키 k의 해시값이다” 라고 표현합니다.

 

 

 

 

여기서 전제 조건은 '키는 무조건 존재'해야하며, '중복되는 키가 없어야' 합니다.

이러한 (키, 값)데이터를 저장하는 공간을, slot(row와 유사) 또는 bucket이라고 합니다.

낭비되는 공간을 최소화할 수 있고, 다양한 자료형의 키를 사용할 수 있습니다.(hash function의 알고리즘을 통해)

 

 

 

Collision(충돌)

collision이란 서로 다른 키의 해시값이 똑같을 때, 서로 동일한 인덱스를 부여받게 되어 충돌이 발생합니다.

이러한 충돌을 방지하기 위해서는 'seperate chaining' 또는 'open addressing' 방법을 사용해야합니다.