[자료구조] 해시 테이블이란?

✅ 들어가며

오늘은 매우 친근한 자료구조 형태인 해시 테이블에 대해서 정리하고자 한다. 

 

 

✅ 해시 테이블이란?

해시란 key- value 쌍의 데이터 형태를 가진 자료구조이다. 

기본적으로 Python의 dictionary , JavaScript의 Object 와 형태가 유사하다.

해시의 특징 및 장점 중 하나는 키를 통해서 즉시 value에 접근할 수 있기 때문에 저장,삭제,검색 의 시간복잡도가 전부 O(1)이다. 

 

여기서 key를 입력받으면 value를 어디에 보관해야 하는지에 대한 고민이 생긴다. 

 

🔸 직접 주소화 테이블?

 말 그대로 k를 그대로 주소로 사용하는 방법이다.

다만  key가 순서대로 존재하지 않고 1, 100, 9999 와 같은 경우 메모리 낭비가 심하며

key가 문자열인 경우 사용할 수 없기에 적절하지 않은 방법이다. 

 

따라서 일반적으로 아래의 Hash Table을 사용한다. 

 

 

🔸 Hash Table

해시 테이블은 key를 입력받고 value를 어디에 저장할 지 정하는 hash function을 활용한다.

   * h(key)= value를 저장할 위치  =>  "h(k)는 키 k의 해시값이다." 라고 표현한다.

 

다만 hash function을 이용하면 다른 key가 h(k) 값이 같은 상황이 발생할 수 있으며 이를 Collision이라고 표현한다.

 

 

> Collision 대응

따라서 Collision이 적게 발생하게 위해서 hash fuction을 잘 설계하는 것이 중요하며, 

동시에 피치못할 collision 발생시 Seperate Chaining, Open Adressing 등의 방법으로 해결한다. 

 

Seperate Chaining이란 Linked List의 형태로 노드를 추가해서 데이터를 저장하는 방식이다. 

 

Open Adressing은 미리 정한 규칙으로 빈 주소를 찾아가는 것을 말한다. 대표적으로 선형 조사법, 이차 조사법, 이중 해시 등이 존재한다. 

 

 

마지막으로 다른 자료구조와 시간복잡도 비교하면 다음과 같다.