해시 테이블

오늘은 멘토님의 갑작스러운 질문에 답변하지 못했던 기억을 되살려 해시테이블을 뿌셔보려고한다.

사실 swift에서는 굳이 해시 테이블을 직접 구현해서 쓸일 이 없다 왜냐면 딕셔너리가 있기 때문이다.

 

하지만 꼭 내가 swift만 공부할거라는 보장도 없고 이번 기회에 내부적으로 어떤식으로 공부하면
다른 언어에서도 자료구조 공부할 떄 도움이 될 것 같다 .

 

그러면  거두절미하고 바로 들어가보자.

 

해시 테이블이란? 

 

해시 테이블은 Key - value 형태로 데이터를 저장하는 자료구조 중 하나이며 다음과 같은 특징을 같는다.

특징

• key 값을 해시 함수를 통해 해시 주소값 해시 index(해시 주소값)으로 바꾼다.
• value에 접근할 때는 위에서 만든 해시 index을 통해 접근한다.
• 해시 테이블의 평균 시간 복잡도는 O(1) , 최악의 경우 O(n)  이다.

 

한번 위 특징들을 아래에서 하나씩 증명해나가보자.

---

해시 함수란?

함수란 보통 인풋 , 계산 , 아웃풋으로 구성되어있는건 우리 모두 알고 있다.

해시 함수 역시 마찬가지다. 우리는 여기서 아웃풋에 집중해야한다.

 

해시함수란 고정된 길이의 고유한 인덱스 값으로 변환하는 역할을 하는 함수이다. 

이렇게 변환하는 과정을 해싱이라한다.

 

종류

• sha-1
• sha-256
• ...

그렇다면 해시 함수를 넣으면 key값만 다르면 항상 겹치지 않는 고유한 인덱스로 변환이 가능할까?? 정답은 그렇지 않다.

 

이렇게 서로 다른 key값에 대해 해시 index가 같을 때를 해시 충돌이라한다.

이번에는 해시충돌에 대해 알아보자.

---

해시 충돌이란?

해시 충동이란 서로 다른 key에 해시 인덱스가 같을 때를 해시 충돌이라한다.

 

그렇다면 어떤 해결법이 있을까 ??  크게 2가지 알고리즘이 있다. 

 

1. Chaining (닫힌 주소)
2. Linear Peobing (오픈 주소)

 

분리 연결법, Separate Chaining

 

• 충돌이 일어날 경우, 연결 리스트를 이용하여 데이터를 추가 저장

장점

• 한정된 bucket을 효율적으로 사용 가능
• 확장이 필요없고 구현이 간단함
• 손쉽게 삭제할 수 있음
• 상대적으로 적은 메모리 사용, 미리 공간을 잡아 놓을 필요가 없다.

단점

• 성능이 좋지 않은 해시 함수로 인해 동일 주소에 여러 값이 들어갈 수 있다.
• 해시 테이블의 장점 퇴색

---

개방 주소법, Open Addressing

• 충돌이 일어날 경우, 빈공간이 나올 때까지 해당 해쉬 인덱스부터 순회하며 빈 공간이 나오면 저장

장점

• 체이닝처럼 포인터가 필요 없고 지정한 메모리 외에 추가적인 공간이 필요 없다.
• 삽입 삭제 시 오버헤드가 적다

단점

• 최악의 경우 비어잇는 버킷을 찾지 못하고 시작위치로 되돌아 올 수 있음
• 특정 위치에만 데이터가 몰리는 현상이 발생할 수 있다.
• 데이터를 삭제하면 삭제된 공간은 dummy space로 활용되어, 재정리 해주는 작업이 필요함

 

1. Linear Probing

선형 탐색 , 해시 충돌 시 고정된 폭 만큼 다음 버켓으로 이동하여 비어잇는 버켓에 데이터를 삽입한다.

 

2. Quadratic Probing

해시 충돌 시 제곱만큼 건너뛴 버켓에 데이터 삽입, 2^1 .. 2^2 ... 2^3 씩 점점 커짐

3. Double Hashing Probing

해시도니 값을 한번 더 해싱하여 해시의 규칙성을 없애버린느 방식

 

---

장단점과 시간 복잡도

장점

• 데이터 저장/ 읽기 속도가 매우빠름
• 키를 이용하여 데이터 접근이 매우 편리함

단점

• 저장곤이 많이 필요함  , 충돌 문제를 해결하기위해
• 충돌 발생 시 해결하기 위해 별도의 자료구조가 필요

시간복잡도를 얻기 위해 공간 복잡도를 희생한 느낌

 

보통 시간 복잡도는 O(1)이지만, 최악의 경우 O(n)이 걸린다.

 

그래서 보통 저장, 검색, 삭제등 탐색을 많이하는 캐시에 이용이 많이됨

 

---

참고

 

Swift) 해시 테이블(Hash Table) 이해하기

 

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

 

Hash란 무엇인가?