데이터 구조 및 알고리즘-해시 테이블

해시 테이블은 연관 방식으로 데이터를 저장하는 데이터 구조입니다. 해시 테이블에서 데이터는 배열 형식으로 저장되며 각 데이터 값에는 고유 한 인덱스 값이 있습니다. 원하는 데이터의 인덱스를 알면 데이터 액세스가 매우 빨라집니다.

따라서 데이터 크기에 관계없이 삽입 및 검색 작업이 매우 빠른 데이터 구조가됩니다. 해시 테이블은 배열을 저장 매체로 사용하고 해시 기법을 사용하여 요소가 삽입되거나 위치가 지정되는 인덱스를 생성합니다.

해싱

해싱은 키 값 범위를 배열의 인덱스 범위로 변환하는 기술입니다. 모듈로 연산자를 사용하여 키 값의 범위를 가져올 것입니다. 크기가 20 인 해시 테이블의 예를 고려하면 다음 항목이 저장됩니다. 항목이 (키, 값) 형식입니다.

• (1,20)
• (2,70)
• (42,80)
• (4,25)
• (12,44)
• (14,32)
• (17,11)
• (13,78)
• (37,98)

Sr. 아니.	키	해시시	배열 색인
1	1	1 % 20 = 1	1
2	2	2 % 20 = 2	2
삼	42	42 % 20 = 2	2
4	4	4 % 20 = 4	4
5	12	12 % 20 = 12	12
6	14	14 % 20 = 14	14
7	17	17 % 20 = 17	17
8	13	13 % 20 = 13	13
9	37	37 % 20 = 17	17

선형 프로빙

보시다시피 해싱 기술을 사용하여 이미 사용 된 배열 인덱스를 생성 할 수 있습니다. 이 경우 빈 셀을 찾을 때까지 다음 셀을 조사하여 배열의 다음 빈 위치를 검색 할 수 있습니다. 이 기술을 선형 프로빙이라고합니다.

Sr. 아니.	키	해시시	배열 색인	선형 프로빙 후 배열 인덱스
1	1	1 % 20 = 1	1	1
2	2	2 % 20 = 2	2	2
삼	42	42 % 20 = 2	2	삼
4	4	4 % 20 = 4	4	4
5	12	12 % 20 = 12	12	12
6	14	14 % 20 = 14	14	14
7	17	17 % 20 = 17	17	17
8	13	13 % 20 = 13	13	13
9	37	37 % 20 = 17	17	18

기본 작동

다음은 해시 테이블의 기본 기본 작업입니다.

• Search − 해시 테이블에서 요소를 검색합니다.

• Insert − 해시 테이블에 요소를 삽입합니다.

• delete − 해시 테이블에서 요소를 삭제합니다.

DataItem

해시 테이블에서 검색을 수행 할 기준으로 데이터와 키가있는 데이터 항목을 정의합니다.

struct DataItem {
   int data;
   int key;
};

해시 방법

데이터 항목 키의 해시 코드를 계산하는 해싱 방법을 정의합니다.

int hashCode(int key){
   return key % SIZE;
}

검색 작업

요소를 검색 할 때마다 전달 된 키의 해시 코드를 계산하고 해당 해시 코드를 배열의 인덱스로 사용하여 요소를 찾습니다. 계산 된 해시 코드에서 요소를 찾을 수없는 경우 선형 프로브를 사용하여 요소를 앞서 가져옵니다.

예

struct DataItem *search(int key) {
   //get the hash
   int hashIndex = hashCode(key);
	
   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
	
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
			
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;        
}

작업 삽입

요소를 삽입 할 때마다 전달 된 키의 해시 코드를 계산하고 해당 해시 코드를 배열의 인덱스로 사용하여 인덱스를 찾습니다. 계산 된 해시 코드에서 요소가 발견되면 빈 위치에 대해 선형 검색을 사용합니다.

예

void insert(int key,int data) {
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;     

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }
	
   hashArray[hashIndex] = item;        
}

작업 삭제

요소가 삭제 될 때마다 전달 된 키의 해시 코드를 계산하고 해당 해시 코드를 배열의 인덱스로 사용하여 인덱스를 찾습니다. 계산 된 해시 코드에서 요소를 찾을 수없는 경우 선형 프로빙을 사용하여 요소를 앞서 가져옵니다. 발견되면 해시 테이블의 성능을 그대로 유지하기 위해 더미 항목을 저장하십시오.

예

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL) {
	
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
			
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      } 
		
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }  
	
   return NULL;        
}

C 프로그래밍 언어의 해시 구현에 대해 알아 보려면 여기 를 클릭하십시오 .