[코딩 테스트 합격자 되기] 해시
본문 바로가기

Coding Test

[코딩 테스트 합격자 되기] 해시

[인프런] 코딩 테스트 합격자 되기 C++

강의 링크 : https://www.youtube.com/watch?v=KsfmSyIYX3g&t=3s

 

<Hash>

배열의 경우 특정 데이터의 위치를 판단할 수 있는 정보가 없으므로, 선형탐색 해야 함 O(n)

contents 자체를 가지고 위치 (index)를 알 수 있는 것이 해시

해시 함수를 사용해서 변환한 값을 인덱스(해시값)로 삼아 키-값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조 O(1)

 

해시함수 : 임의의 키를 해시테이블의 인덱스로 변경해주는 함수

  1. 해시 테이블의 크기가 N이라면 해시함수는 0 ~ (N-1) 사이 값을 내야 함
  2. 충돌을 최소화 할수록 좋은 해시함수

* 충돌 : 서로 다른 키에 대해 해시 함수가 동일한 인덱스를 반환하는 것

 

[해시함수 종류]

  • 나눗셈법 : h(x) = xmodk (x는 키, k는 소수)
    • k가 소수여야 함 -> 테이블 크기가 커지면 큰 소수 필요 (큰 소수 구하기 어려움)
  • 곱셈법 : h(x) = (((x * A) mod 1) * m), (x는 키, A는 황금 비, m은 최대 버킷의 개수)
    •  황금비(A=1.6180339887)를 곱하는 방식
    •  mod 1 : 소수 부분만 취함 => 0 ~ 0.999999
    • 위 결과에 m을 곱하면 0 ~ m-1.xxxx
  • 문자열 해싱 : h(s) = (s[0] + s[1]*p + s[2]*p^2 + ... + s[n-1] * p^(n-1)) mod m 
    • 문자열의 아스키 코드 값을 활용한 해싱
    • p는 31 (홀수이면서 메르센 소수 - 값을 균등하게 퍼트리기 위함), m은 테이블 크기
    • a = 1, b = 2, ... z = 26로 숫자를 매칭해서 사용
    • 숫자가 금방커지므로 구현시 overflow가 발생할 수 있음 -> 수정된 공식 사용
    • (a+b)%c = (a%c + b%c) %c
    • => h(s) = (s[0] %m + s[1]*p %m + s[2]*p^2 %m + ... + s[n-1] * p^(n-1) %m)%m

[해시 충돌]

서로 다른 키에 대해 해시 함수 결괏값이 같은 경우 "충돌"이 발생함

충돌을 처리하는 대표적인 방법 : 체이닝, 개방 주소법

  • 체이닝 : 충돌 발생 시, 해당 버킷에 링크드리스트로 데이터를 연결함
    • 특정 버킷에 데이터가 N개인 경우, 탐색 성능은 최대 O(N)이 됨
    • 이를 좀 더 효율적으로 하는 방법 : 선형+이진트리
  • 개방 주소법 - 선형 탐사 : h(k,i) = (h(k) + i) mod m (k는 키, i는 충돌 시 이동할 버킷 수, m은 버킷 사이즈)
    • 충돌 발생 시, 다른 빈 버킷을 찾아 충돌값을 삽입
    • 최대한 기존 테이블을 사용하자는 방식 (메모리 save)
  • 개방 주소법 - 이중해싱 : h(k,i) = (h1(k) + i*h2(k)) mod m
    • 해시 함수를 2개 사용 (경우에 따라 N개까지 확장0
    • 2번째 해시함수에 i를 곱하는 방식, 이 때 클러스터를 줄이기 위해 m을 제곱수나 소수로 함

[해시를 사용하는 경우]

  1. 키-값 쌍으로 연관된 데이터가 존재하며, 해당 값에 대한 접근이 빈번한 경우 ex) 사전이나, 연락처 검색
  2. 중복되지 않는 키를 사용하는 경우 ex) 학번, 집주소

예시)

학생 정보 관리 시스템 - 점수 한개, 점수 여러개

문자열 내 문자 빈도수

  •  map
    • 해시(x), 이진탐색트리를 활용한 것
    • 매번 키 순으로 데이터가 정렬됨 O(logN)
    • 2중 반복문 안에 map 데이터 추가 연산하면 O(N^2*logN) -> TLE 발생 가능
    • 키 값 정렬이 필요하지 않은데 map 쓰면 안됨
    • 해시 문제는 map이 아니라 unordered_map
    • 파이썬은 defaultdict가 따로 있는 반면 c++ map은 기본값으로 0 들어감


C++ 예시 코드를 보는데 간단한 구현 부분도 문법들이 너무 낯설게 느껴짐

계속 보면서 익힐 필요

준비하고 있는 시험이 있어서 문제는 추후 풀어볼 예정