[C언어] 자료구조 - Hash -오버플로우 처리 방법 및 기본 연산-2

 앞에서 오버플로우가 일어나는 원인을 알아보았다. 

 

자료가 들어가는 자리에 버킷이 겹칠 때, 또한 슬롯도 꽉 차있을 때 오버플로우가 생긴다고 했는데

 

그렇다면 다른 버킷은 비어있는데 어느 특정 버킷만 자꾸 나와서 오버플로우가 된 경우를 생각하자

 

200개 중에 자꾸 1개 버킷에만 몰려서 오버플로우가 발생하는데, 오버플로우를 막으려면 해시함수부터 수정해야한다.

 

해시함수를 잘못만들어서 테이블 전체를 골고루 활용하지 못하고 편중되게 사용하는 것이다. 

해시함수가 가져야 할 특징을 못가져서 그렇다.

 

해시함수가 가져야 할 특징

 

1. 충돌이 적어야함

2. 해시 테이블에 고르게 분포시킬 수 있는 주소의 연산 값이 나와야 한다.

3. 계산이 빨라야 한다.

 

아무튼 이러한 특징을 가지는 함수 중 가장 대표적인 것만 알아보자

 

제산 함수라는 해시함수가 있다.

나머지 연산자 mod 또는 %을 활용해서 만든다.

테이블의 크기가 M일 때 탐색키 k에 대하여 해시함수를 만든다면 이렇게 만든다.

 

h(k) = k & M 

 

M이 가능하면 소수(prime number)일 때 테이블에 골고루 분포된다고 한다.

이유는 나도 모르지만 소수의 세계는 신비하니까 ㅎㅎ

 

그렇다. 만약 해시함수도 적당히 잘 만들었는데도?? 오버플로우가 발생한다??? 그렇다면 어떻게 해야할까...

 

2가지 정도 방법이 있다.

 

1. 선형조사법(linear probing)

2. 체이닝(chaining)

 

선형조사법은 해시함수로 거쳐나온 주소값이 가리키는 버킷이 아닌 다른 곳에 저장하는 것이다.

쉽게 말하면 꽉차있으니까 다른 곳에 저장하는 것이다. 

피시방 꽉차면 옆 피시방 찾아다니듯이 ㅎㅎ  근데 막무가내로 집어넣으면 나중에 탐색할 때 다돌아봐야겠지...?ㅋㅋㅋㅋ

시간복잡도가 엄청 올라갈 수 있음 

 

체이닝은 슬롯의 개수가 정해져있으니까 !!! 꽉차는 거 아니냐? 그냥 이거 연결 리스트로 만들자!! 

그렇게 해서 테이블의 구조 자체를 바꿔서 저장하는 방법이다.

 

여기서 우선 기본연산을 알아보자 

선형조사법을 사용한 스크립트다.

그 중에서 1차 조사!!

 우선 문자열이 key값으로 들어왔을 때 문자열을 숫자로 바꿔주는 함수이다.

꼭 이렇게 할 필요는 없으며 나는 그냥 문자열의 아스키코드 전체의 합을 반환하는 함수로 만들었다.

그냥 수많은 예들 중 하나니까 너무 심각하게 받아들이지 ㄴㄴㄴ

 

얘가 바로 해시함수이고 제산함수를 이용해서 만들었다.

 

얘가 레코드이다. 2가지 이상의 필드를 가진 레코드 

저렇게 2차 매트릭스로 선언해야 버킷과 슬롯 둘다 만들 수 있다. 

 

입력하기전에 초기화 시키고 입력해야하니까 2차 매트릭스 모두 초기화를 시켜야한다.
그래서 for문 2번 들어가서 다 청소한다.

 

기본함수를 내가 분명 삽입 삭제 탐색 이라고 했지만,,, 출력이 필요한 이유는?? ㅋㅋㅋ써먹어야지 ㅋㅋㅋㅋㅋ 

 

아무튼 써먹으려면 저렇게 써먹을 수 있다. 초기화 하는 방법이랑 비슷하다. 다 뒤지면서 다 출력한다. 

 

 

내가 잘 짰는지는 모르겠는데,,, ㅋㅋㅋ 결과는 잘 나오더라 \0은 null 문자를 말하는 것이다. 참고바람

그리고 저기 i= (i+1) & TABLE_SIZE; 가 바로 오버플로우 처리를 위한 함수이다.

1차조사법이라고도 부른다. 

 

이것도 잘 짰는지는 모르겠다. ㅋㅋㅋㅋㅋ 근데 역시나 잘 돌더라.

 

메인함수 보여주려고 했는데,, 스샷찍기 너무 길어서

copy & paste 하겠다. 내 해시 테이블이 13*3 크기여서 오버플로우 좀 나게하려고 30개 정도 데이터를 넣었다.

 

void main()
{
init_map();
add_record("age", "A");
add_record("ant", "A");
add_record("allow", "A");
add_record("best","B");
add_record("beef","B");
add_record("bye","B");
add_record("creep", "C");
add_record("conscience", "C");
add_record("dirty", "D");
add_record("distinguish","D");
add_record("exam","E");
add_record("excellent","E");
add_record("fool", "F");
add_record("full", "F");
add_record("game", "G");
add_record("good","G");
add_record("great","G");
add_record("high","H");
add_record("hyperbolic", "H");
add_record("intelligent", "I");
add_record("ion", "I");
add_record("joker","J");
add_record("korea","K");
add_record("lemon","L");
add_record("monster", "M");
add_record("operation", "O");
add_record("queen", "Q");
add_record("rust","R");
add_record("special","S");
add_record("terrific","T");
print_map();
search_record("exam");
search_record("special");
search_record("high");
search_record("lemon");
search_record("terrific");
}

 

결과

 

ㅋㅋㅋㅋ 저 bar는 데이터가 들어가지 않으면 저따구로 나오기는 하는데,,, 아무튼 그렇다.. 디자인 잘못했더라

그래도 결과는 어찌저찌 나오더라.

 

 

체이닝은 다음 글에서 그냥 스크립트 전체를 복붙해야겠다. 비슷비슷하니까.