Hash | 해시

해시

• 키에 대응되는 값을 저장하는 자료구조
• 시간 복잡도 : Insert, Erase, FInd, Update 모두 O(1)

 

해시함수 

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

 

충돌 해결 방안

• 충돌은 해시에서 가장 큰 애로사항으로 해결 시 성능에 큰 영향을 미치기에 해결하면 나이스

1. Chaining

• 각 인덱스마다 연결리스트를 하나씩 두는 것.
• 삽입 : 발생 시 연결리스트에 값을 추가.
• 탐색 : 인덱스를 찾아 해당 연결리스트 내에서 특정 값에 대한 탐색을 재 실행
• 시간복잡도 : 이상적 : O(1) /  최악 O(N) => 각 키의 해시값이 균등해야 성능 굳굳

 

2. Open Addressing

• 각 인덱스에 (키,값)쌍을 저장
• 삽입 : 충돌 예상 시 다음 인덱스에 값을 저장
• 탐색 : 인덱스에 해당하는 키값이 일치하는 지 확인 후 다음 인덱스로 이동하여 탐색 진행
  • 없으면 오또케? ->  또 다음 인덱스로 이동하여 값의 탐색을 진행
  • 언제까지? -> 타겟 값을 찾거나 Null을 만날 때(;타겟 값 없음) 까지.
• 삭제 : 값을 날리고 Null값을 두는 것이 아니라 해당 값에 Dummy값 등을 둠으로써 원래 값이 있었지만 제거된 상태임을 명시해 둘 필요 있음.
  • + erase시 Dummy값을 판단하는 조건 구현 필요

 

종류

2_1. Linear Probing

• 충돌 발생 시 오른쪽으로 한 칸 씩 이동하는 방식
• 장점:Cache hit rate가 높다
• 단점 : Clustering이 생겨 성능에 영향을 줄 수 있다. 빈칸을 찾을 때 까지 이동하는 횟수가 늘어나 성능 저하의 가능성이 있다.

 

2_2. Quadratic Probing

• 충돌 발생 시 오른쪽으로 1,3,5,...칸씩 이동하는 방식
• 장점 : Cache hit rate가 나쁘지 않다, Clustering 어느정도 회피 가능
• 단점 : 해시값이 동일할 경우 여전히 Clustering 발생

 

2_3. Double Hashing

• 충돌 발생 시 이동할 칸의 수를 새로운 해시 함수로 계산.
• 장점 : Clustering을 아주 효과적으로 회피 가능
• 단접 : Cache hit rate가 낮음

 

 

*Cache hit rate

-명령이나 자료를 찾기 위해 캐시 메모리에 접근했을 경우 원하는 정보가 캐시 메모리에 있을 때.

- 성능을 나타내는 척도의 일부

- 적중률 = 적중 횟수 / 총 접근 횟수

- 0.95 ~ 0.99일 때 우수하다고 함.

 

 

 

출처 : https://www.youtube.com/watch?v=1-k-D2AYY0I