Week9_해시테이블_실습(2)

2. 개방주소법으로 정리하기

 

[HOW? by pseudo code]

Alg findElement(k)

    input bucket array A[0,..,M-1], hash function h, key k

    output element with key k

1. v<--h(k)

2. i <--0

3. while(i<M) 

     b<--getNextBucket(v, i)

     if(isEmpty(A[b]))

           return NoSuchKey

     elseif(k=key(A[b])

           return element(A[b])

     else

           i<--i+1

4. return NoSuckKey

 

Alg insertItem(k, e)

1. v<--h(k)

2. i<--0

3. while(i<M)

      b<--getNextBucket(v, i)

      if(isEmpty(A[b]))

          Set bucket A[b] to (k, e)

      else 

          i <--i+1

4. overflowException()

5. return

 

<--선형조사법-->

Alg getNextBucket(v, i)

1. return (v+i)%M

 

<--2차조사법-->

Alg getNextBucket(v, i)

1. return (v+i^2)%M

 

<--이중해싱-->

Alg getNextBucket(v, i)

1. return (v+i*h'(k))%M

 

Alg initBucketArray()

   input bucket array A[0,..,M-1]

   output bucket array A[0,...,M-1] initialized with null buckets

1. for i<--0 to M-1

         A[i].empty<--1

2. return

 

Alg isEmpty(b)

   input bucket b

   output boolean

1. return b.empty

 

---

 

 

STEP1) 변수 선언

int *hash, M; //해시테이블, 배열 크기 선언

STEP2) 해시 함수 & 조사 방식

int h(int x){
  return x % M;
}

int getNextBucket(int v, int i){
        return (v+i) % M; //선형조사법
}

int getNextBucket(int v, int i) {
	return (v + i*i) % M; //2차조사법
}

---

STEP2-1) 이중해싱인 경우

int* hashTable, M,n,q;

int h(int x) {
	return x % M;

}
int h2(int x) {
	return q - (x % q);
}

int getNextBucket(int v, int i, int k) {
	return (v + i*h2(k)%M) % M;

} 
//이중해싱

 

STEP3) 삽입

실습 2번 예시

void insertItem(int x) {
	int v = h(x, M);
	int i = 0,b;
	while (i < M) {
		b = getNextBucket(v, i); //다음 셀로 이동
		if (hash[b] == 0) { //비어있는 셀 발견
			hash[b] = x;

			for (int j = 0; j < i; j++) printf("C"); //충돌 발생
			printf("%d\n", b);
			return;
		}
		else {
			i += 1;
		}

	}
}

---

STEP3-1) 이중해싱 삽입 // 위와 동일

 

STEP4) 탐색

void searchItem(int x) {
	int v = h(x, M);
	int i = 0, b;
	while (i < M) {
		b = getNextBucket(v, i);
		if (hash[b] == 0) {
			printf("-1\n");
			return;
		}
		else if(hash[b]==x) {
			printf("%d %d\n", b, x); //주소와 키 출력
			return;
		}
		else {
			i += 1;
		}
	}
}

---

STEP4-1) 이중해싱 탐색

void searchItem(int k) {

	int v = h(k), i = 0, b;
	while (i < M) {

		b = getNextBucket(v, i,k);
		if (hashTable[b] == 0) {
			printf("-1\n");
			return;
		}

		else if (hashTable[b] == k) {
			printf("%d %d\n", b, hashTable[b]);
			return;

		}

		else i = i + 1;

	}
	printf("-1\n");

}

 

STEP5) 해시테이블 초기화 & main함수

int main() {
	int n, key;
	char ch;
	scanf("%d %d", &M, &n);
	hash = (int*)malloc(M*sizeof(int));
	for (int i = 0; i < M; i++) {
		hash[i] = 0; //0으로 초기화
	}
	while (1) {
		scanf("%c", &ch);
		
		if (ch == 'i') {
			scanf("%d", &key);
			getchar();
			insertItem(key);
		}
		else if (ch == 's') {
			scanf("%d", &key);
			getchar();
			searchItem(key);
		}
		else if (ch == 'e') {
			break;
		}
	}
	return 0;
}