[자료구조의 심화]

우선순위 큐(Priority Queue)와 힙(heap)

큐 자료 구조는 선입 선출 구조를 가지고 있었다. 우선 순위는  먼저 들어간 데이터 인 것이다.

그렇다면 우선 순위가 바꿀 수 있을까 ? YES!  그것이 바로 우선 순위 큐 이다.

 즉,  다른 우선 순위를 부여하여  우선순위에 맞는 데이터를 먼저 꺼내는 것이다.

 

 

힙 

최댓값 최솟값을 빠르게 연산하기 위해 고안된 완전 이진트리를 기반으로 한다.부모의 노드의 키 값이 자식보다 큰 경우는 최대힙 작은 경우에는 최소 힙이라고 한다.

힙을 만드는 방법 [위키백과]

완전 이진 트리로 주로 구현 하기 때문에 탐색의 시간 복잡도는 O(logn)이다.

 

해시테이블(HashTable)

Key-Value의 데이터 구조인 자료구조.해시 테이블은 각각 Key 값에 해시 함수를 적용해 index를  생성하고 이는 검색시에 사용된다.따라서 이 구조는 데이터를 검색하기에 용이하다.

해쉬 테이블(위키 백과)

데이터의 삽입,삭제,조회의 시간복잡도의 평균 속도 모두 O(1)이다.

 

 

해시함수

데이터를 가르키는 주소를 만들기 위해 적용하는 함수이다. 

나눗셈	입력 값을 테이블의 크기로 나눈다.  해시 테이블의 크기는 2의 배수에 가깝지 않은 소수가 좋다.
Digit Folding(자리수 접기)	각 Key의 문자열을 아스키 코드로 바꾸고 값을 합한 데이터를 테이블 내 주소로 사용한다. 이는 충돌을 줄위기 위해 되었다.
Multiplication Method	숫자로 된 Key 값과 K와 0 사이의 실수A, 2의 제곱인 m 곱한다. h(k)=(kAmod1) × m

 

 

이러한 방식으로 주소를 만들어도, 수학적 계산이기 때문에 같은 주소가 나오면 어떻게 해야할까 ?

 

분리 연결법(Separate Chaining) VS개방 주소법(Open Addressing) 

분리 연결법[위키백과]

분리 연결 법은 해당 위치에 값이 있다면, 연결리스트의 방식으로 빈 공간에 값을 삽입하는 체이닝(Chaining) 방식이다. 해당 방식은 삽입 삭제가 용이 하지만 데이터 수가 많아 질수록 충돌은 잦아 질 것이고 비효율 적이 것이다.

 

개방주소법 은 비어있는 해시를 찾아서 데이터를 저장하는 방식이다. 비어있는 해시를 찾는 방법은 크게 세가지가 있다.

데이터를 삭제하면 삭제된 공간은 비어버린다. 따라서, 재정리 해주는 작업이 필요하다.

 

• 선형 탐색(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 비어있는 장소에 데이터를 삽입한다.
• 제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)
• 이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.

 

 

출처 :

망나니개발자 블로그

[자료구조] 해시테이블(HashTable)이란?

preamtree의 행복 블로그