📒 갈무리 - 해시테이블과 딕셔너리(Hashtable & Dictionary)

📌 해시테이블이란?

- key에 value가 매핑되는 방식으로 데이터를 저장하는 자료구조

- 각각의 key에 해시함수를 적용하여 배열의 고유한 index를 생성하고 버킷(Buckets)이라는 장소에 저장하게 된다.

- 해당 index를 활용하여 값을 저장하거나 검색하게 된다.

처리 순서 : key를 해시함수를 통해 해시코드 값으로 변경 -> 변경된 해시코드를 버킷(Buckets)이라는 저장공간 인덱스에 매핑 시켜서 값을 저장

- 같은 인덱스를 같게 되면 충돌이 발생함 (Hash Collision)

- .Net에서의 해시함수는 웬만해선 중복되지 않게 내부적으로 구현이 되어 있음

 

📌 충돌 해결 방법

Separate chaining : index에 접근했을 때 값이 이미 존재한다면 LinkedList로 값을 저장하고 해당 index의 다음 노드로 연결하는 방식

- 하나의 인덱스에 데이터가 몰려있는 경우 효율이 떨어지게 되지만 chaining 방식은 메모리를 미리 할당하지 않기 때문에 메모리 측면에서는 좋은 효율을 띄게 된다.

Open addressing : index에 충돌이 난다면 다음 index에 공간이 있는지 확인한 후 비어있다면 다음 index에 저장하는 방식

- 만약 Buckets이 가득 찬 경우에는 배열을 재생성 하고 key값과 value 값들을 다시 한번 해시함수를 통해서 재배열을 하게된다.

 

📌 .Net의 Hashtable과 Dictionary<T>

- Dictionary는 HashMap 또는 Map이라고도 함

- Hashtable은 Object 타입이기 때문에 내부적으로 박싱과 언박싱이 지속적으로 발생해 효율이 많이 떨어지게 된다. 그렇기 때문에 Hashtable 보다 Dictionary<T> 사용을 지향한다.

 

📌 특징

- 키를 가지고 빠르게 값에 접근하기 좋다

- 순서나 중복되는 데이터가 있는 경우에는 맞지 않다.

- 미리 저장공간을 확보하기 때문에 메모리 효율이 좋지 않다.

// C#
			Hashtable hash = new Hashtable(); // Hashtable 선언

            // Hashtable 초기화
            hash.Add(0, "liz"); // (key, value)
            hash.Add(1, "C#");
            hash.Add(2, "자료구조");
            hash.Add(3, "hashtable");

            Console.WriteLine(hash[0]); // index로 접근
            // liz

            Dictionary<string, string> dic = new Dictionary<string, string>(); // Dictionary 선언

			// Dictionary 초기화
            dic.Add("C#", "010-1234-5678"); // (key, value)
            dic.Add("C++", "010-0000-1111");
			// dic.Add("C#", "010-5678-0123"); // 오류!! key의 중복을 허용하지 않음
            
            foreach (var key in dic.Keys) // Dictionary의 모든 데이터 출력
            {
            	Console.WriteLine(key + " : " + dic[key]); // key 값으로 접근 
            }
            
            dic.ContainsKey("C#"); // "C#"이라는 키가 존재하는지 확인
            dic.Remove("C#"); // "C#"이라는 키의 데이터를 삭제