'
용어 정의
해시함수 : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수. 균일하게 매핑할수록 좋은 해시함수이다.
해시 : 해시 함수에 얻어지는 값
해시 테이블 : 해시 값을 인덱스로 하여 데이터를 저장하고 있는 자료구조
Hashing
- 정의 : 데이터를 담을 해시 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시함수에 의해 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 과정
- 장점 : 데이터 접근 속도가 빠르다.
- 단점 : 충돌(collision)발생 - 서로 다른 입격 값에 대해 동일한 해시 테이블 주소를 반환하는 경우
- 해결법
- chaining : 충돌되는 데이터들을 해당 주소에 링크드 리스트로 연결
- open addressing : 충돌 발생시 해당 주소에 고정 폭 만큼을 더한 주소 값에 데이터 저장
- linear probing : 고정 폭의 값을 1로 설정하여 선형적으로 빈 주소를 탐색
- double hashing : 제 2의 해시함수의 값을 고정 폭의 값으로 설정하여 해시테이블 내의 클러스터를 방지
'Computer Science > algorithm' 카테고리의 다른 글
Graph, DFS, BFS, Dijkstra (0) | 2020.07.19 |
---|---|
Tree, Traversal, Binary Search Tree (0) | 2020.07.19 |
탐색1 : 선형탐색, 이진탐색 (0) | 2020.07.19 |
정렬3 : heap sort (0) | 2020.07.19 |
정렬2 : 분할정복을 이용한 정렬 (0) | 2020.07.19 |