📝Hash의 정의
데이터를 다루는 기법 중 하나로 검색과 저장을 빠르게하는 자료구조이다.
❗ 관련 용어
1) 해시테이블
- 해시테이블은 hash를 주소로 삼아 데이터를 key와 value로 저장하는
연관 배열구조이다.- 연관 배열은 자료구조의 하나로 키 하나와 값 하나가 연관되어 있으며 키를 통해 연관된 값을 얻는 것
2) 해시함수
- 임의의 길이의 데이터를 규칙을 거쳐서 고유한 인덱스 값으로 설정하는 함수
해시 함수 예시
1)Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다. ex) 주소 = 입력값 % 테이블의 크기
2)Digit Folding: 각 Key의 문자열을 ASCII(아스키) 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
3)Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m
4)Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 방법이다.
3) 해싱
- 해시 함수에서 해시를 출력하고 해시 테이블에 저장하는 과정
🔎 장단점
-
장점
- 해시테이블은 key와 value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가지고 있다.
- 내부적으로
배열(버킷)을 사용하여 데이터를 저장하기 때문에 검색 속도가 빠르다.해시테이블은 각각의 key값에 해시 함수를 적용해 배열의 고유한 인덱스를 생성하고 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
-
단점
- 해시 충돌이 발생할 수 있다.
- 순서/관계가 있는 배열과는 어울리지 않는다.
- 데이터가 저장되기 전에 저장공간을 미리 만들어야 한다. 공간을 만들었지만 공간에 채워지지 않는 경우가 발생하여 공간 효율성이 떨어진다.
- 해시 함수의 의존도가 높다. 해시함수가 복잡하다면 hash를 만들어 내는데 오래 걸리고 단순하다면 충돌이 잦아진다.
💥해시 충돌
해쉬 함수를 통해 나온 값이 동일한 슬롯에 해시되는 것을 해쉬 충돌이라고 한다.
해결 방법 1.분리연결법(Separate Chaining)
저장소에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트로 연결하는 방법이다.
-
장점
충돌이 나면 그때 공간을 만들어서 연결시킬 수 있다. 메모리 사용량을 줄여준다.
해시 테이블의 확장이 필요없어 간단하게 구현이 가능하고, 손쉽게 삭제할 수 있다. -
단점
같은 해쉬에 자료들이 많이 연결되면 검색시 효율이 낮아진다.
데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소한다.
해결 방법 2.개방주소법 (Open Addressing)
추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다.
-
장점
추가적인 메모리 공간을 사용하지 않기 때문에 Separate Chaining 방식보다 메모리를 덜 사용한다. -
단점
해시 테이블을 재정리 해주는 작업이 필요하다.
삭제하는 방법이 비교적 어렵다.
참고자료
