맵(Map)

맵은 자료를 저장하고 키를 이용해 원라는 자료를 빠르게 찾을 수 있도록 하는 자료구조이자, 고유한 기를 기반으로 키-값 쌍으로 이루어져있는 정렬된 자료구조를 말한다. 이 중 트리 맵은 균형잡힌 이진탐색 트리인 레드 - 블랙트리로 구현된다.

트리맵의 구현방식

Tree Map : Key & Value가 Key값에 의해 정렬이 되는 Map (순서를 갖지 않음)

트리맵의 시간복잡도

• 참조:O(logn)
• 탐색:O(logn)
• 삽입/삭제:O(logn)

맵은 고유한 키를 갖기 때문에 하나의 키에 중복된 값이 들어갈 수없으며 자동으로 오름차순 정렬되기 때문에 넣은 순서대로 map을 탐색할 수 있는 것이 아닌 아스키코드 순으로 정렬된 값들을 기반으로 탐색하게 된다. 또한 대괄호 연산자 [] 로 해당 키로 직접 참조할 수 있다.
예를 들어서 "이승철" : 1, "김현영" : 2 이런식으로 string : int 형태로 값을 할당해야 할 때 map을 쓴다. 맵의 키와 value는 string이나 int 뿐만 아니라 다양한 값이 들어갈 수 있다.

셋(Set)

셋(set)은 고유한 요소만을 저장하는 자료구조로, 중복을 포함하지 않는 자료구조를 말한다. map처럼 {key, value}로 집어넣지 않아도 되며, 중복된 값은 제거되며 map과 같이 자동 정렬된다.

셋의 시간복잡도

• 참조:O(logn)
• 탐색:O(logn)
• 삽입/삭제:O(logn)

해시테이블(Hash Table)

해시 테이블은 큰범위를 가진 각양각색의 데이터들을 해싱을 통해 한정된 범위의 정수값을 가진 해시로 만들고 해시라는 키에 대응하여 원본 데이터들을 매핑시켜놓은 테이블을
말한다.

해시, 해싱, 해시함수??

해시란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값을 말한다.
해싱은 임의의 데이터를 해시로 바꿔주는 일을 하며 이를 해시함수가 담당한다,

위 사진을 보면 H(x)는 해시함수를 의미하며, 11%10, 12%10과 같은 식은 해싱을 의미하고, Hash table 위에 있는 주소값(0,1,2,3,4,5)가 해시를 의미한다.
일반적으로 해시테이블의 해시함수는 % 연산자가 들어가는 경우가 많다. 이를 통해 유한한 값의 키를 만들 수 있다.

해시테이블의 시간복잡도

평균시간복잡도

해시테이블은 최악의 시간복잡도와 평균시간 복잡도차이가 크며 이를고려해서 쓸지 말지를 고민해야 한다.
이 중 평균시간복잡도는 다음과같다.

• 참조:O(1)
• 탐색:O(1)
• 삽입/삭제:O(1)

최악의 시간복잡도

만약 해시테이블에서 충돌이 많이 일어난다면 해당 해시값이같은 모든 요소들을 탐색해야 하므로O(n)의 시간복잡도가 걸린다.

• 참조:O(n)
• 탐색:O(n)
• 삽입/삭제:O(n)

해싱 오버플로우

• 충돌(collision)
h(k1)=h(k2)인 경우 (k1≠k2일 때)
두개의 키 값에 대한 해싱 함수 결과가 같은 주소를 갖는 경우

• 오버플로우(overflow)
충돌이 슬롯 개수보다 많이 발생

해시테이블의 경우 범위를 크게 잡아도 거의 필연적으로 충돌이 많이 일어나게 된다. 아무리 범위를 넓게 설정을 하더라도 birthday paradox에 의해서 23명이 한 방에 있을 때 같은 생일을 가질 확률이 50%이기 때문에 크게 범위를 잡아도 충돌이 일어난다.
증명은 링크 참고
https://www.geeksforgeeks.org/birthday-paradox/
다만 충돌이 발생하면 해시테이블에 항목 저장이 불가능하기 때문에 해결하는 방법을 써서 그러한 충돌을 해결해야 한다.

해시테이블의 충돌문제 해결 방법

1. 체이닝

충돌 시 각 버킷에 삽입과 삭제가 용이한 연결리스트에 할당하고 충돌시 연결리스트를 탐색하는 기법을 말한다.
장점으로는 구현이 간단하며 해시테이블에 많은 데이터를 집어넣을 수 있지만, 단점으로는 연결리스트 기반이라 캐시성능이 좋지 않고, 체인이 길어지면 최악의 경우 O(n)이 될 수 있다.

해당 그림은 충돌 시에 연결리스틀를 사용한 체이닝 방식으로 충돌을 해결한 모습이다.

그리고 JAVA8이상에서는 요소의 수가 특정 임계값을 초과하면 연결리스트가 아닌 레트 블랙트리를 해쉬맵에 사용해서 시간복잡도를 O(log n)으로 개선했다고 알고 있다.
링크 참고
https://openjdk.org/jeps/180

2. 개방주소법(Open Addressing)

개방주소법(open addressing)은 충돌시 다른 버킷에 데이터를 삽입하는 기법을 말한다.
예로는 선형탐색,제곱탐색,이중해시방법이 있다.

1. 선형 탐색(Linear Probing)
해싱 함수로 구한 버킷에 빈 슬롯이 없으면 그 다음 버킷에 빈 슬롯이 있는지 조사(probing)하는 방법

ex) 충돌이 ht[k]에서 발생했다면,
1. ht[k+1]이 비어 있는지 조사
2. 만약 비어있지 않다면 ht[k+2]조사
3. 비어있는 공간이 나올 때까지 계속 조사
4. 테이블의 끝에 도달하게 되면 다시 테이블의 처음부터 조사
5. 조사를 시작했던 곳으로 다시 되돌아오게 되면 테이블이 가득 찬 것임
• 조사되는 위치: h(k), h(k)+1, h(k)+2,...

2. 제곱 탐색
해시충돌 시 1부터 연속적인 수를 만들며 해당 수의 제곱만큼 건너뛴 버킷에 데이터를 삽입하는 것을 말한다.

3. 이중 해싱
해시 충돌시 다른 해시함수를 한번 더 적용한 결과를 이용해서 데이터를 삽입한다.

우선순위 큐(Priority Queue)

우선순위 큐는 우선순위를 가진 항목들을 저장하는 큐를 말한다. 우선순위가 높은 데이터가 먼저 나가게 되면 가장 일반적인 큐라고 생각할 수 있다. 스택과 큐와 비교를 한다면 아래 표와 같다.

실제 그림을 본다면 아래와같다.

이 우선순위 큐는 최소 우선순위큐와 최대 우선순위 큐 2가지로 구분한다. 이 때 구현시에는 3가지 방법이 있다. 배열, 연결리스트, 힙을 이용한 구현인데 각자 시간 복잡도를 비교한다면 아래 표와 같다.