딕셔너리 (Dictionary <T>)
1. 해시테이블
: 키(key) 값(value)을 한쌍으로 저장하는 구조. 키를 기준으로 값을 저장하는 구조.
각 키는 해싱되어 값을 가리키는 고유한 식별자 역할
대부분의 경우 O(1)의 시간복잡도를 가짐
* 해시 : 임의의 길이를 가진 데이터를 '해시 알고리즘'을 사용해 고정된 길이를 가진 데이터로 출력한 값
1) 기본개념
(1) 키
- 데이터를 저장하고 찾기 위해 사용되는 고유한 식별자
- 해시함수를 거쳐 데이터를 보관할 수 있는 식별코드(해시코드)로 전환된다.
(2) 값
- 키를 기준으로 한 위치에 저장되는 데이터
- 키를 통해 값에 엑세스 할 수 있다.
(3) 해시함수
- 입력된 키를 해시테이블의 주소(해시코드)로 변환하는 함수
- 자료구조의 성능을 결정짓는 중요한 요소
- 보관하고자 하는 테이블의 크기 내의 결과를 출력
- 대표적인 방법으로 나눗셈법이 있음
(ex. 1581 % 1000 => 581 )
(ex2. "파이리" => 이진수 % 1000 = 221 )
2) 동작원리
: 키를 해시함수가 가공하고 해싱된 키를 배열에 삽입하는 구조
+ 만약 변환 후에 키가 충돌 된다면?
(ex. 나눗셈법의 1081 과 2081의 해싱값은 같음)
(1) 체이닝
- 해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식
- 장점 : 해시테이블의 자료사용률에 따른 성능저하가 적음
- 단점 : 해시테이블 외 추가적인 저장공간이 필요, 삽입삭제시 오버헤드가 발생
(2) 개방주소법 (C#에서는 이방법을 사용함)
- 해시 충돌이 발생하면 다른 빈 공간에 데이터를 삽입하는 방식
- 해시 충돌시 선형탐색, 제곱탐색, 이중해시 등을 통해 다른 빈 공간을 선정
- 장점 : 추가적인 저장공간이 필요하지 않음, 삽입삭제시 오버헤드가 적음
- 단점 : 해시테이블의 자료사용률에 따른 성능저하가 발생
< 해시테이블 효율 >
- 해시테이블의 공간 사용률이 높을 경우 (통계적으로 70% 이상) 급격한 성능저하가 발생
- 이런 경우 재해싱을 통개 공간 사용률을 낮추어 다시 효율을 확보함
- 재해싱 : 해시테이블의 크기를 늘리고 테이블 내의 모든 데이터를 다시 해싱하여 보관
2. 딕셔너리 (Dictionary<T>)
: 해시테이블 기반의 자료구조
키값을 통해 값을 찾을 수 있음
ex. Dictionary<string, Monster> monsterDic = new Dictionary<string, Monster>();
1) 삽입
- Dictionary.Add(Key, Value);
: 키 값에 값을 저장함. 이후 찾을 땐 Key를 통해 값을 찾을 수 있음
ex. monsterDic.Add("파이리", new Monster("파이리", Type.Fire...);
2) 삭제
- Dictionary.Remove(Key);
: 키 값을 통해 딕셔너리 내에서 키와 값을 삭제함
ex. monsterDic.Remove("파이리");
3) 탐색
- Dictionary[Key];
: 키 값으로 값을 찾아서 반환함
-> O(1)의 시간복잡도를 가짐
ex. Monster findMon = monsterDic["파이리"];
4) 확인
- Dictionary.ContainsKey(Key);
: 딕셔너리 내에 해당 키값 + 키에 대응하는 값이 존재하는지를 확인 후 bool 값 반환
ex. if(monsterDic.ContainsKey("파이리")) => true
** 틀리거나 제 공부에 도움을 줄 추가 정보를 알고계시다면 댓글로 알려주세요 **