Hash

• hash 함수를 사용해서 변환한 값을 index로 삼아 key, value를 저장하는 자료구조
• key, value 로 이루어진 자료구조
• 데이터가 저장되기 전에 미리 공간을 만들어놔야 하므로 공간 효율성은 낮다.

Hash Function

• key를 고정된 길이의 hash로 변경해줌 : hashing
• key를 hash로 만들어내는 함수

Hash Table

• hash function을 사용하여 key를 hash 값으로 매핑. 이 hash 값을 주소, 또는 색인 삼아 value를 key와 함께 저장하는 자료구조
• hash를 주소로 삼아 value를 저장하는 자료구조

bucket, slot

value(데이터) 가 저장되는 곳

사용

적은 자원으로 많은 데이터를 효율적으로 쓰기 위해

시간복잡도

삽입, 삭제, 검색 시 모두 평균적으로 O(1)

Direct-address Table

• key의 전체 개수 == bucket의 크기
• key의 개수와 table의 개수가 같기 때문에 해시 충돌이 일어나지 않음
• 실제 키가 사용되지 않으면 메모리 낭비
• 그래서 키 개수보다 버킷 크기를 적게해서 해시충돌이 발생.

해시 충돌

• A, B 가 존재
• hash(A) = 2
• hash(B) = 2
• 이것이 hash collision

해시충돌 해결방법

• Chaining
  • bucket 에서 충돌이 일어나면 기존값과 새로운 값을 연결리스트로 연결
  • 충돌이 나면 그 때 공간을 만들어서 연결만 해주면 된다
  • 같은 hash에 많이 연결되면 검색 시 효율이 떨어짐 (-> 그래서 open addressing 이 나옴)
• Open Addressing
  • 충돌이 일어나면 비어있는 hash에 value를 저장
  • 비어있는 hash를 찾는 방법
    • 선형 탐색 : 해시 값에서 고정폭으로 건너 뛰며 비어있는 해시가 나오면 저장
    • 제곱 탐색 : 고정폭이 아닌 1 -> 4 -> 9 -> 16 ... 으로 빈칸을 찾음. 공간을 많이 확보해놔야함.

해시 함수 매핑 개선

• division method
  • 기본적인 해시 함수. key mod hash table의 크기 m (해시 중복 방지를 위해 주로 소수)
  • 간단하면서 빠른 연산
  • 남는 공간이 발생해 메모리 상으로 비효율적
• multiplication method
  • key, 0 < A < 1, h(key) = (key * a mod 1) * m
  • 2진수 연산에 최적화된 컴퓨터 구조를 고려한 해시함수
• universal hashing
  • 여러 개의 해시함수를 만들고, 해시함수의 집합에서 무작위로 해시함수를 선택해 해시값을 만드는 기

 

References

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Hash.md

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖

https://go-coding.tistory.com/30

[자료구조] Hash의 개념 및 설명