.gif&blockId=11b00c82-b138-8050-a58b-dcbceda2ef8f)
해시
•
데이터를 다루는 기법
•
검색과 저장을 아주 빠르게 하는 자료구조
•
데이터를 저장할 때 Key-Value형태(딕셔너리)로 데이터가 존재
•
Key값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어나게 됨
해시 함수(Hash Function) & 해싱(Hashing)
•
해시 함수
◦
Key값을 고정된 길이의 해시로 변환하는 역할
•
해싱
◦
해시 함수에서 Key값을 hash로 변환하는 과정
•
해시 값, 해시코드
◦
해시 함수에서 Key값을 해싱 과정을 통해
▪
해시 값
▪
해시 코드
로 변경하며, 이 해시 값이 저장되는 위치가 됨.
•
해시 충돌
◦
서로 다른 키(key)가 같은 해시가 되는 경우
•
해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요
해시 테이블
•
연관 배열구조를 이용하여 데이터를 Key와 Value로 저장하는 자료구조
연관 배열 : 키 하나와 값 하나가 연관되어 있으며 키를 통해 연관되는 값을 얻을 수 있는 자료구조
ex)맵, 딕셔너리, 연상 배열, 결합 배열
일반적인 명령 지원
- 키와 값이 주어졌을 때, 연관 배열이 그 두 값을 저장하는 명령
- 키가 주어졌을 때, 연관되는 값을 얻는 명령
- 키와 새로운 값이 주어졌을 때, 원래 키에 연관된 값을 새로운 값으로 교체하는 명령
- 키가 주어졌을 때, 그 키에 연관된 값을 제거하는 명령
•
해시 테이블 : 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산
장점
•
중복 제거
•
데이터 캐싱, 보안에 주로 사용
•
배열 인덱스로 접근하기 때문에 삽입, 삭제 등의 연상이 빠름
단점
•
공간 복잡도가 커짐
•
충돌이 발생할 가능성 있음
•
순서 배열에는 부적합
해시 테이블 & 해시 맵
•
Java의 경우, 해시 테이블과 해시 맵의 가장 큰 차이는 동기화 지원 여부와 널(Null) 처리여부
해시 테이블 | 해시 맵 |
동기화 고려 | O |
Null 허용 | X |
충돌
•
서로 다른 문자열이 해시 함수를 통하여 해싱한 해시값이 중복인 경우
•
충돌이 많아질수록 탐색의 시간 복잡도가 O(1)에서 점점 O(n)에 가까워지게 됨
•
충돌 해결 방법
◦
Separating Chaining - LinkedList, Tree(Red-Black Tree)
◦
Open addressing - Linear Probing, Quadratic Probing, Double hashing
Separating Chaining
•
JDK 내부에서 사용하는 충돌처리 방식
•
LinkedList를 사용하는 방식
•
Tree(Red-Black Tree)를 사용하기도 함
