C/C++ HASH의 구현.

해싱(Hashing)
테이블제 저장된 데어트를 주어진 Key(input) 값을 수학적 계산을 통해 원하는 데이터를 탐색하는 방법.

 

해싱 테이블(Hashing Table)
데이터를 저장 수 있는 버킷(Buket)으로 구성.

 

아래는 오픈어드레싱(open addressing) 방식의 예제다.

해쉬 인덱스의 계산

const int MOD = 100007;
const int D = 31;

int hashing(char* str)
{
	int hashValue = 0;
	int s = 1;

	for (int i = 0; str[i] != NULL; ++i)
	{
		hashValue = (hashValue + str[i] * s) % MOD;
		s = s * D % MOD;
	}

	return hashValue;
}

해쉬 테이블의 정의

// const int MOD = 100007;

struct Buket {
	char str[11];		// 키
	int data;			// Data
};

Buket hashtable[MOD];

삽입

int insert(char *str)
{
	int hash_idx = hashing(str);

	for (int i = 0; i < MOD; ++i)
	{
		if (hash_idx == MOD)
			hash_idx = 0;

		if (hashtable[hash_idx].str[0] == '\0')
		{
			mstrcpy(hashtable[hash_idx].str, str);
			return hash_idx;
		}
		if (mstrcmp(hashtable[hash_idx].str, str) == 0)
		{
			return hash_idx;
		}

		hash_idx++;
	}
	return 0;
}

탐색

int search(char* str)  // has
{
	int hash_idx = hashing(str);

	for (int i = 0; i < MOD; ++i)
	{
		if (hash_idx == MOD)
			hash_idx = 0;

		if (mstrcmp(hashtable[hash_idx].str, str) == 0)
		{
			return hash_idx;
		}

		hash_idx++;
	}
	return -1;
}

삭제

void remove(char* str)
{
	int hash_idx = hashing(str);

	for (int i = 0; i < MOD; ++i)
	{
		if (hash_idx == MOD)
			hash_idx = 0;

		if (mstrcmp(hashtable[hash_idx].str, str) == 0)
		{
			hashtable[hash_idx].str[0] = 0;
			return;
		}

		hash_idx++;
	}
}