오늘은 딕셔너리에 대한 내용을 알아보겠습니다.
1. 🖥️ 해시테이블
키 값을 해시함수로 해싱하여 해시테이블의 특정 위치로 직접 엑세스하도록 만든 방식입니다.
즉, 해시함수를 사용하여 키를 해시 코드로 변환하고, 이를 인덱스로 사용하여 값을 저장합니다.
이 저장 된 키를 이용해서 검색을 빠르게 할 수 있도록 합니다.
해시한다? 인덱스로 저장한다? 이게 무슨 말이지???
쉽게 말한다면 도서관에서 책 정리 할 때 카테고리별로 정리한다면 빠르게 원하는 책을 볼 수 있잖아요?
마찬가지로 많은 데이터들을 보기 좋게 정리하면 빨리 찾을 수 있는 개념으로 이해하시면 됩니다.
이 때 데이터를 규칙성을 부여해서 더 찾기 쉽도록 넣어주도록 만들어주는 것이 해시함수입니다.
그 해시함수를 통해 정리된 표를 해시테이블이라고 합니다!
1-1 🔖 해시함수
해시함수의 규칙성은 여러가지가 있습니다만 대표적으로 많이 사용하는 것이 나눗셈법입니다.
2581 → (2581 % 1000) = 581
1674 → (1674 % 1000) = 674
이런 식으로 나머지를 이용하여 인덱스 1에는 1674, 인덱스 2에 2581을 넣는 거죠
| 1 | 2 | 3 | ... | 50 |
|---|---|---|---|---|
| 1674 | 2581 |
1-2 🔖 해시테이블
해시함수를 통해서 정리된 표가 해시테이블이라고 했었잖아요?
하지만 만약 나머지가 같은 경우에는 수가 다르지만 같은 인덱스에 배치되는 충돌이 발생할 수도 있습니다.
1581 → (1581 % 1000) = 581
2581 → (2581 % 1000) = 581
| 1 | 2 | 3 | ... | 50 |
|---|---|---|---|---|
| 1581 2581 |
1-2-1 ✔️ 체이닝
해시 충돌이 발생하는 경우 연결리스트로 데이터들을 연결하는 방식입니다.
| 1 | 2 | 3 | ... | 50 | ↔ | 50 | 51 |
|---|---|---|---|---|---|---|---|
| 1581 | ↔ | 2581 |
여기서 1581, 2581 따로 공간을 만들어서 연결하는 방식으로 충돌을 방지하는 방안입니다.
1-2-2 ✔️ 개방주소법
C#에서는 개방주소법을 채택하여 사용하고 있습니다.
해시 충돌이 발생하면 겹치지 않는 다른 빈 공간에 데이터를 삽입하는 방식입니다.
추가적인 저장공간이 필요하지 않고 삭제시 오버헤드가 적은 장점은 있지만
공간사용률이 높을수록 많은 성능저하가 발생할 수 있습니다.
| 1 | 2 | 3 | ... | 50 | 51 |
|---|---|---|---|---|---|
| 1581 | 2581 |
1-2-3 ✔️ 해시테이블 효율
앞에서 공간 사용률이 높을 경우에 급격한 성능저하가 발생한다고 했었는데
이런 경우 재해싱을 통해 공간 사용률을 낮출 수 있습니다.
재해싱은 해시테이블의 크기를 늘리고 테이블 내의 모든 데이터를 다시 해싱하여 보관하는 것입니다.
| 1 | 2 | 3 |
|---|---|---|
| 1674 | 2581 | 3896 |
여기서 재해싱을 통해 테이블 크기를 늘리고 이전 테이블 내의 모든 데이터를 다시 보관합니다.
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 1674 | 2581 | 3896 | 6541 |
1-2-4 ✔️ 해시테이블 시간복잡도
해시테이블 시간복잡도를 정리한다면
접근 X
탐색 O(1)
삽입 O(1)
삭제 O(1)
애초에 접근의 목적으로 사용하는 경우가 아니기 때문에 의미는 없고
여기서 삽입과 삭제의 경우 자주 사용할 경우 효율이 급격하게 떨어지기 때문에 주의해야 합니다.
Add, remove를 계속 사용하지 말자는 의미입니다.
2. 🖥️ Dictionary
앞에서 언급한 해시테이블의 개념을 사용하는 딕셔너리에 대해 알아봅시다.
딕셔너리는 많은 양의 데이터를 미리 저장해두고, 필요시 찾고 싶을 때 사용합니다.
public class Monster
{
public string name;
public int id;
public Monster(string name, int id)
{
this.name = name;
this.id = id;
}
}
static void Main(string[] args)
{
Dictionary<string, Monster> monsterDic = new Dictionary<string, Monster>();
// 추가 : 0(1)
monsterDic.Add("피카츄", new Monster("피카츄", 1));
monsterDic.Add("파이리", new Monster("파이리", 2));
monsterDic.Add("꼬북이", new Monster("꼬북이", 3));
monsterDic.Add("이상해씨", new Monster("이상해씨", 4));
// 하지만 동일한 Key값을 사용할 경우 오류가 생긴다.
// monsterDic.Add("피카츄", new Monster("다른몬스터", 5));
// 삭제 : 0(1)
monsterDic.Remove("피카츄");
// 탐색 : 0(1)
monsterDic.ContainsKey("파이리");
monsterDic.TryGetValue("파이리", out Monster monster); // 있으면 값을 내주고 없으면 Null
// 인덱서를 통한 간략한 사용 (확실히 있을 때 사용해야 됨)
Monster find = monsterDic["파이리"];
monsterDic["피카츄"] = new Monster("피카츄", 1);2-1 🔖 딕셔너리 기능 정리
2-1-1 ✔️ 호출
Dictionary<자료형, 클래스형> 객체명 = new Dictionary <자료형, 클래스형>()
Dictionary<string, Monster> monsterDic = new Dictionary<string, Monster>();2-1-2 ✔️ 추가
monsterDic.Add("피카츄", new Monster("피카츄", 1));
monsterDic.Add("파이리", new Monster("파이리", 2));
monsterDic.Add("꼬북이", new Monster("꼬북이", 3));
monsterDic.Add("이상해씨", new Monster("이상해씨", 4));2-1-3 ✔️ 삭제
monsterDic.Remove("피카츄");2-1-4 ✔️ 탐색
monsterDic.ContainsKey("파이리");
monsterDic.TryGetValue("파이리", out Monster monster);
// 만약 확실히 키 값이 있다고 확신할 수 있을 때 사용합니다.
Monster find = monsterDic["파이리"];
monsterDic["피카츄"] = new Monster("피카츄", 1);