Key-Value 자료구조
DAT(Direct Adress Table)는 데이터 값을 직접적으로 키 값(Index)으로 사용해 데이터 정보를 저장하는 구조인데,
이와 같은 방식은 데이터가 음수이거나 엄청 큰 수일 경우 활용할 수 없다는 단점이 있다.
이를 보완한 것이 Key-Value 자료구조이다. 내부 원리는 Hash 와 BST로 나뉘게 되는데 Hash를 먼저 직접 구현해볼 것이다.
Hash-Table은 요소 값을 Key(Index)로 바로 사용하는 것이 아닌, HashFunction을 거쳐 만들어진 HashCode를 바탕으로 새로운 Key를 만들어 Bucket에 요소를 배치한다. 이때 요소들은 특정한 순서로 정렬되지 않는다.
동일한 HashCode를 가진 요소는 동일한 Bucket에 저장되며, 이로인해 요소를 검색, 삽입, 제거 시에 정확한 Bucket에 빠르게 엑세스할 수 있다.
참고로 뒤에서 언급할 <unordered_map>은 Hash-Table 구조이고, <map>은 BST(Binary Search Tree) 이진 검색 트리 (정확히는 Red-Black Tree라고 한다)구조이다.
둘 다 동일하게 여러 데이터를 저장하고 빠르게 찾는 것은 동일하지만 Hash-Table은 정렬 되어있지 않지만 빠른 탐색(평균적으로 O(1) )이 가능하고, BST는 Key 값에 따라 자동으로 정렬해주기 때문에 순서가 중요할 때 사용된다.(삽입, 삭제, 탐색 모두 O(log N) 의 시간복잡도를 가진다)
Hash-Table
*Hash-Table 내부 구조를 직접 구현 (인접리스트 chaining방식)
#include <iostream>
using namespace std;
struct Node
{
int Key;
int Value;
Node* Next;
};
Node* Bucket[4];
Node* Last[4];
int KeyList[] = { 6,9,32,10000,15 };
// Key값을 임의로 HashCode로 만들어 반환
int HashFunction(int Key)
{
int HashCode = Key % 3;
return HashCode;
}
// 인접리스트에 데이터 저장
void AddNode(int HashCode, int Value, int Key)
{
if (Bucket[HashCode] == NULL)
{
Bucket[HashCode] = new Node();
Bucket[HashCode]->Key = Key;
Bucket[HashCode]->Value = Value;
Last[HashCode] = Bucket[HashCode];
}
else
{
Last[HashCode]->Next = new Node();
Last[HashCode] = Last[HashCode]->Next;
Last[HashCode]->Key = Key;
Last[HashCode]->Value = Value;
}
}
// 인접리스트에서 변환된 HashCode값에 데이터가 있다면 삭제
void DeleteNode(int Key)
{
int HashCode = HashFunction(Key);
Node* PreviousNode = Bucket[HashCode];
Node* CurrentNode = Bucket[HashCode]->Next;
// 첫 번째 노드가 삭제 대상인지 확인 후 맞다면 삭제
if (Bucket[HashCode]->Key == Key)
{
Bucket[HashCode] = Bucket[HashCode]->Next;
return;
}
// 리스트 순회하며 타겟 삭제
while (CurrentNode)
{
if (CurrentNode->Key == Key)
{
PreviousNode->Next = CurrentNode->Next;
delete CurrentNode;
return;
}
// Previous와 Current노드 한 칸씩 앞으로 이동
CurrentNode = CurrentNode->Next;
PreviousNode = PreviousNode->Next;
}
}
// HashCode로 변환한 뒤, 인접리스트 형태로 저장
void Push(int Key, int Value)
{
int HashCode = HashFunction(Key);
AddNode(HashCode, Value, Key);
}
// HashCode 데이터로 Bucket 순회하며 같은 HashCode 값을 찾아 Value 반환
int GetValue(int Target)
{
int HashCode = HashFunction(Target);
for (Node* p = Bucket[HashCode]; p != NULL; p = p->Next)
{
if (p->Key == Target) return p->Value;
}
return NULL;
}
int main()
{
for (int i = 0; i < 5; i++)
{
Push(KeyList[i], 1);
}
DeleteNode(6);
Push(7, 1);
return 0;
}
1. KeyList에 있는 값 전체를 Bucket에 저장
2. DeleteNode로 6의 값 삭제
3. 7의 값 추가
unordered_map
*String 형태의 Input이 주어졌을 때, 각 글자가 몇 개 있는지 반환하는 알고리즘
#include <iostream>
#include <unordered_map>
using namespace std;
// string을 input으로 받아, unordered_map 컨테이너에 저장하고 이를 반환
unordered_map<char, int> Calculate(string InputStr)
{
unordered_map<char, int> CountChar;
//string을 글자 하나하나 순회하며 탐색
for (int i = 0; i < InputStr.size(); ++i)
{
// CountChar에 해당 글자가 존재하면 Value값 증가
if (CountChar.find(InputStr[i]) != CountChar.end())
{
CountChar[InputStr[i]]++;
}
// CountChar에 해당 글자가 없다면 Value에 1 저장
else
{
CountChar[InputStr[i]] = 1;
}
}
return CountChar;
}
int main()
{
string InputStr = "spartan";
auto Result = Calculate(InputStr);
for (const auto& Pair : Result)
{
cout << Pair.first << " : " << Pair.second << endl;
}
return 0;
}
map
STL 컨테이터 <map>은 BST 자료구조를 가지고 있다.
<unordered_map> 과 같이 Key-Value 자료구조이지만 Value의 값을 정렬하여 저장한다는 특징을 가지고 있다.
BST 삽입 규칙:
- 새로 삽입할 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로 이동
- 새로 삽입할 값이 현재 노드의 값보다 크면 오른쪽 서브트리로 이동
- 적절한 자리가 비어있으면 새 값을 해당 자리에 삽입
중위 순회(In-Order Traversal) 과정
- 왼쪽 서브트리 방문: 제일 왼쪽으로 내려가며 서브트리 탐색
- 현재 노드 방문: 가운데 현재 노드 탐색
- 오른쪽 서브트리 방문: 오른쪽으로 이동해 서브트리 탐색
*Vector 의 데이터를 정렬하여 몇 개인지 세어주는 알고리즘
#include <iostream>
#include <map>
#include <vector>
using namespace std;
map<int, int> BST(vector<int> NumList)
{
map<int, int> SortedMap;
for (int Num : NumList)
{
SortedMap[Num]++;
}
return SortedMap;
}
int main()
{
vector<int> NumList = { 15,7,3,4,1,9 };
auto Result = BST(NumList);
for (const auto& Pair : Result)
{
cout << Pair.first << " : " << Pair.second << endl;
}
return 0;
}
출력 했을 때, 값이 정렬된 상태에서 빈도 수가 저장되어 있는 것을 확인할 수있다.