기록이 힘이다.

해싱 본문

자료구조

해싱

dev22 2022. 7. 11. 21:19
728x90

심볼 테이블(symbol table)
컴파일이나 인터프리터와 같은 언어 변환기에서 사용되는 자료구조

해싱 테이블(hashing table)
1. 데이터가 저장될 위치가 데이터의 값에 의해 결정되는 자료구조
2. 데이터가 저장되는 버킷(bucket)들의 배열로 만들어지며 한 버킷은 하나 이상의 레코드를 수용할 수 있음
3. 해싱 테이블에는 키(key)라는 인덱스로 자료를 접근하고 키와 배열 사이에서 해싱 함수를 이용하여 매핑(mapping)을 함

해싱 함수
1. 입력된 킷값을 해싱 테이블의 주소로 변환시켜주는 함수
2. 주어진 킷값으로부터 레코드가 저장되어 있는 주소를 직접 계산할 수 있도록 하는 수식
3. 키를 전달받아 키의 해시값을 반환하게 됨
4. 킷값을 해싱 함수에 넣어서 계산하면 해싱 테이블의 주소 값이 나오게 됨

해싱 함수의 대표적인 예
1 중간 제곱(mid-square) 함수
  킷값을 제곱한 후에 그 결과의 중간에 있는 적당한 수의 비트를 취하여 해싱 테이블의 버킷 주소로 만드는 방법
2 나누기(division-remainder) 함수
  나누기 함수는 해싱 함수로 나눗셈을 이용하는 방법으로 킷값을 해싱 테이블의 크기로 나누어서 그 나머지를 버킷 주소로 변환하는 방법
3 접지(folding) 함수
  종이를 접듯이 숫자를 접어 일정한 크기 이하의 수로 만드는 방법
   각 부분을 더하는 방식은 shift folding과 boundary foloding 방법이 있음

충돌(collision)
1. 해싱 테이블의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것으로 한 원소를 해싱해서 저장하려는데 다른 원소가 이미 그 자리를 차지한 상황
2. 해싱 함수를 통해 만들어진 해시 주소가 중복되면 데이터 값이 충돌함

오버플로우
더이상 슬롯에도 빈자리가 없는 경우

오버플로우 처리 기법
1. 개방 주소법(open addressing)
   해시 충돌이 발생하면 다른 버킷에 데이터를 삽입하는 방식
    선형 조사(linear probing)
    -가장 간단한 충돌 해결 방법으로 충돌이 일어난 바로 뒷자리를 보는 것
    -해시 충돌 시 다음 버킷, 혹은 몇 개 건너뛰어 데이터를 삽입함
    이차원 조사(quadratic probing)
    -충돌 시 바로 뒷자리를 보는 대신에 보폭을 이차 함수로 넓혀가면서 찾는 방법
    -이차원 조사는 선형 조사의 문제점을 해결하기 위한 방법이며 가능하면 충돌이 발생한 위치에서 먼 곳의 버킷에 저장되도록 함

2. 폐쇄 주소법(closed addressing) : 키에 대한 해시값에 대응되는 곳에만 키를 저장하는 충돌 해결 방법(대표적인 방법으로는 체이닝(chaining)이 있음)


<체이닝>
동일한 주소로 해싱된 모든 키들을 하나의 연결 리스트(linked list)로 저장하는 것

'자료구조' 카테고리의 다른 글

탐색과 정렬  (0) 2022.07.11
그래프  (0) 2022.07.06
트리  (0) 2022.06.17
연결리스트  (0) 2022.06.12
스택과 큐  (0) 2022.05.21