6/26 해시테이블, 해시셋, 딕셔너리

대규모 데이터에서 원하는 데이터를 빠르게 찾을 수 있도록 해주는 자료구조

해시테이블(HashTable)

키 값을 해시함수로 해싱하여 해시테이블의 특정 위치로 직접 액세스하도록 만든 방식

해시 : 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑

해시테이블은 기본적으로 배열 기반 자료구조이다.

Key의 해시값을 배열의 인덱스로 변환하여 데이터를 저장한다.

이때 해시테이블 내부 배열의 크기를 Capacity라고 하며,

저장된 데이터 수가 Capacity에 가까워질수록 충돌 가능성이 증가한다.

따라서 공간 사용률이 높아지면 더 큰 배열을 만들고 재해싱을 수행한다.

GetHashCode()

GetHashCode()는 object 클래스에 포함된 virtual 메서드이다.

사용자 정의 클래스에서 GetHashCode()를 오버라이딩하지 않으면, 기본적으로 객체의 필드 값이 아니라 참조 동일성을 기준으로 해시값이 생성된다.

즉, 내부 데이터가 같아도 new로 각각 만든 객체라면 서로 다른 Key로 취급될 수 있다.

참조형 타입을 Dictionary나 HashSet의 Key로 값 기준 비교하고 싶다면, Equals()와 GetHashCode()를 함께 오버라이딩해야 한다.

충돌 해결 방안 - 개방주소법

해시 충돌이 발생하면 다른 빈 공간에 데이터를 삽입하는 방식

해시 충돌시 선형탐색, 제곱탐색, 이중해시 등을 통해 다른 빈 공간을 선정

장점 : 추가적인 저장공간이 필요하지 않음, 삽입삭제시 오버헤드가 적음

단점 : 해시테이블에 자료사용률에 따른 성능저하가 발생

Linear probing : 충돌이 나도 해시 테이블 배열 내부의 다른 빈 칸을 찾아 넣는 방식입니다.

Chaining :충돌이 나면 테이블 내부의 다른 칸을 찾는 것이 아니라, 같은 인덱스에 데이터를 연결 리스트처럼 이어 붙이는 방식입니다.

해시테이블 효율

해시테이블의 공간 사용률이 높은 경우(통계적으로 70%이상 == 해시테이블 Capacity에 데이터가 70% 이상 사용되고 있는 경우) 급격한 성능 저하가 발생 → 따라서 해시테이블의 경우 권장 사용률은 50% 이하임.

→ 따라서 안정적인 성능을 위해 실제 저장할 데이터 수보다 여유 있는 Capacity를 설정하는 것이 좋으며, 개방주소법에서는 데이터 수의 약 2배 정도 크기를 확보해 부하율을 낮게 유지하는 방식도 사용된다.

이런 경우 재해싱을 통해 공간 사용률을 낮추어 다시 효율을 확보함

재해싱(Rehashing) : 해시테이블의 공간이 너무 많이 차서 충돌이 늘어났을 때, 더 큰 해시테이블을 새로 만들고 기존 데이터를 다시 넣는 과정

→ 재해싱이 발생하는 순간에는 모든 데이터를 다시 해싱해야 하므로 해당 삽입 연산의 비용이 일시적으로 O(N)까지 증가한다.

딕셔너리에 값을 추가할 때, Add를 쓰는게 국룰

→ Dictionary.Add(value), Dictionary[value] 둘 다 Dictionary에 값을 추가시키는 방법이다. 하지만 Add의 경우, 중복 확인까지 해주고, []는 기존 값을 변경시키므로 값을 추가할 때에는 Add를 쓰는 것이 일반적임

Dictionary.Remove를 해도 내부 Capacity가 즉시 줄어드는 것은 아니기 때문에 권장되지 않음

Dictionary는 접근이 아닌 탐색

HashSet

HashSet

중복을 허용하지 않는 집합 자료구조.

값의 해시값을 이용해 데이터를 저장하므로 Add, Remove, Contains가 평균적으로 O(1)에 동작한다.

List와 달리 순서가 보장되지 않으며, 인덱스로 접근할 수 없다.

주로 중복 제거, 빠른 존재 여부 확인, 방문 여부 체크 등에 사용된다.

Dictionary

Dictionary는 Key와 Value를 한 쌍으로 저장하는 자료구조이다.

Key를 해시 함수로 변환하여 내부 해시테이블의 특정 위치에 접근하기 때문에, Key를 통한 데이터 검색, 삽입, 삭제가 평균적으로 O(1)에 가깝다.

같은 Key는 중복 저장할 수 없으며, 하나의 Key는 하나의 Value와 매핑된다.

C#의 Dictionary<TKey, TValue>는 내부적으로 해시테이블 기반으로 구현되어 있으며, Key의 GetHashCode()와 Equals()를 이용해 저장 위치와 동일 여부를 판단한다.

객체지향

객체지향은 객체(Object) / 설계도(Class) / 실체(Instance) 로 구성된다.

객체(Object) - 개념 ex) 몬스터란? - 몬스터의 정보/행동

설계도(Class) - 객체의 정보와 행동을 정의하는 것 / 정보 : 필드, 행동 : 메서드 → 변수는 명사로,메서드는 동사로

실체(Instance) - 설계도(class)를 new 키워드를 통해서 만든 실제 물체가 인스턴스, 즉 실체임.