개요

• 집합은 데이터를 중복되지 않게 저장하는 추상 자료형이다.
• 맵은 키와 이에 연관되는 값을 함께 저장하는 추상 자료형으로 이때 키는 유일해야 한다.

• 맵은 연관 배열, 사전이라고도 함

• 중복된 데이터를 허용하는 자료형을 멀티셋, 멀티맵이라고 한다.
• 둘은 저장되는 타입만 다를 뿐 똑같기 때문에 구현하는 방식도 같다.
• 배열, 이진 검색 트리, 해시 테이블을 사용하게 된다.
• 배열과 이진 검색 트리는 이미 포스팅 했던 개념이므로 해시 테이블만 중점적으로 다루겠다.
  

해싱

• 배열은 모든 원소에 O(1)으로 접근할 수 있다.

• 인덱스만 알면 주소 연산을 할 수 있기 때문

• 룩업테이블처럼 어떤 데이터를 인덱스로 바꿀 수만 있다면 매우 유용하다.
• 모든 데이터가 정수 타입은 아니기 때문에 모든 데이터를 인덱스로 바꿀 수 없다.
• 어떤 타입의 데이터든 인덱스로 바꾸기 위해 해싱을 사용하는 것이 해시 테이블의 핵심이다.
• 해시 테이블은 캐시 친화적이지 않다는 단점이 있다.
• 해싱은 어떤 길이의 데이터든 입력의 크기에 상관 없이 일정 크기의 값으로 변환하는 것을 말하며, 이런 기능을 하는 함수를 해시 함수라고 한다.
• 해시 함수는 아래의 성질을 만족해야 한다.

1. 균일성 : 충돌이 발생할 확률이 낮은 것을 의미

• 충돌이란 서로 다른 입력에 대해 같은 해시 값이 생성된 것

2. 효율성 : 계산이 쉬운 것을 의미한다. (컴퓨터가 빠르게 처리 가능)

• 아무리 균일성이 높다고 해도 해시 값을 계산하는데 오래 걸린다면 효용성이 떨어짐

3. 결정적 : 같은 입력에 대해 같은 해시 값이 생성되는 걸 말한다.

• 해시 함수의 이런 특징 때문에 해시는 보안과 관련된 기술에 많이 사용된다.
• 디지털 서명, 공인인증서 등 우리 주변에서 흔히 볼 수 있다.
• 보통 해시 함수는 이미 구현된 것을 많이 사용한다.

• 가장 많이 쓰이는 것은 SHA-256, SHA-512 등

충돌 처리

• 해시 테이블에서 충돌은 피할 수 없다.
• 메모리 용량을 해시 값의 범위만큼 미리 확보해둘 수 없기 때문이다.
• 충돌을 처리하는 방법에는 2가지 방법이 있다.

1. 분리 연결법 : 분리 연결법은 충돌이 발생했을 때, 공간을 추가적으로 생성해 저장하는 방법
2. 개방 주소법 : 충돌이 발생했을 때, 해시 테이블 내 빈 공간을 찾아서 저장하는 방법으로 여기에는 선형 조사법, 2차 조사법, 이중 해싱 등이 있음
   
   

컬렉션

• C#에서는 HashSet과 Dictionary로 구현이 되어 있다.
• 사용법은 SortedSet과 SortedDictionary와 비슷하다.