[C언어] Hash

1. Hash Table의 Open addressing quadratic probing 방식
Hashing이란 자료 저장 및 열람을 위한 데이터구조 중 검색기능에 가장 특화된 구조이다. 이 때 검색을 위한 Key를 Hash Function을 이용해 숫자로 변환 후 Hash Table의 Entry에 저장하는데, open addressing이란 이 데이터를 저장하는 방식을 가리킨다. 이 방식은 그 data를 hash function을 이용해 변환시켜 할당된 공간이 비어있지 않을 경우 미리 정해놓은 함수의 계산을 통해 그 자리로부터 일정한 거리(숫자)만큼 이동하면서 다른 빈자리를 찾아가는 식이다. Quadratic probing은 F(i)=i2만큼 (즉, +1, +4, +9, +16, …)이동하는 방식을 말한다.

2. 설계 과정
Hashing에 관한 기본적인 code는 본문에 대부분 수록되어 있으므로 이를 상당부분 참고하였다. 책에서도 삭제는 고려하지 않았으나, 불필요하다고 판단되는 내부함수 몇 개는 포함시키지 않았다 (rehash(), retrieve() 등등). 헤더파일에 들어갈 내용은 본문과 거의 유사하다.
#ifndef_HashQuad_H

typedef unsigned intIndex;
typedefconst char* Name; //내부함수의변수 type으로쓰일 Name
typedefIndex Position;

structHashTbl;
typedefstructHashTbl *HashTable;

HashTableInitializeTable(Index Size);
Position Find(Name Key,HashTable H);
void Insert(Name Key,intw,intl,floatwr,HashTable H);

#endif
↑헤더파일 hash_header.h에 들어갈 code

그 다음은 구조체의 정의인데, 이 부분도 본문을 많이 참고했다. 이 과제에서는 Key로 쓰일 변수가 char형 변수이므로 변수형을 바꾸고 승, 패, 승률을 포함할 변수를 더 추가했다.