1. 딕셔너리
1-1. Dictionary
- c#에서 Dictionary는 해시테이블로, key와 value로 이루어진 자료구조.
- 키 값을 해시함수로 해싱하여 해시테이블의 특정 위치로 직접 엑세스하도록 만든 방식.
- 해시: 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑
1-2. 해시테이블 구현
- 데이터를 담을 테이블을 이미 크게 확보.
- 입력받은 키를 해싱함수를 통해 해싱하여 테이블 고유한 index를 계산하고 데이터를 담아 보관.
- Entry배열에 Hash, next, Key, value 값을 가짐.
- Hash값이 bucket배열의 index를 가르킴.
- Bucket배열에서는 Entries배열 중에서 매칭되는 data의 index값을 가르킴.
1-3. 키 충돌
- 해시 함수가 서로 다른 입력 값에 대해 동일한 해시테이블 주소를 반환하는 것
- 모든 입력 값에 대해 고유한 해시 값을 만드는 것은 불가능하며 충돌은 피할 수 없음.
-> 해결방안으로 체이닝, 개방주소법 존재.
- c#에서는 Hash 충돌일어나면 배열을 순회하면서 Entries 빈자리에 data를 삽입.
- next값에 충돌이 일어난 index값 삽입.
- bucket에서는 매칭되는 data의 index값을 바꿔줌.
1-4. 체이닝
- 해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식.
- 장점: 해시테이블에 자료사용률에 따른 성능저하가 적음.
- 단점: 해시테이블 외 추가적인 저장공간 필요, 삽입삭제시 오버헤드가 발생.
1-5. 개방주소법
- 해시 충돌이 발생하면 다른 빈 공간에 데이터를 삽입하는 방식.
- 해시 충돌시 선형탐색, 제곱탐색, 이중해시 등을 통해 다른 빈 공간을 선정.
- 장점: 추가적인 저장공간이 필요x, 삽입삭제시 오버헤드가 적음
- 단점: 해시테이블에 자료 사용률에 따른 성능저하가 발생.
1-6. 재해싱
- c#에서는 개방주소법을 사용.
- 해시테이블의 공간 사용률이 높은 경우(70%이상) 급격한 성능저하가 발생.
-> 따라서, c#에서는 70%이상의 공간을 사용하는 경우 재해싱!
- 해시테이블의 크기를 늘리고 테이블 내의 모든 데이터를 다시 해싱하여 보관한다.
1-7. 시간복잡도
- 접근: x
- 탐색: O(1)
- 삽입: O(1)
- 삭제: O(1)
- 해시테이블의 탐색 삽입 삭제는 모두 O(1)이지만, 삽입과 삭제가 빈번하게 일어나는 경우 재해싱 과정이 일어나 공간사용률이 높아져 효율이 떨어진다.
1-8. 해시테이블 사용목적
- 해시테이블은 탐색을 목적으로 하고, 무의미하고 빈번한 삽입 삭제를 피하여 공간사용률을 늘리지 않는 상태로 탐색하는 방식을 선호.
-> 처음에 최대한 많이 삽입을 한상태에서 탐색하는 것은 좋지만, 중간에 삭제가 일어나고 삽입이 일어나고 반복하면 좋지 않음!
2. 인접행렬그래프와 인접리스트그래프
2-1. 인접행렬그래프
- 2차원 배열을 사용
- 장점: 인접 여부 접근 빠름 O(1)
- 단점: 메모리 사용량 많음 O(n^2) ex) 노드가 4개면 4x4이차원배열 필요.
2-2. 인접리스트그래프
- c#에서 리스트 사용
장점: 메모리 샤용량 적음 O(n)
단점: 인접 여부를 확인하기 위해 리스트 탐색필요 O(n)
개발노트