자료구조_검색 ⑥ 해싱 검색의 개요

 

 

[1] 해싱 검색

---

(1) 해싱검색 개요 

hashing 검색

해시함수를 사용하여 키를 고정된 길이의 해시값으로 매핑하고 해시값을 인덱스 , 메모리 주소 기반으로 데이터를 키와 함께 저장하는 자료구조  

순차적으로 데이터를 저장하지 않는다

value는 중복이 가능하지만 key는 중복 불가

기억장치를 직접 접근하고 연산에 의한 방식으로 데이터 주소를 찾는다 

key에 대한 자료를 검색한다 

연산에 의해 데이터의 기억공간을 찾는다

인덱싱 , 암호화 ,복호화 , 비교를 위해 사용한다. 

 

 

index = h(key) : 해시 함수가 key에 대한 인덱스를 반환해줌 해당 인덱스 위치에 자료를 저장하거나 검색하게 됨

 

키 key	input->	해시함수	ouput->	버킷
				해시값 (key)	value
kim				01	123-123
park				02	456-456
lee				03	789-789
min				04	123-123

 

해싱 : 키를 고정된 길이의 해쉬로 변경해주는 과정 

버킷 : 데이터가 저장되는 공간

해시함수 : 키를 고정된 길이의 해시로 변경해주는 역할

해시값 : 정수;  버킷의 크기로 나누고 나온 나머지를 버킷의 인덱스로 갖는다 

 

(2) 해싱함수 

주소를 데이터의 일부를 이용한 연산방법에 의해 찾는다 

중간 제곱(mid-square )	데이터를 제곱하여 같은 값이 발생되지 않을것을 예상되는 자릿수를 추출하여 주소로 이용한다  data =1234 , 제곱값 =1522756 이라면 1의자리 1 , 3의 자리 2 , 5의 자리 7 , 7의자리 6을 기억장치의 주소로 사용한다
제산 (나눈나머지 )	데이터를 특정값으로 나눈 나머지를 이용하여 주소로 이용한다  파일크기 = 1024 , 데이터 =12345678이라면 주소는 12345678%1024 =334를 기억장치 주소로 사용한다
승산(곱하기)	데이터 x 실수 = 결과의 소수점 이하 특정 자릿수를 선정하여 주소로 이용한다
접지(접기, folding)	접는방법 , 데이터의 개수를 분할하여 더한값을 주소로 이용한다  shift folding : 분할된 값의 끝을 기준으로 정렬하여 더한 값을 주소로 이용한다  boundary folding : 분할된 값은 자릿수를 기준으로 접어 구한 값의 합을 주소로 이용한다
계수분석	숫자의 자리 값을 비교하여 그 값의 특징에 따라 동일한 값이 빈번하게 발생하지 않을것으로 예상되는 자리를 지정하여  주소로 이용한다
진법(기수변환)	일반적으로 10진수를 가장 많이 쓴다고 가정할때 , 이수를 16진법으로 인식하여 다시 10진수로 변환하여 나온 값의 일부를 주소로 이용한다

 

(3) 해싱 충돌 

 

해싱충돌 : 해싱함수의 결과로 충돌이 발생할경우 동의어가 발생하며 , 이 갯수가 해싱테이블의 버킷의 개수를 초과할경우 충돌이 발생함 

int 32비트 정수형으로 모든 해시값을 담기는 부족하기 때문에 m개 배열을 사용하여 데이터 구현체를 관리한다

확률적으로 같은 공간(해시값)을 사용하게 되는데 이것이 해시 충돌이다 .

충돌이 일어날 확률이 적은 함수가 좋은 함수이며 , 충돌이 발생하더라도 대처가 가능한 구조로 만들어야한다 

 

영화관 좌석이 1번부터 100개 까지 있는데

영화표는 300개를 팔았다 

관객1번의 영화표가 125번이고 해싱함수를 이용하여 125 % 100 = 나머지 25가 나오면 25번 자리에 앉히자라고 함수를 만들었을때 

관객2번의 영화표가 225번이고 해싱함수를 이용하여 225 % 100 = 나머지 25가 나오면 해싱충돌로 인해 어떻게 앉아야할지 모를때 

비어있는 옆자리에 앉히면 126, 226번의 영화표를 가진 관객은 또 어디에 앉힐것인가 하는 충돌이 발생한다 

25 125 225 가 동이어 , 배열 로 이웃으로 만들어 관리한다 

 

 

 

(4) 해싱충돌 오버플로 해결방법 

선형
제곱
재해싱
오픈 어드레싱 open addressing	충돌이 일어나면 다른 비어있는 장소를 찾아 이동하여 저장하는 방법 a와 b가 125 으로같은 인덱스를 가질때 125 인덱스에 a가 들어가고 b가 들어갈수가 없자 126번으로 들어간다 126 인덱스를 가진 c는 버킷이 차있자 다른 인덱스를 찾아서 들어가고  이런 현상으로 인해 근처 버킷을 순회 데이터 갯수가 적을때 좋다
세퍼레이트 체이닝 separate chaining	하나의 저장소 위치에 다수의 값들을 저장할수 있도록 구현 방식  링크드리스트로 엮는다 데이터 갯수가 많을때 좋다