해시 테이블
Hash table ( hash map ) 이란 해시함수를 사용해서 변환한 값을 index 로 삼아 key 를 value 로 매핑하는 자료 구조를 의미한다. 해시 테이블은 다음과 같은 특징을 가진다.
- Key 값으로 Value 값을 찾을 수 있기 때문에, 매우 빠른 검색 속도를 가지고 있다.
- 특정 키값을 알면 value 값이 나오기 때문에 키 값은 Unique 해야한다.
- Key - value 의 1대1 매칭구조이기 때문에 삽입, 삭제, 검색 모두 평균적으로 충돌이 없는 경우 O(1) 의 시간 복잡도를 가짐
해시 함수
- Hash Code 를 만들어주는 함수
- MD5, SHA 가 대표적이다.
- 보통 1비트 값만 바뀌어도 값이 크게 바뀌는 눈사태 효과를 가지고 있다. ( 보안과 관련 )
해시 테이블의 장점
- 적은 리소스로 많은 데이터를 효율적으로 관리 가능
- 키와 해시값이 연관성이 없고 원본의 값을 뭉개버리기 때문에 높은 보안성
좋은 해시 함수의 조건
- simple uniform hashing 을 만족하는 함수
- 이는 중복이 없이 확률적으로 슬롯에 골고루 나눠지는 것을 의미한다.
Reference
'Algorithm' 카테고리의 다른 글
| [ 알고리즘 ] 스택, 큐 (0) | 2023.01.13 |
|---|---|
| [ 알고리즘 ] 그래프, 트리 (0) | 2023.01.13 |
| [ 알고리즘 ] 이진 탐색 ( Binary Search ) (0) | 2023.01.13 |
| [ 알고리즘 ] 배열과 링크드 리스트 (0) | 2023.01.12 |
| [ 알고리즘 ] 시간 복잡도와 공간 복잡도에 대하여 (0) | 2023.01.12 |