해시(Hash)는 무엇인가? 간단한 해시 테이블 설명까지!

알고리즘 문제를 풀다보면 Hash(해시) 카테고리를 보기 마련이다. 또한 해시 개념은 암호학에서도 빈번히 등장한다.

여기서 해시가 무엇인지 정확히 짚고 넘어가도록 하자.

 

해시란?

임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다. 

이를 이용하면 데이터를 보다 더 쉽게 다루며 검색과 저장이 아주 빠르게 진행된다.

 

wikipedia

 

해시함수란?

• 임의의 길이의 문자열을 받아서 고정 문자열로 바꾸어주는 함수이다.
• 이때, 함수를 구현하는 방법에 따라서 서로 다른 임의의 문자열이 같은 고정 문자열로 되기도 하며 이러한 부분을 충돌이라고 한다. (H(s1)=H(s2))
• 함수에 넣고 나온 결괏값을 후에 인덱스로 사용한다.

 

//문자열을 받아서 정수로 반환하는 해시 함수의 예제

int hash(const char* str){
  int hash=401;
  int c;

    while(*str!='\0'){
    	hash=((hash<<4)+(int)(*str))%MAX_TABLE;
        str++;
    }
    
    return hash%MAX_TABLE;
 }

MAX_TABLE은 TABLE의 크기로 함수에 넣고 나온 결괏값을 후에 인덱스로 사용한다고 했기 때문에

인덱스 값에 들어갈 수 있게끔 %처리를 해주어야 한다.

 

 

 

해시테이블이란?

• 데이터를 검색할 때 사용할 key - 실제 데이터의 값 value를 한쌍으로 저장하는 자료구조이다.
• (ex>C++-map , python-dictionary)
• 데이터라 저장되는 곳을 버킷 또는 슬록이라고 한다. 
• 해시테이블의 기본 연산은 삽입insert, 삭제delete, 탐색search이다.

 

 

 

 

테이블을 구성 후 값을 찾는 것은 리스트를 사용하여 쭉 순회하는 방식으로 찾으면 된다. 삭제도 마찬가지이다.

 

또한, 해시테이블을 구성할 때 해시 충돌이 나면 Chaining or Open Addressing으로 해결해야한다.

 

 

 

Chaining

• 충돌이 일어날 경우 데이터들을 포인터를 이용한 Linked List(체인)형태로 연결하는 것
• key값을 포인터로 이어서 연결

 

Open Addressing

• 모든 데이터를 테이블에 저장하는 방법
• 사용하려는 테이블이 이미 사용중인 경우 다른 버킷을 사용
• Chaining과 다르게 포인터를 쓰지 않기 때문에 포인터로 인한 오버헤드를 방지할 수 있고, 테이블의 크기가 크지 않다면 효율적이나 크면 장점이 사라지게 됨

 

 

 

 

해시 코드 구현 (일부만 작성)

 

//function of string

void str_cpy(char *dest, const char* src){

	while(*src != '\0'){
    	*dest=*src;
        dest++;src++;
    }
    *dest='\0';
    
}


int str_cmp(const char* str1, const char* str2){


	while(*str1 != '\0' &&(*str1==*str2)){
    	str1++;
        str2++;
    }
    
    return *str1- *str2;

//문자열을 받아서 정수로 반환하는 해시 함수의 예제

int hash(const char* str){
	int hash=401;
    int c;
    
    while(*str!='\0'){
    	hash=((hash<<4)+(int)(*str))%MAX_TABLE;
        str++;
    }
    
    return hash%MAX_TABLE;
 }

 

 

//search

bool find(const char *key, int *val){
  int index=hash(key);
  Node* cur=tb[index];
    
    //리스트를 이용하여 하나씩 순회
    while(cur!=NULL){
    	if(str_cmp(cur->key,key)==0){
        	*val=cur->value;
            return true;
        }
        
    cur=cur->next;
    }
    
    return false;
    
 }

 

//delete

bool destroy(const char* key){
	int index=hash(key);
    
    //처음이 비어 있는지 확인
    if(tb[index]==NULL){
    	return false;
    }
    
    
    //첫번째.. 이전거를 현재에 갖고와서 삭제함
    if(str_cmp(tb[index]->key, key)==0){
    Node*first = tb[next];
    tb[index]=tb[index]->next;
    free(first);
    return true;
    }
    
    //나머지
    
    else{
    Node*cur = tb[index]->next;
    Node*prev=tb[index];
    
   while (cur != NULL && my_str_cmp(cur->key, key) != 0) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

		prev->next = cur->next;
		free(cur);
		return true;
	}
}

 

 

 

 

 

 

 

 

 

참고자료)

 

https://power-overwhelming.tistory.com/42

[자료구조/알고리즘] 해시(Hash) 란?

https://twpower.github.io/139-hash-table-implementation-in-cpp

[Algorithm] C/C++에서 해시 테이블(Hash Table) 구현하기

https://kgh940525.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%B4%EC%8B%B1Hashing-%EC%A0%95%EB%A6%AC%ED%95%98%EA%B8%B0

[알고리즘] 해싱(Hashing) 정리하기