크래프톤 정글 6기 TIL - Day 11 | 해시, 그래프

드디어!!! 1주차가 끝났다아아~

먼가 빨리 지나간 것 같은데, 1주일동안 한 공부양을 보면 빨리 지나간건 또 아닌듯.

아침에 시험봐서 그런가 걍 개개ㅐㄱ 오늘 개개개 무기력했음. 집이었다면 게임하다 잤겟지..하지만??여기서는 그럴수가 없다~ 해야지 뭐 어떡해~

---

해시

 

정의와 성질

해시 자료구조 : 키에 대응되는 값을 저장하는 자료구조

insert, erase, find, update → O(N)

 

해시 함수: 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수

* 이상적인 상황 → O(1), 충돌이 빈번한 경우 성능 저하, 최악의 상황 → O(N)

각 키의 해시 값이 최대한 균등하게 퍼져야 성능이 좋아지기 때문에 좋은 해시 함수를 정해야 함!

 

충돌

서로 다른 키가 같은 해시 값을 가진 경우 충돌이 일어난다.

 

충돌 회피 1
Chaining

각 인덱스마다 연결 리스트를 둬서 충돌 회피를 하는 방법

 

Insert

 

 

Erase

 

충돌 회피 2 
Open - Addressing

각 인덱스에 바로 (키, 값) 쌍을 쓴다

 

Insert

 

 

Find

 

 

Erase

값을 삭제 할 때 빈칸으로 두면 나중에 find 할 때 뒤의 원소들을 확인하지 않게 되서 반드시 Dummy 값을 넣어 주어야한다.

 

Linear Probing : 충돌 발생시 오른쪽으로 한 칸씩 이동하는 방식

장점 - Cach hit rate 가 높다.

단점 - Clusting 이 생겨 성능에 영향을 줄 수 있다.

 

Quadratic Probing : 충돌 발생 시 오른쪽으로 1,3,5...칸씩 이동하는 방식

장점: Cache hit rate가 나쁘지 않다, Clusting을 어느정도 회피할 수 있다.

단점 : 해시 값이 같을 경우 여전히 Clusting이 발생한다.

 

Double Hashing: 충돌 발생 시 이동할 칸의 수를 새로운 해시 함수로 계산하는 방식

장점: Clusting을 효과적으로 회피할 수 있다.

단점: Cache hit rate가 낮다.

 

---

그래프

정의 : 정점과 간선으로 이루어진 자료구조

 

 

단순 그래프
Simple Graph

두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프

 

표현법 1
인접 행렬

 

 

표현법 2
인접 리스트

인접 행렬과 비교했을 때 정점이 많고 간선은 상대적으로 작은 상황에서 공간을 절약할 수 있는 방식

 

인접 행렬과 인접 리스트 비교