해쉬, 라빈 카프

Hash Table (해쉬)

• 임의의 길이의 데이터 → 고정된 길이의 데이터로 mapping
  • 문자열 → 숫자 (문자열 해쉬)
  • ex) d[“some blah”] → d[727]
• 용어
  • 해쉬 함수
    • 입력한 키를 수로 바꾸는 함수
  • 해쉬 값
    • 해시 함수의 결과
    • 데이터를 저장할 위치(인덱스)
  • 해쉬 테이블
    • 해시 값을 인덱스로 사용하는 저장공간 (dict, set 내부 구조)
    • 해쉬 값을 % m 로 연산한 크기만큼 배정 및 인덱스로 활용
      • 해쉬 값은 무한하기에 고정된 범위로 줄이는 용도
  • 해싱
    • 해시 값으로 변환시키는 것
  • 충돌
    • 서로 다른 키가 같은 해시 값을 가지는 것
    • hash(“abc”) #5
    • hash(“xyz”) #5
• 특징
  • 같은 입력, 같은 출력
  • 다른 입력, (가능한한) 다른 출력
    • 해쉬 충돌 존재
  • $O(1)$의 탐색, 삽입, 삭제 (armotized)
  • linked list처럼 처음부터 끝까지 탐색 불 필요

문자열 해싱

• 문자열 비교 vs 수 비교
  • 문자열은 처음부터 비교해야 함
  • 수는 비교가 바로 가능
• 문자열 해싱
  • 문자열을 $n$ 진법으로 변환 하는 것 (+ % m)
    • $m$은 가능한 큰 소수 (해쉬 테이블의 크기에 해당)
  • 소문자로 이루어진 ‘abc’를 숫자로 해싱 예시
    • $n=29$ (각 글자의 경우의 수보다 크게)
    • key = $$ Seq(‘a’) * n^2 + Seq(‘b’) * n^1 + Seq(‘c’) * n^0 % mod
  • 주어진 문자열에서, 3칸씩 슬라이드가 이동해야 할 경우
    • ex) ‘abc’d에서 a’bcd’로 빠르게 해시 구하기
    • $(key-(Seq{(}^{\prime }{a}^{\prime })\ast n^2))\ast n+seq{(}^{\prime }{d}^{\prime })$

라빈 카프

• 폴리노미얼 해시 함수
  • $hash(s)=(s_0\cdot b^{m-1}+s_1\cdot b^{m-2}+\cdots +s_{m-1}\cdot b^0)modp$
• 슬라이드 윈도우로 해시 갱신
  • 이전 맨앞 해시 빼고
  • 새로운 문자 해시 추가
  • 해시 값이 같고, 글자도 같으면 일치
• 문자열 패턴 검색