[자료구조] 해싱 (hashing)CSE/자료구조 (data structure)2022. 11. 25. 00:00
Table of Contents
반응형
해싱이란?
해싱(Hashing)은 키(key)에 산술적인 연산(해시 함수)을 적용해 항목이 저장되어 있는 테이블의 주소를 계산해 항목에 접근합니다.
- 해시 함수(hash function): 키를 입력으로 받아 해시 주소(hash address)를 생성
- 해시 테이블(Hash Table): 키에 대한 연산에 의해 직접 접근이 가능한 구조
- 해싱(Hashing): 해시 테이블을 이용한 탐색
해싱의 구조
탐색 키들의 문자열이나 매우 큰 숫자가 나오는 경우에 탐색 키를 직접 배열의 인덱스로 사용할 수는 없으니 작은 정수로 매핑(함수의 사상)시키는 어떤 함수가 필요합니다.
키값 $k$를 입력받아 해시 함수로 연산한 결과인 해시 주소 $h(k)$를 인덱스로 사용해 해시 테이블에 있는 항목에 접근합니다.
해시 테이블
- 버킷(bucket): 주소를 갖는 한 구역. 하나의 버킷은 여러 개의 슬롯을 가질 수 있음
- 슬롯(slot): 해시 주소를 담는 데이터 공간.
- 충돌(collision): 서로 다른 두 개 이상의 키들의 해시 주소가 같은 경우.
- 동의어(synonym): 충돌난 해시 주소들의 모임
- 오버플로우(overflow): 버킷에 더 이상 저장할 수 없게 되는 상황.
충돌이 발생하고 해시 주소에 더 이상 빈 버킷이 남아 있지 않으면 오버플로우가 발생합니다. 오버플로우를 해결하는 방법이 두 가지가 있습니다.
- 개방 주소법(open addressing): 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장
- 체이닝(chaining): 해시 테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시 테이블의 구조를 변경
728x90
반응형
'CSE > 자료구조 (data structure)' 카테고리의 다른 글
[자료구조] 개방 주소법 (open addressing) - 선형 조사법, 이차 조사법, 이중 해시법 (0) | 2022.11.27 |
---|---|
[자료구조] 해시 함수 (hash function) (0) | 2022.11.26 |
[자료구조] AVL 트리 (0) | 2022.11.22 |
[자료구조] 보간 탐색 (interpolation search) (0) | 2022.11.21 |
[자료구조] 색인 순차 탐색 (indexed sequential search) (0) | 2022.11.20 |
@junyeokk :: 나무보다 숲을
경북대학교에서 컴퓨터과학을 전공하고 있는 학부생입니다. 컴퓨터 전공 관련 내용들과 프론트엔드 개발 지식들을 공유합니다. React, Javascript를 다룰 줄 알며 요즘에는 Typescript에도 관심이 생겨 공부하고 있습니다. 서로 소통하면서 프로젝트 하는 것을 즐기며 많은 대외활동으로 개발 능력과 소프트 스킬을 다듬어나가고 있습니다.
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!