심볼 테이블은 키(Key)와 값(Value)을 한 쌍으로 묶어 저장하는 추상 자료형입니다. 이 자료구조의 핵심은 특정 키를 통해 그에 대응하는 데이터를 효율적으로 찾아내는 데 있으며, 모든 키는 중복되지 않는 유일성을 가집니다.
실생활에서 심볼 테이블의 개념이 적용된 사례는 다음과 같습니다.
| 적용 분야 |
검색 목적 |
키(Key) |
값(Value) |
| 사전 |
단어의 의미 확인 |
단어 |
설명 및 정의 |
| 도서 색인 |
용어의 위치 파악 |
용어 |
페이지 번호 목록 |
| 웹 검색 엔진 |
키워드 관련 페이지 검색 |
검색어 |
웹 페이지 주소 |
심볼 테이블 API 설계
연결 리스트 기반의 심볼 테이블을 구현하기 위해 다음과 같은 구조를 설계합니다.
1. 노드(Entry) 클래스
- 필드:
key(데이터 식별자), value(연결된 데이터), next(다음 노드 참조)
- 생성자: 키, 값, 다음 노드 포인터를 인자로 받아 초기화
2. 심볼 테이블(LinkedMap) 클래스
void put(K key, V val): 새로운 키-값 쌍을 삽입하거나 기존 키의 값을 갱신
V get(K key): 키에 해당하는 값을 반환
void remove(K key): 특정 키를 가진 노드 삭제
int count(): 현재 저장된 요소의 총 개수 반환
기본 심볼 테이블 구현
아래 코드는 순서가 보장되지 않는 기본적인 심볼 테이블의 구현 예시입니다.
public class LinkedMap<K, V> {
private Node firstNode;
private int elementCount;
private class Node {
K key;
V val;
Node next;
public Node(K key, V val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
public LinkedMap() {
this.firstNode = new Node(null, null, null);
this.elementCount = 0;
}
public int count() {
return elementCount;
}
public void put(K key, V val) {
// 기존 키가 존재하는지 확인 후 값 업데이트
Node current = firstNode.next;
while (current != null) {
if (current.key.equals(key)) {
current.val = val;
return;
}
current = current.next;
}
// 존재하지 않는 경우 리스트 맨 앞에 새 노드 추가
Node newNode = new Node(key, val, firstNode.next);
firstNode.next = newNode;
elementCount++;
}
public V get(K key) {
Node current = firstNode.next;
while (current != null) {
if (current.key.equals(key)) {
return current.val;
}
current = current.next;
}
return null;
}
public void remove(K key) {
Node prev = firstNode;
while (prev.next != null) {
if (prev.next.key.equals(key)) {
prev.next = prev.next.next;
elementCount--;
return;
}
prev = prev.next;
}
}
}
정렬된 심볼 테이블(Ordered Symbol Table)
데이터를 저장할 때 키의 순서를 유지해야 하는 경우,
Comparable 인터페이스를 활용하여 키 값을 비교하고 적절한 위치에 삽입하는 방식을 사용합니다.
public class SortedLinkedMap<K extends Comparable<K>, V> {
private Node head;
private int size;
private class Node {
K key;
V value;
Node next;
public Node(K key, V value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
public SortedLinkedMap() {
this.head = new Node(null, null, null);
this.size = 0;
}
public void put(K key, V value) {
Node prev = head;
Node curr = head.next;
// 키를 비교하여 삽입될 적절한 위치 탐색
while (curr != null && key.compareTo(curr.key) > 0) {
prev = curr;
curr = curr.next;
}
// 이미 키가 존재하면 값만 갱신
if (curr != null && key.compareTo(curr.key) == 0) {
curr.value = value;
return;
}
// 새 노드 삽입
prev.next = new Node(key, value, curr);
size++;
}
public V get(K key) {
Node curr = head.next;
while (curr != null) {
if (curr.key.equals(key)) return curr.value;
// 정렬되어 있으므로 현재 키보다 작아지면 더 이상 찾을 필요 없음
if (key.compareTo(curr.key) < 0) break;
curr = curr.next;
}
return null;
}
public int getSize() {
return size;
}
}
정렬된 심볼 테이블은 데이터 삽입 시점에는 추가적인 비교 연산이 필요하지만, 범위 검색이나 최솟값/최댓값을 찾는 작업에서 무작위 심볼 테이블보다 훨씬 효율적입니다.