해시(Hash)
각각의 이름(text)에 대해 유일한 Key값을 가지게 하는것이다.
해시에서 Key를 생성하기 위한 다양한 알고리즘이 존재한다. ( MD-5, SHA 등이 존재한다.)
Key를 주면 해싱 함수에 의해 해시코드로 변환되고, 해당 해시코드는 배열의 각 요소인 버킷이 인덱스 역할을 한다.
해당 버킷을 찾아가면 값을 삽입 및 조회할 수 있다.
apple이라는 문자열이 주어져있다고 가정해보자
Key를 만들기 위해 특정한 소수인 5381을 이용해보자
- Hash 값을 왼쪽으로 5번 비트 연산 시킨다.
- 원본 Hash값을 더한다.
- 한 문자의 ASCKII 값을 더한다
- 위의 결과를 모든 문자에 대해서 반복한다.
- 최종 값이 해시테이블의 범위를 벗어나면 나머지 연산을 취해준다.
Hash table의 최대 크기를 8191로 가정해보자
만들어진 Key의 위치에 자료를 삽입할 수 있다.
해시의 충돌
언젠가는 다른 문자열에 대해서 동일한 Key값이 발생할 수 있다.
서로 다른 원본에 대해서 동일한 Key 값을 가지게 되는 현상을 해시에서 충돌이 발생했다고 말한다.
충돌 해결 방법
충돌이 일어난 인덱스를 뛰어 넘어서, 빈 공간이 있는지 탐색 후 삽입 -> 개방 주소법
충돌이 일어난 지검을 사용하되, 연결 리스트로 묶는 방법 -> 체이닝(chaining)
개방 주소법의 경우, 인덱스만 증가시켜주면 되기 때문에 안정적인 방법이다.
chaining의 경우 정해진 해시 테이블 이외의 주소를 추가로 할당해서 확장해서 사용할 수 있다는 장점이 있다.
개방 주소법을 사용하여 구현하기
#include <iostream>
#define MAX_TABLE 8191
#define MAX_KEY 64
typedef long long ll;
using namespace std;
typedef struct Hash {
char key[MAX_KEY + 1];
int data;
} Hash;
Hash table[MAX_TABLE];
ll hashGen(char key[]) {
ll h = 5381;
while (*key != '\0')
h = (((h << 5) + h) + *key++) % MAX_TABLE;
return h;
}
int m_strcmp(const char* str1, const char* str2) {
while (*str1 != '\0' || *str2 != '\0') {
if (*str1 != *str2) return *str1 - *str2;
str1++; str2++;
}
return 0;
}
void m_strcpy(char dsc[], char src[]) {
while (*src != '\0')
*(dsc++) = *(src++);
}
int hashDelete(char key[]) {
ll h = hashGen(key);
int cnt = MAX_TABLE;
while (table[h].key[0] != 0 && cnt--) {
if (!m_strcmp(table[h].key, key)) {
table[h].key[0] = 0;
table[h].data = 0;
return 1;
}
h = (h + 1) % MAX_TABLE;
}
return 0;
}
int hashAdd(char key[], int data) {
ll h = hashGen(key);
int cnt = MAX_TABLE;
while (table[h].key[0] != 0 && cnt--) {
if (!m_strcmp(table[h].key, key)) {
table[h].data = data;
return 1;
}
else cout << "[충돌 발생]" << endl;
h = (h + 1) % MAX_TABLE;
}
if (cnt == -1) return 0;
m_strcpy(table[h].key, key);
table[h].data = data;
return 1;
}
int hashFind(char key[], int* data) {
ll h = hashGen(key);
int cnt = MAX_TABLE;
while (table[h].key[0] != 0 && cnt--) {
if (!m_strcmp(table[h].key, key)) {
*data = table[h].data;
return 1;
}
h = (h + 1) % MAX_TABLE;
}
return 0;
}
int main(void) {
while (true) {
char key[64];
int data;
char c;
cout << "[명령]\n1. 삽입\n2. 찾기\n3. 삭제\n4. 테이블 조회\n5. 종료\n→ ";
cin >> c;
switch (c) {
case '1':
cout << "[Key, Data 입력] ";
cin >> key >> data;
if (hashAdd(key, data)) cout << "[성공] 입력 완료\n";
else cout << "[실패] 해시가 가득 찼습니다."<< endl;
cout << "-----------------------------"<< endl;
break;
case '2':
cout << "[Key 입력] ";
cin >> key;
if (hashFind(key, &data)) cout << "[성공] " << data << endl;
else cout << "[실패] 존재하지 않는 데이터입니다." << endl;
cout << "-----------------------------" << endl;
break;
case '3':
cout << "[Key 입력] ";
cin >> key;
if (hashDelete(key)) cout << "[성공] 삭제되었습니다." << endl;
else cout << "[실패] 존재하지 않는 데이터입니다."<< endl;
cout << "-----------------------------" << endl;
break;
case '4':
for (int i = 0; i < MAX_TABLE; i++)
cout << "[" << i << "] " << table[i].key << ", " << table[i].data << endl;
cout << "-----------------------------"<< endl;
break;
case '5':
return 0;
default:
cout << "잘못 입력하였습니다." << endl;
cout << "-----------------------------" << endl;
continue;
}
}
return 0;
}
해시 맵(Hash Map)
- 키 기반의 빠른 엑세스 : 키를 사용하여 값을 빠르게 검색하거나 수정할 수 있다.
- 순서를 보장하지 않음 : HashMap은 내부적으로 키의 순서를 보장하지 않는다.
- 키의 중복 불가 : 같은 키를 중복해서 사용할 수 없다. 이미 존재하는 키에 대해 값을 저장하면 기존 값이 덮어씌워진다.
- null 키와 값 : Hash Map은 null 키와 null 값을 저장할 수 있다.
- 키 기반의 유연성 : 어떤 객체든 키로 사용할 수 있다.
데이터의 순서가 중요하지 않고 키를 기반으로 빠른 데이터 액세스가 필요할 때 사용하면 좋다.
해시맵은 해시 테이블의 한 구현체이며 JAVA에서 제공한다..
해시테이블은 보다 일반적인 자료 구조 원칙 또는 개념을 의미하며,
해시맵은 그 원칙을 구체적으로 구현한 특정 클래스나 자료구조를 의미한다.