[자료구조] 해시 [Hash]와 해시 테이블 [Hash Table]
해시 [Hash]
해시 함수(hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. 그 용도 중 하나는 해시 테이블이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어어 널리 사용된다. 해시 함수는 큰 파일에서 중복되는 레코드를 찾을 수 있기 때문에 데이터베이스 검색이나 테이블 검색의 속도를 가속할 수 있다.
저장된 키와 값을 이루는것을 테이블이라고 하는데 이중에 키에 해당하는 값을 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근하기가 용이하게 만드는 작업이라고 할 수 있습니다. (사전을 생각해보면 적당한 비유가 될 것 같습니다.)
즉 , 해시를 이용하면, 즉시 저장하고자 하는 위치나 찾고자 하는 위치를 쉽게 찾을 수 있게 됩니다.
(기존에 선형구조를 가지는 자료구조라면 탐색 시간이 O(n)이라는 시간이 소요되겠지만 테이블 자료구조의 탐색이 O(1)이기 떄문에
빠른 검색 및 삽입이 가능합니다.)
이런 구조를 Map , 또는 Dictionary라고도 합니다.(용어)
한 마디로, 공간과 시간을 교환하여 더 빠르게 사용할 수가 있습니다.
예를 들어서 "해시"라는 단어에 해시 함수를 적용해서 100이라는 색인이 생성되면, 리스트에 100번째 index에 해당 값을 저장하는 것 입니다.
[이미지 출처 : http://faculty.cs.niu.edu/]
해시 함수의 종류
| 이름 | 설명 | 특징 |
| 나눗셈 | 키 값이 정수 일때 이를 적당한 값으로 나누어 그 나머지를 사용하는 방식입니다. | 단순합니다. |
| 중간 제곱 | 키 값의 제곱에서 중간 자릿수를 선택하여 사용하는 방식입니다. | 아주 작은 적재율 일때는 좋은 성능을 보이나, 많은 충돌이 발생할 수 있습니다. |
| 폴딩 기법 | 키 전체를 균등한 크기로 나누고 , 이를 모두 더하거나 XOR 방식으로 사용하는 방식입니다. | 계산하기에 용이하지만, 불규칙적인 결과를 가져올 수 있습니다. |
| 기수 변환 | 어떠한 진법으로 표현된 키를 다른 진법으로 표현되었다고 가정하고 키를 변환하여 사용하는 방식입니다. | 계산 방법이 비교적 복잡합니다. |
| 자릿수 선택 | 키의 특정 위치에서 중복의 비율이 높거나, 공통으로 들어가는 값이 있다면, 이를 제외하고 나머지를 가지고 해시 값을 사용하는 방식입니다. | 모든 키 값들이 미리 알려진 상태에서만 사용이 가능합니다. |
그럼 배열을 사용하여 코드를 작성해보겠습니다.
struct User
{
int ID;
int Age;
char Name[10];
};
void main()
{
User userArray[1000];
User user;
cout << "ID와 나이 , 이름을 입력해주세요." << endl;
cin >> user.ID >> user.Age >> user.Name;
userArray[user.ID] = user;
cout << "ID = " << userArray[user.ID].ID << " 나이 = " <<
userArray[user.ID].ID << " 이름 = " << userArray[user.ID].Name << endl;
}
[결과]
유저의 ID를 고유 키값으로 사용하였고, 해당하는 키 값으로 바로 유저의 정보에 접근할 수 있었습니다.
다만, 이럴 경우 고유 식별 ID에 따라서 배열의 크기가 늘어나게 됩니다.
(실제로 고유의 값을 가지는 ID의 경우 이렇게 짧을 수가 없겠지요..)
그럼 임의의 값으로 나눈 해시 값을 가지는 구조로 코드를 작성해보겠습니다.
int MakeHashKey(int _id)
{
return _id * 0.01f;
}
struct User
{
int ID;
int Age;
User(int _id , int _age )
: ID(_id) , Age(_age) {}
void ShowUserData()
{
cout << "유저의 ID = " << ID << " 유저의 나이 = " << Age << endl;
}
};
User* MakeUserData(int _id, int _age)
{
return new User(_id, _age);
}
struct Data
{
int key;
User* value;
Data()
: key(0) , value(nullptr) {};
Data(int _key , User* const _value)
: key(_key) , value(_value){}
};
class HashTable
{
private :
Data data[100];
public :
HashTable() {};
User* Find(int _key)
{
if (_key <= 0)
{
return nullptr;
}
else if (data[MakeHashKey(_key)].value == nullptr)
{
cout << "데이터 없음." << endl;
return nullptr;
}
else
return data[MakeHashKey(_key)].value;
}
void Add(int _key, User* const _value)
{
int hashValue = MakeHashKey(_key);
Data newData;
newData.key = _key;
newData.value = _value;
this->data[hashValue] = newData;
}
void Remove(int _key)
{
int hashValue = MakeHashKey(_key);
if (data[hashValue].value != nullptr)
{
this->data[hashValue].key = NULL;
delete(data[hashValue].value);
data[hashValue].value = nullptr;
}
}
};
void main()
{
HashTable hashTable;
int id = 0;
int age = 0;
for (int i = 0; i < 1 ;i++)
{
cout << "아이디와 나이를 입력하세요." << endl;
cin >> id >> age;
hashTable.Add(id, MakeUserData(id, age));
}
cout << "검색할 아이디를 입력하세요." << endl;
cin >> id;
if (hashTable.Find(id) != nullptr)
hashTable.Find(id)->ShowUserData();
cout << "삭제할 아이디를 입력하세요." << endl;
cin >> id;
hashTable.Remove(id);
cout << "검색할 아이디를 입력하세요." << endl;
cin >> id;
if (hashTable.Find(id) != nullptr)
hashTable.Find(id)->ShowUserData();
[결과]
위에 구조로 그나마 해시를 사용하는 해시 테이블을 만들어본것 같습니다.
(작성하는 코드는 다 직접 작성하고 있으니 틀리면 말씀해주시길 ..)