심볼 테이블(Symbol Table) 자료구조의 이해와 구현

심볼 테이블은 키(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;
    }
}
정렬된 심볼 테이블은 데이터 삽입 시점에는 추가적인 비교 연산이 필요하지만, 범위 검색이나 최솟값/최댓값을 찾는 작업에서 무작위 심볼 테이블보다 훨씬 효율적입니다.

태그: SymbolTable DataStructure java LinkedList MapImplementation

10월 12일 05:36에 게시됨