밸~하!

밸로그 여러분 안녕하세요!
오늘은 해시 테이블에 대해서 알아보겠습니다!

해시테이블에 대해서 알아보기 전에
잠깐 일상생활에서 한번 봐볼까요?

헬스장이나 학교에서 보던 사물함 기억나시나요?
각각 번호가 쓰여져 있고 위치가 정해죠있죠?
해시테이블은 마치 이 사물함과 같다고 할 수 있습니다!

해시테이블도 마찬가지로 key를 index로 변환하여 값을 넣게 됩니다!

그럼 index는 어떻게 만들어 질까요?? 한번 알아보겠습니다!

1. 해시 테이블 이란?

해시 테이블은 키와 값을 받아 키를 해싱(hashing)하여 나온 index에 값을 저장하는 선형 자료구조 입니다!

삽입은 O(1)곧 상수시간만이 걸리게 되며
키를 알고있다면 삭제와 탐색 또한도 O(1) 상수시간만이 걸리게 됩니다!

잠깐 용어 설명을 드리자면
각 테이블에 해당하는 index를 해시 테이블에서는 bucket이라고 부릅니다!
그리고 테이블의 각 요소는 key와 값을 둘다 저장하고 있어야합니다!

그럼 도대체 hash는 무엇일까요??
해시 하면 생각나는 음식이 있죠??
네 맞습니다! 바로 해시브라운의 그 해시입니다
해시의 의미는 고기와 감자를 잘게 다져 요리한것을 의미합니다!

해시 테이블의 해시도 입력받은 키를 잘게 잘라 숫자로 만든다는 점이 비슷합니다!

이번엔 해시 함수에 대해서 알아보겠는데요!

해시함수란?

입력받은 값을 특정 범위 내 숫자로 변경하는 함수입니다!
그렇기에 개발자의 마음대로 구현할 수가 있는데요!

이렇게 해시함수를 사용해서 해시테이블을 구현하면 완벽해 보일수도 있지만 한가지 문제가 있습니다!

바로 만약에 해시 함수의 결과가 동일하게 나타난다면 어떨까요??
이러한 상황을 바로 해시충돌이라고 부릅니다!

그럼 해시충돌은 어떻게 해결할 수 있을까요??

해시충돌 해결법

첫 번째 해결법

첫 번째 해결법은 바로 선형 탐사법입니다!

선형탐사법이란 충돌이 발생하면 옆으로 한칸씩 이동하는 방식입니다!

단순하지만 특정 영역에 데이터가 몰릴수 있다는 단점이 있으며
이후 또 충돌이 발생한다면 충돌이 발생하지 않을때 까지 이동하게 됩니다!

그래서 이름 그대로 최악의 경우 O(n)곧 선형시간이 걸릴 수 있습니다

그래서 특정영역에 데이터가 몰리지 않게끔 방법이 나왔는데요
바로 두번째 해결방법입니다!

두 번째 해결법

바로 제곱 탐사법입니다!

충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동하는 방식입니다

충돌이 커질수록 공간이 커지기 때문에 특정 영역에 데이터가 몰리는것을 방지할 수 있습니다

세 번째 해결법

세 번째 방법은 바로 이중해싱입니다!

이중해싱은 충돌이 발생했을때 또 다른 해싱함수를 사용하여 이중으로 해싱하는 방법을 의미합니다

충돌이 발생할 경우 기존의 해시함수가 아닌 다른 해시함수를 사용하여 새로운 인덱스를 만들어 냅니다!

또 충돌이 발생하면 충돌이 발생하지 않을때 까지 두번째 해싱함수로 지속적으로 해싱을 하여 인덱스를 만들어 냅니다!

마지막 해결법

마지막 해결법은 바로!
분리 연결법 입니다!

앞서 이야기드린 세가지 방법과는 다르게
충돌이 발생할 경우 다른 인덱스로 이동하지 않습니다!

그럼 어떻게 해결할까요??

인덱스로 이동하는 대신에 해시 테이블의 요소를 연결리스트로 만들어 충돌이 발생한 bucket에 그대로 요소를 추가합니다!

대신 이 방법은 최악의 경우에 하나의 bucket이 무한정 늘어날 수 있다는 단점이 있습니다!

자 이렇게 해시충돌의 4가지 방법에 대해서 알아보았는데요

그럼 다시 해시 테이블로 돌아오겠습니다

도대체 해시 테이블은 어디에 사용하는 걸까요??

바로 빠르게 값을 찾아야하는 경우 해시 테이블을 사용합니다

이전에 학습했던 연결리스트의 경우에는 전부다 탐색을 해야했기에 선형시간이 걸렸지만
해시 테이블을 사용하며 key와 index를 통해서 그 값을 알 수 있기 때문에 O(1)즉 상수시간만 걸리게 되어 어떠한것을 탐색할때 훨씬 빠르게 할 수 있습니다!
물론 최악의 경우에는 O(n)의 시간이 걸리지만 연결리스트보다는 훨씬 안정적이라고 할 수 있습니다!

자 오늘은 이렇게 해시 테이블에 대해서 알아보았는데요!

해시테이블의 정의와 왜 사용하는지 그리고 어디에 사용하는지를 알아가는 시간이었습니다!

그럼 오늘도 이만!
밸~바!