해시테이블은 Bucket배열에 Key, Value Entry를 저장하고 인출하는 구조입니다. 해시테이블 클래스는 Bucket 배열을 기본 데이터 필드로 가집니다.
Chaining 방식으로 해시 충돌 문제를 해결하는 해시테이블에 대해 살펴볼 건데요,
해시테이블에서 자주 사용되는 주요 메서드는 아래와 같습니다.
1. Add(Key, Value) 메서드
해시테이블에 새로운 Key, Value 엔트리를 추가하는 메서드입니다. 입력된 Key를 해시함수를 사용해 Bucket 주소로 변환하면서 이 Bucket에 Key, Valuㄷ 엔트리를 추가합니다. 해당 Bucket 주소에 다른 엔트리가 있다면 Bucket의 엔트리 연결 리스트(Linked List) 앞부분에다가 새 엔트리를 넣습니다. 연결리스트의 마지막까지 이동하고 뒤에 추하는 것보다 휴욜성이 있습니다.
2. Get(Key) 메서드
해시테이블에서 입력된 Key에 상응하는 Value를 return 하는 메서드입니다. 입력된 Key를 해시함수를 사용하여 Bucket 주소로 변환하고 이 Bucket에 있는 연결 리스트에서 해당 Key를 갖는 Key, Value 엔트리를 검새하여 Value를 반환합니다.
3. Contains(key) 메서드
해시테이블에 입력된 Key가 존재하는지 체크하는 메서드입니다. 입력된 Key를 해시함수를 사용해 Bucket 주소로 변환하고 이 Bucket에 있는 연결리스트에서 해당 Key를 갖는 엔트리를 검색하여 없으면 false, 있으면 true로 반환합니다.
해시테이블의 Bucket 배열은 연결 리스트 노드들을 가리키는 배열이고, 생성자에서 임의의 Bucket 크기로 배열을 생성합니다. 연결 리스트 노드는 단일 연결 리스트 노드로서 Key, Value 와 다음 노드를 가리키는 Next 노드를 가지고 있습니다.
- .NET 해시테이블
.NET에서 해시테이블을 구현한 클래스는 Non-Generic Class 인 Hashtable Class, Generic Class인 Dictionary<Tkey, TValue> Class, multi thread 환경에서 해시테이블을 간편하게 사용할 수 있는 ConcurrentDictionary<TKey, TValue> Class 등 있습니다.
1. Hashtable Class
Non-Generic Class 인 Hashtable Class는 System.Collections name space 에 있는 클래스로 Key, Value 가 모두 object type 이고, Open Addressing 방식을 사용하는 해시테이블입니다. 일반적으로 Generic Class인 Dictionary<Tkey, TValue> Class를 사용할 것을 권장합니다.
2. Dictionary<Tkey, TValue> Class
Dictionary<Tkey, TValue> Class는 Generic 방식으로 구현한 해시테이블 클래스로 Key, Value Type을 객체 생성 시 사용자가 지정하게 됩니다. System.Collection.Generics name-space 안에 있고 Chaining 방식을 사용하는 해시테이블 클래스 입니다.
3. ConcurrentDictionary<TKey, TValue> Class
.NET 4.0부터 multi thread 환경에서 해시테이블을 편리하게 사용할 수 있는 새로운 클래스를 제공했습니다. System.Collection.Concurret name-space 안에 있고 multi thread 환경에서 데이터 핸들링 시 Lock을 사용하여 동시접근을 컨트롤 해야 될 때, ConcurrentDictionary<TKey, TValue> Class는 Locking 부분을 내부적으로 처리해줍니다.
