hash table (해시테이블)

출처 : 코드스테이츠

본 포스팅은 코드스테이츠의 immersive course 강의를 정리한 내용입니다.

 

 

 

hash table (해시테이블) 은 data structure이다.

어떤 data structure이냐면, 두 가지 관계를 연결시켜주는 것.

 

 

그럼 예를 들어서

bat을 넣으면 scary가 나오는 해시테이블 구조를 만들고 싶다면?

 

 

 

이렇게 배열에 인덱스에 하나하나 값을 집어넣어주는 방법이 있다.

그런데 이렇게 했을 때, bat을 찾으려면 0부터 하나하나 다 찾아야하기 때문에 O(n)의 시간복잡도가 나오게 된다.

 

우리가 원하는 것은 O(1)의 시간복잡도이기 때문에 위 구조는 곤란하겠다.

 

 

그러면 배열에 어떤 input을 했을 때, 그 index가 새롭게 나오게 되어 배열의 index에 값이 저장되는 구조를 만들면?

찾을 때도 O(1) 의 시간 복잡도로 찾을 수 있을 것이다.

 

그 index를 만드는 과정을 해시함수를 통해 구현할 수 있다.

 

 

 

그러면 바로 이런 모양이 나오게 된다.

오른쪽 해시함수에 dog를 넣으면 그 결과 값으로 5가 리턴되고 그러면 배열의 5번째 인덱스에 happy라는 값이 저장되게 되는 것이다.

 

그러면 이 해시 함수를 어떻게 만들어야할까? 조건이 3가지 있다.

첫번째, 리턴되는 index의 값은 무조건 array의 length보다 적어야한다. 그래야 array안에 담을 수 있기 때문이다.
두번째, input 이 같을 때 무조건 같은 index가 나와야 한다.
세번째, 해시함수는 저장을 할 수 없다. 그냥 그 때 그 때 input을 주면 index를 뱉어주면 된다.

 

그런데 해시함수에서는 예외적 상황이 발생할 수 있다.

 

이것은 바로 dog를 넣었을 때 index가 5가 나오고

fox를 넣었을 때도 index가 5가 나올 수도 있다는 것이다.

 

이것이 바로 해시충돌이라는 것이다.

 

이 때, 한 인덱스에 (dog-happy), (fox-quick) 두 개 다 들어가는 방법이 있다.

 

 

그래서 위의 슬라이드가 바로 해시테이블의 기본적인 구조라고 볼 수 있다.