코딩 테스트 합격자 되기 - 5주차

공부한 내용

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

   • ex) 전화기록부 (이름(key)-전화번호(value))
   • 해시의 특징
     1. 단방향 동작 : 키를 통해서만 값을 찾을 수 있음! 값을 통해 키를 찾을 수 없다.
     2. 찾고자 하는 값을 O(1)에서 바로 찾을 수 있다. 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기위한 탐색 과정이 필요치 않다.
     3. 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 한다.

   

   • 해시의 특성을 활용하는 분야
     • 비밀번호 관리 : 값(value)를 바로 외부에 공개하지 않으므로 보안에 이용한다. 네트워크 보안에도 이용된다.
     • 데이터베이스 인덱싱
     • 블록체인 : 각 블록은 이런 블록의 해시값을 포함하고 있으며 데이터 무결성을 확인할 수 있다.

2. 해시 함수

   • 고려 사항
     1. 0<해시함수 반환값 <= len(hash table)-1
     2. 충돌 최소화
        • 충돌이란? 키가 다른데 해싱 함수를 적용한 결과가 동일한 것
        • 충돌 최소화의 의미는 충돌이 0인 해시 함수는 거의 없기 때문
   • 자주 사용하는 해시 함수
     1. 나눗셈법 : 키를 소수로 나눈 나머지를 활용, 모듈러 연산이라고 함, 소수가 아니라면 규칙적으로 같은 해시값이 반복됨
        • 테이블의 크기는 소수의 크기로 결정되며 큰 소수를 구하는 효율적인 방법은 아직 없는 것이 단점
     2. 곱셈법
        • 모듈러 연산을 활용하지만 소수를 활용하지 않음
        • 공식 : h(x)= (((x*A)mod1))*m), A는 활금비(1.6180339887), m은 최대 버킷의 개수
        • ex) k*A = x.y -> y*m을 통해 해시 테이블에 맵핑한다. 나눗셈법처럼 소수가 필요가 없으며 해시 테이블의 크기가 커져도 추가 작업이 필요하지 않다.
     3. 문자열 해싱
        • 헤헤.. 이해하기 힘들어서 포기^^...

3. 충돌처리

   1. 체이닝으로 처리
      • 충돌 발생시 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결한다.
      • 단점
        1. 해시 테이블 공간 활용성 떨어짐 : 충돌이 많아지면 그만큼 링크드 리스트의 길이가 길어지고 다른 해시 테이블의 공간을 덜 사용함,
        2. 검색 성능 저하 : 링크드 리스트의 순차검색으로 인한 시간 복잡도 증가 (O(N))
   2. 개발 주소법으로 처리 : 빈 버킷을 찾아 충돌값 삽입
      1. 선형 탐사 방식
         • 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동함
         • 수식 : h(k,i) = (h(k)+i)mod m, m = 수용할 수 있는 최대 버킷
         • 단점 : 충돌 발생시 N 칸씩 이동하는데 해시 충돌이 발생한 값끼리 모이는 영역이 생긴다. 클러스터를 형성한다고 한다, 즉, 해시값은 겹칠 확률이 더 올라간다.
      2. 이중 해싱 방식
         • 해시 함수를 2개 사용한다.