해싱

알고리즘 문제를 풀다가 해싱이 나와서 복습하는 차원에서 다시 공부해보았다.

 

산술 연산(해시함수)을 통하여 키 값에 직접 접근하는 방식이다.

 

탐색키를 입력받아서 산술연산을 통해 주소 생성

 

보통 2차원 배열로 구성

오버플로우==>즉, 저장하려고 하는데 슬롯이 가득찬 경우

1차원 배열로 구성하면 슬롯의 크기는 1임. ==> 충돌이 곧 오버플로우

 

고르게 분포하지 않으면 충돌이 많이 발생하기 때문에 고르게 분포해야함.

 

-폴딩: 세자릿 수 넘어가면 잘라서 3자릿수만 가져옴 (if, 5699면 ==> 699)

 

비트 추출만 이용하면 완전한 무작위성을 가질 수없기에 비트 추출방법과 중간 제곱 방법을

같이 사용하기도 한다.

 

크기를 줄이기 위해 슬롯의 크기를 줄이기 때문에 충돌과 오버플로우는 발생할 수 밖에 없다.

대부분은 1차원배열로 슬롯의 크기는 1 ==>즉, 충돌 해결하면 오버플로우도 해결'

 

선형조사법 : 충돌이 일어난 그 다음위치에 넣는 방법

군집화가 일어나면 순차탐색으로 자꾸 비교연산을 하기 때문에 시간이 많이 걸리게 된다.

 

선형조사법(스트링) - 문자열을 아스키코드로 10진수로 변환 3자리넘어가면 3자리만 추출