[코딩테스트 합격자 되기 스터디] 3주차 - 해시

[해시의 개념]

• 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조
  
  • 값 : 최종적으로 얻고자 하는 정보
  • 키 : 값을 검색하기 위해 활용하는 정보
  • 해시 함수 : 키를 이용해 해시값(인덱스) 로 변경해주는 함수
  • 해시 테이블 : 키와 대응한 값이 저장되어 있는 공간
  • 버킷 : 해시 테이블의 각 데이터

 

[해시함수]

• 임의의 키를 해시테이블의 인덱스로 변경해 주는 함수
  • 해시 테이블의 크기가 N이라면 해시함수는 0~ (N-1) 사이 값을 내야 함
  • 충돌을 최소화 할 수록 좋은 해시 함수

[자주 사용하는 해시 함수]

• 나눗셈법
  • 키를 소수로 나눈 나머지를 활용

h(x) = x mod d   // (x 는 키, k는 소수)

• 곱셈법
  • 나눗셈법은 k가 소수여야 하므로, 테이블 크기가 커지면 큰 소수가 필요
  • 곱셈법은 소수를 활용하지 않고 황금비를 곱하는 방식

h(x) = (((x * A) mod 1) * m)  // x는 키, A는 황금 비, m은 최대 버킷의 개수

• 문자열 해싱
  • 문자열의 아스키코드 값을 활용한 해싱

---

[해시 충돌]

• 서로 다른 키에 대해 해시 함수 결괏값이 같은 경우 "충돌" 이 발생함
• 충돌을 처리하는 방법 : 체이닝 , 개방 주소법

[언제 해시를 활용해야 하나?]

• 키-값  쌍으로 연관된 데이터가 존재하며, 해당 값에 대한 접근이 빈번한 경우
  • 사전 (단어를 검색해서 뜻을 찾음) , 연락처 (이름을 검색해서 번호를 찾음)
• 중복되지 않는 키를 사용하는 경우
  • 학번이나 집주소 (중복되지 않음)

---

[참고 강의]

코딩테스트 합격자 되기 - C++ [ https://inf.run/t92e1 ]

 

[참고 도서]

코딩테스트 합격자 되기 - 파이썬 편

[ https://www.yes24.com/Product/Goods/123272392 ]