C# HashTable, Dictionary, Graph

장현태입니다·2025년 3월 31일

HashTable

hashtable은 key와 value로 구성

해시 : 뭉치는 과정 - 키를 입력해서 데이터를 받아오는것
테이블 : 배열의 크기가 저장된곳
해시 테이블: 크기가 지정된 테이블에 키를 입력해서 value를 가져오는것(탐색)
해시함수: 어떤 방법을 사용해서 index로 만들지
해시함수 조건 : 나하의 키값을 해싱하는경우 항상 똑같은 인덱스가 나와야함

ex) index가 테이블의 크기를 넘을경우
table =1000
해시함수 = 5678
index = 5678 %1000 = 678

해시테이블 주의점 -충돌
해시 함수가 서로 다른 입력값에 대해 동일한 해시테이블
주소를 반환하는것. 피할 수 없으니 추가적인 조치필요

충돌 해결방안 - 체이닝
해시 충돌이 발생하면 연결리스트로 데이터들을 연결
-> 추가적인 저장공간을 만들어줘야함

장점 : 자료 사용률에 따른 성능저하 작음
단점 : 해시테이블 외에 추가적 저장공간 필요

충돌 해결방안 - 개방주소법
다른 빈 공간에 데이터를 삽입하는 방식
-> 선형탐색, 제곱탐색, 이중해시를 사용하여 다른
빈공간 선정

장점 :추가적 저장공간이 필요없음,삽입 삭제시 오버헤드적음
단점 : 해시테이블에 자료사용률에 따른 서능저하
-> 데이터가 많을수록 성능저하

해시테이블 효율 - Capacity사용

해시테이블의 공간 사용률이 높을경우(70%이상) 성능저하
-> 재해싱을 통해 해시 테이블 크기를 늘리고, 테이블 내의 모든 데이터 다시 해싱

ex) 테이블크기 1000 -> 2000
해싱 1034, 2056 -> 34, 56
재해싱 1034, 2056 -> 1034, 56

해시테이블 시간 복잡도
접근 탐색 삭제 삽입
X O(1) O(1) O(1)

접근 없는이유 : 키로 값을 탐색하는 것이라 접근은 없음

삽입 -> 데이터가 많아질수록 테이블 크기가 커지고,
데이터가 많을시 효율 떨어짐
-> 빈번하게 삽입 삭제시 좋은 방법이 아님

이유 : 해시테이블에서 데이터 삭제시 해당 인덱스칸은
사용자체를 금지 시킨다 -> 재해싱을 통한것이 아니면
접근 불가능

C#에서 제공하는 HashTable -> Dictionary

Dictionary

hashtable의 재해싱, 탐색 등을 제공하는 자료구조
hashtable의 구조를 가지며, 하나의 키에 하나의 value를 가지는 특성을 유지한다 예시를 보면서 확인해보자

Dictionary는 재해싱을 자동으로 설정 해주기 때문에 capacity를 따로 설정 해주지 않아도 된다
Dictionary에서 제공하는 함수로 Add,TryAdd(시도해서 있으면 바꾸고 없으면 바꾸지 않는함수),Remove(있으면 true를 반환후 삭제 없으면 false). ContainsKey(키가 있으면 찾아주고 없으면 false), TryGetValue(키에 대한 값이 있으면 true 없으면 false)