Hash 자료구조란
- Key와 Value를 갖는 자료구조.
- 효율적인 검색을 위해 사용된다.
- 링크드리스트 같은 자료구조 처럼 처음부터 찾아 나감이 아닌 임의의 길이의 키값을 해시 함수 하여
해당 자료가 위치한 버킷의 주소값을 바로 알아내어 찾아갈 수 있다.
그림출처 - Wiki
용어
1. HASH 함수란
- 임의의 길이의 데이터를 고정길이의 데이터로 매핑하는 함수
- 아래의 그림을 보면 John Smith 를 해시 함수하여 02라는 해시값을 얻어낸 것을 볼 수 있다.
그림 출처 - https://preamtree.tistory.com/20
문제점 - *비둘기집 원리에 의해 해시함수의 결과값이 중복 될 수 있다. 이는 해시 충돌이라는 문제를 야기한다.
2. HASH란
- 해시 함수의 결과값으로 얻어지는 것으로 해시 값, 해시 코드, 체크섬, 해시 라고한다.
- 해시테이블 , 해시맵에 특정 자료가 저장되어있는 버킷의 키값으로 사용된다
3. Hash Table 이란
- 레코드를 한 개 이상 보관할 수 있는 버킷(Bucket)들로 구성된 기억공간
- 각버킷은 몇개의 슬롯으로 구성 되어 있다.
4. OverFlow란
- 여러개의 키값이 공통된 버킷을 가리키는 경우 버킷들의 공간은 유한하여 결국 버킷이 꽉차게 된다
이때 또하나의 키값이 해당 버킷에 매핑된다면 오버플로우가 발생한다.
- 간단히 말해 꽉찬 버킷에 또 다른 레코드를 저장하는 경우 발생한다.
5. 해시충돌(Hash Collision)이란
- 임의의 키값을 해시함수하여 같은 버킷을 가리키는 해시값이 출력되는것
- 다른 키값을 가진 레코드가 동일 버킷에 매핑되는 것
해시충돌과 OverFlow - http://galid1.tistory.com/170
'CS(Computer Science) > 자료구조' 카테고리의 다른 글
| 자료구조 - 이진 탐색 트리(Binary Search Tree)란 - 수정중 (0) | 2018.11.03 |
|---|---|
| 자료구조 - 트리(Tree)란 (1) | 2018.11.03 |
| 자료구조 - 해시 함수(Hash Collision)종류와 충돌 처리 방식 (0) | 2018.11.02 |
| 자료구조 - 단일 연결리스트(Linked List) (0) | 2018.10.07 |
| 자료구조 - 순차표현 연결표현 (0) | 2018.10.07 |
