[Symbol Table]

컴퓨터 과학에서 심볼 테이블(symbol table)은 컴파일러나 인터프리터에서 사용되는 데이터 구조로, 프로그램 소스 코드에 사용된 각 식별자(또는 심볼, 언어 번역기에서 사용하는 심볼)에 그 선언이나 소스에서의 등장과 관련된 정보를 연결하여 저장한다.

-위키피디아-

 

심볼 테이블의 아이디어는 각 키마다 하나의 값을 연관짓는 것이다.

따라서 키-밸류 쌍의 추상화이다. 심볼 테이블의 ADT는 다음과 같다.

 

value는 null 값이 될 수 없으며 주어진 키를 통해 해당 키에 대응하는 값을 검색할 수 있다.

 

중복 키 문제 해결하기

사용자 정의 타입(user-defined types)을 비교하거나 해시 코드를 계산할 때의 표준 방법은 다음과 같다.

 

1. 참조 동등성에 대한 최적화

2. null 체크

3. 두 객체가 동일한 타입인지 확인하고 캐스팅

4. 중요한 필드 비교

 

best practices는 디음과 같다.

 

1. 계산된 필드를 사용할 필요가 없다.

2. 차이가 날 가능성이 높은 필드부터 비교한다.

3. compareTo를 equals와 일관되게 구현한다. 

 

Ordered ST

 

Ordered ST는 모든 키가 정렬된 배열을 유지한다. 또한 키가 연결된 인덱스를 찾기 위해 이진 탐색을 이용한다. 

Rank라는 헬퍼 함수가 존재하는데 k보다 작은 키가 얼마나 많은지 알려준다. 

 

삽입

rank()를 이용해 정확히 어디에 키를 업데이트 또는 삽입해야 할 지 결정 한다.

키를 새로 삽입 할 때는 삽입할 키보다 큰 키들을 한 칸씩 뒤로 밀어서 공간을 확보한다. 

탐색

rank()를 이용해 주어진 key보다 작은 key의 개수를 구한 후 key를 중간 키와 비교해 같으면 그 인덱스를 반환하고 아니면 null을 반환

floor, ceiling

floor는 key <= k 중 가장 큰 키 값이고, ceiling은 key >= k중 가장 작은 키 값이다.

성능

Unordered ST

연결리스트를 이용하며 검색할 때 전체 리스트를 순차적으로 따라가야하며 삽입할 때도 모든 키를 따라가야 하므로 비효율적이다.

성능 비교