symbol table
자료구조를 배우는데 있어서 중요한 개념 중 하나가 심볼 테이블(symbol table)입니다. 심볼 테이블은 키와 키 값을 일대일로 연관시켜주는 자료 구조로써, 여러 다양한 알고리즘에 쓰이고 있습니다. 대표적인 예시 중 하나가 주변에서 많이 볼 수 있는 사전입니다. 사전을 예로 들자면, 사전의 단어가 키가 되고, 그 단어의 의미가 키 값이 될 수 있습니다. 이렇게 단어와 의미를 일대일로 연관시키면, 나중에 단어의 의미를 찾을 때 쉽게 찾을 수 있죠. 사전 말고도 프로그래밍 언어로 작성된 프로그램을 어셈블리어 언어로 변환시켜주는 컴파일러도 심볼 테이블의 형식을 띠고 있습니다.
void put(Key key, Value val)먼저, 인자 값으로 key와 val를 주었는데, 그 타입이 Key,Value로 구체화되지 않았죠. 추상적인 타입을 줌으로써 나중에 사용자가 원하는 대로 타입을 정할 수 있게 한 겁니다. 여기에 대해서는 나중에 자세히 설명하겠습니다. 이 함수의 기능은 키와 키값을 심볼 테이블에 삽입하는 것입니다. 그리고, 만약 키 값에 null을 주게 되면, 그 키는 심볼 테이블에서 삭제됩니다. 또한, 만약 주어진 키가 이미 심볼 테이블에 존재하는 키라면, 그 이미 존재하는 키의 값은 새로운 값으로 대체됩니다. 정리하자면, 이 하나의 함수 안에 삽입, 삭제, 수정의 기능이 모두 들어가 있는 것이죠.
Value get(Key key)이 함수는 주어진 키의 값을 반환하는 역할을 합니다. 만약 주어진 키가 심볼 테이블에 존재하지 않는다면 이 함수는null값을 반환하게 됩니다.
void delete(Key key)이 함수는 키와 키 값을 심볼 테이블에서 삭제하는 기능을 합니다. 위에서 얘기했던 put 함수의 삭제기능과 결과적으론 같은 기능이지만, 방법론에선 완전히 다른 함수입니다. put의 경우엔 키 값은 null로 대체하는 것에 머물렀지만, delete은 키와 그 값을 아예 심볼 테이블에서 제외시켜버리는 함수입니다. 쉽게 얘기하면, put이 소극적인 반면, delete은 적극적인 거죠.
int size(); //테이블에 키와 그 값의 세트의 개수를 반환하는 함수입니다.boolean contains(Key key) //주어진 키가 테이블 내에 존재하는지 체크하는 함수입니다.boolean isEmpty(); //심볼 테이블 자체가 비어 있는 지 체크하는 함수입니다.Iterable<Key> keys(); //테이블에 존재하는 모든 키들을 순서대로 나열해주는 함수입니다.정렬된 심볼 테이블
기존의 심볼 테이블이 정렬없이 삽입하는 순서대로 그냥 나열되는 구조였다면, 정렬된 심볼 테이블은 문자 그대로 키를 삽입하는 순간 기존에 테이블에 존재하던 키들과 비교를 통해 정렬을 하는 구조입니다. 위에서 언급한 사전도 가나다 또는 abc순서로 정렬이 되어있죠.
여기서 특이점은 키를 서로 비교하기 위해 Comparable이라는 객체를 사용한다는 점입니다. 이 객체의 함수 compareTo()를 사용하여 키 두 개를 비교할 수 있죠. 이 정렬된 심볼 테이블엔 위에서 언급된 함수들 외에 새로 추가된 함수들이 있습니다.
Key max() //가장 큰 키를 반환
Key min() //가장 작은 키를 반환
Key floor(Key key) //주어진 키보다 작거나 같은 키들 중 가장 큰 키를 반환
Key ceiling(Key key) //주어진 키보다 크거나 같은 키들 중 가장 작은 키를 반환
int rank(Key key) //주어진 키보다 작은 키들의 개수를 반환
key select(int a) //주어진 a값의 위치에 존재하는 키를 반환(가장 작은 키는 0에 위치함)
void deleteMax() //가장 큰 키를 테이블에서 삭제
void deleteMin() //가장 작은 키를 테이블에서 삭제
int size(Key low, Key high) //주어진 두 키 사이의 키들을 순서대로 나열