직접 주소 지정 테이블(Direct Addressing Table)은 각 요소가 전체 집합(universal set) S = {0, 1, ..., n−1}에서 추출된 키(key)를 가질 때 사용하는 자료구조입니다. 이때 n은 너무 크지 않아야 하며, 모든 키는 서로 중복되지 않는 고유한 값이어야 합니다.
이 자료구조의 가장 큰 장점은 키 값이 곧 배열의 인덱스라는 점입니다. 해시 함수나 별도의 탐색 과정 없이 키를 인덱스로 바로 사용하기 때문에 삽입(insert), 검색(search), 삭제(delete) 연산을 모두 O(1)의 시간 복잡도로 매우 빠르게 수행할 수 있습니다.
주요 함수 및 의사코드
직접 주소 지정 테이블의 기본 연산은 다음과 같은 의사코드로 표현할 수 있습니다.
Begin
insert():
테이블 변수 word와 key를 인자로 받는다.
T[ x.key ] = x (x는 저장할 데이터)
delete():
테이블 변수 word와 key를 인자로 받는다.
T[ x.key ] = tab(0, "") (해당 위치를 빈 상태로 초기화)
search():
T[key]를 반환한다.
End
C++ 전체 예제 코드
아래는 위의 개념을 C++로 실제 구현한 코드입니다. 메뉴 기반으로 동작하며, 요소의 삽입·삭제·검색을 반복적으로 수행할 수 있습니다.
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
using namespace std;
struct tab { // 테이블의 변수 선언
string word;
int key;
tab()
{}
tab( int k, string w ) // 변수를 초기화하는 생성자
{
word = w;
key = k;
}
};
void INSERT( tab T[], tab x ) {
T[ x.key ] = x;
}
void DELETE( tab T[], tab x ) {
T[ x.key ] = tab(0, "");
}
tab SEARCH( tab T[], int key ) {
return T[ key ];
}
int main() {
int i, k, c;
string str;
tab T[65536]; // 테이블 크기 초기화
tab x;
for(i = 0; i < 65536; i++)
T[i] = tab(0,"");
while (1) {
cout<<"1.Insert element into the key"<<endl;
cout<<"2.Delete element from the table"<<endl;
cout<<"3.Search element into the table"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your Choice: ";
cin>>c;
switch(c) {
case 1: {
string str1 = "";
cout<<"Enter the key value: ";
cin>>k;
cout<<"Enter the string to be inserted: ";
cin.ignore();
getline(cin, str);
INSERT(T, tab(k, str));
break;
}
case 2:
cout<<"Enter the key of element to be deleted: ";
cin>>k;
x = SEARCH(T, k);
DELETE(T, x);
break;
case 3:
cout<<"Enter the key of element to be searched: ";
cin>>k;
x = SEARCH(T, k);
if (x.key == 0) {
cout<<"No element inserted at the key"<<endl;
continue;
}
cout<<"Element at key "<<k<<" is-> ";
cout<<"\""<<x.word<<"\""<<endl;
break;
case 4:
exit(1);
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
코드 설명
- tab 구조체: 문자열(word)과 정수형 키(key)를 함께 저장하며, 생성자를 통해 값을 편리하게 초기화합니다.
- INSERT 함수: 입력받은 키를 배열 인덱스로 사용하여 해당 위치에 데이터를 바로 저장합니다.
- DELETE 함수: 해당 키 위치를 빈 값(tab(0, ""))으로 되돌려 삭제를 처리합니다.
- SEARCH 함수: 키에 해당하는 인덱스의 값을 즉시 반환하므로 탐색 비용이 전혀 들지 않습니다.
- main 함수: 크기 65536의 테이블을 미리 빈 상태로 초기화한 뒤, 무한 루프 안에서 메뉴를 출력하고 사용자의 선택에 따라 각 연산을 수행합니다.
실행 결과
1.Insert element into the key 2.Delete element from the table 3.Search element into the table 4.Exit Enter your Choice: 1 Enter the key value: 1 Enter the string to be inserted: hi 1.Insert element into the key 2.Delete element from the table 3.Search element into the table 4.Exit Enter your Choice: 1 Enter the key value: 2 Enter the string to be inserted: tutorials 1.Insert element into the key 2.Delete element from the table 3.Search element into the table 4.Exit Enter your Choice: 1 Enter the key value: 3 Enter the string to be inserted: point 1.Insert element into the key 2.Delete element from the table 3.Search element into the table 4.Exit Enter your Choice: 3 Enter the key of element to be searched: 1 Element at key 1 is-> "hi" 1.Insert element into the key 2.Delete element from the table 3.Search element into the table 4.Exit Enter your Choice: 3 Enter the key of element to be searched: 4 No element inserted at the key 1.Insert element into the key 2.Delete element from the table 3.Search element into the table 4.Exit Enter your Choice: 2 Enter the key of element to be deleted: 1 1.Insert element into the key 2.Delete element from the table 3.Search element into the table 4.Exit Enter your Choice: 3 Enter the key of element to be searched: 1 No element inserted at the key 1.Insert element into the key 2.Delete element from the table 3.Search element into the table 4.Exit Enter your Choice: 4
장단점 정리
장점
- 모든 연산이 O(1)로 실행되어 속도가 매우 빠릅니다.
- 구현이 단순하고 직관적입니다.
- 충돌(collision)이 발생하지 않습니다.
단점
- 키의 범위(n)가 클 경우 전체 테이블을 위해 많은 메모리가 낭비될 수 있습니다.
- 실제 저장되는 요소 수가 적으면 메모리 효율이 크게 떨어집니다.
따라서 직접 주소 지정 테이블은 키의 범위가 작고 밀집되어 있으며, 키가 고유한 경우에 가장 적합한 자료구조입니다. 키 범위가 넓거나 희소한 데이터에는 해시 테이블(hash table)과 같은 대안을 고려하는 것이 좋습니다.