(C#) Dictionary 와 Hash Table

동영상 강좌

Dictionary와 Hash 동일 특징

• 키와 값을 한쌍으로 저장하는 자료구조
• 대부분 삽입,삭제,읽기,검색 연산이 O(1)로 빠르다
• Key는 Hash Function(해시함수)를 통해서 Hashing되어 HashCode가 되고, HashCode는 주소값의 몇번째 Index가 될지 결정. 해당 배열의 주소값의 index번째에 Key와 Value값을 저장한다
  Key -> HashCode (by Hash Function) -> 주소의 HashCode번째에 KeyValuePair저장
• 변환된 키값(HashCode)가 중복된다면?
  ->체이닝, 개방주소법 등 으로 중복된 키값을 처리한다 (동영상참조)

Dictionary

사전 이라는 뜻
Key값을 주면 해당하는 Value가 반환됨
Key값은 중복되지않음. 추가전 .ContainsKey로 확인후 안전하게 추가가능
사용할 타입을 미리 정의하기 때문에 박싱,언박싱 일어나지않음(장점)

코드

class Program
{
    static void Main(string[] args)
    {
        Dictionary<string, int> itemAmount = new Dictionary<string, int>();
        itemAmount.Add("파괴폭탄", 12); //키와 값을 세트로
        itemAmount.Add("회오리수류탄", 18);

        if (itemAmount.ContainsKey("신호탄") == false) //안전하게
        {
            itemAmount.Add("신호탄", 32);
        }
        Console.WriteLine(itemAmount["회오리수류탄"]); //18출력
        itemAmount["회오리수류탄"] = 15; //값수정 가능
        Console.WriteLine("--구분--");

        foreach (var a in itemAmount) //모든 Key와 Value 출력하기
        {
            Console.WriteLine($"{a.Key}에 대한 밸류값은 {a.Value}"); //예시출력) 파괴폭탄에 대한 밸류값은 12
        }
    }
}

자료구조 2개 묶기 (Dictionary + List)

Dictionary 안에 List를 넣은 형태

class GameObject
{
    public string Name { get; set; }
}
class Enemy : GameObject
{
}
class Ally : GameObject
{
}
class Program
{
    static void Main(string[] args)
    {
        Dictionary<string, List<GameObject>> inGameCharacters = new Dictionary<string, List<GameObject>>();
        List<GameObject> playerUnits = new List<GameObject>();
        playerUnits.Add(new Ally { Name = "아군1" });
        playerUnits.Add(new Ally { Name = "아군2" });

        List<GameObject> enemyUnits = new List<GameObject>();
        enemyUnits.Add(new Enemy { Name = "적군1" });
        enemyUnits.Add(new Enemy { Name = "적군2" });

        inGameCharacters.Add("적군모음", enemyUnits);
        inGameCharacters.Add("아군모음", playerUnits);

        inGameCharacters["적군모음"].Add(new Enemy { Name = "적군3" });
        inGameCharacters.Add("중립모음", new List<GameObject>());
    }
}

Hash Table(해시테이블)

C#에서는 Dictionary로 구현되어 사용하면 된다.
Dictionary와 다르게 모든 데이터가 들어감 (Object형)
Object의 단점인 박싱언박싱, 언박싱 시도시 안전하지못한 형변환으로인해 프로그램 비정상 종료 가능성 존재
데이터를 빠르게 찾기 위해 특정 규칙(해쉬함수)에 따라 숫자(위치)를 반환

Hashtable hashtable = new Hashtable();
hashtable.Add("id", 12);
hashtable["name"] = "홍길동";
hashtable["score"] = 95;

키 충돌

동영상에 더 자세히 나와있다.
만약 키를 해시함수로 변환시킨 값이 충돌(중복) 되었다면?

1. 체이닝(Chaining)
겹치는 곳의 배열의 원소에 연결 리스트로 구현해서 같은 키값의 데이터 보관

2. 개방주소법(Open Address) : 선형탐사(Linear Probing)
배열을 지정된 폭만큼 순회하면서 빈공간에 바로 할당

3. 개방주소법(Open Address) : 제곱탐사(Quadractic Probing)
충돌발생시 첫번째에는 1의 2제곱, 2의2제곱, 3의2제곱 순으로 폭을 늘리며 해당 공간에 저장

4. 개방주소법(Open Address) : 이중 해싱(Double Hashing Probing)
충돌된 해싱값을 다시 한번 해싱함수를 통해 해싱
충돌이 일어나지 않을때까지 반복