Hash란 무엇인가?

개발하는 지용이의 쐬주집·2023년 2월 15일
algorithmhash
1

알고리즘(Algorithm)

목록 보기
1/4
post-thumbnail

Hash 란?

  • Hash 의 정의 : 해시는 데이터를 다루는 기법

  • Hash 값 이란 : 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값이다

이미지 출처

Hash 특징

  • 해시를 통한 데이터 저장시에는 검색과 저장이 아주 빠르게 진행

    • 빠르게 진행될 수 있는 이유는? 
      => 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가)  한 쌍으로 존재하고, key값이 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 된다.

  • 무결성

    • 해시를 통해 무결성을 지킬 수 있는 이유?
      => 해시는 특정한 데이터를 상징하는 고정된 길이의 데이터로 변환하게 된다.
      여기서 상징 이터는 원래의 데이터가 조금만 달라져도 확연하게 달라지는 특성 가지고 있어 무결성을 지키는 데에 많은 도움을 준다.

      EX) 'A'라는 문자열의 해시와 'B'라는 문자열의 해시는 고작 한 알파벳이 다를뿐이지만 해시 결과값은 완전히 다른 문자열이 나오게 된다.


  • 보안성

    • 해시는 기본적으로 복호화가 불가능 하다는 특징이 있다.
      => 이는 당연히 입력 데이터 집합이 출력 데이터 집합을 포함하고 있으므로, 특정한 출력 데이터를 토대로 입력 데이터를 찾을 수 없기 때문이다.

      즉, 동일한 출력 값을 만들어낼 수 있는 입력 값의 가짓수는 수학적으로 무한개라고 볼 수 있다.해시는 애초에 복호화를 수행할 수 없도록 설계되었으며, 실제로도 해커가 쉽게 복호화를 할 수 없다는 점에서 강한 보안성을 가진다.

    • 입력값 상관없이 고정된 길이의 해시값을 출력한다.
    • 복호화 불가능하다. [단방향 암호화 기법의 특징]
    • 복잡하지 않은 알고리즘으로 구현되기 때문에 상대적으로 CPU, 메모리 같은 시스템 자원을 덜 소모한다.
    • 같은 입력값에 대해서는 같은 출력값을 보장한다.

Hashing 이란?

  • Hashing 이란?
    키(key)와 값(value)으로 매핑되는 과정 자체를 해싱(Hashing) 이라고 한다.

Hash Function 이란?

Hash 함수란?

  • 정의 : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 단반향성 함수/알고리즘 이다.

  • 사용 용도

    • 메세지(중요 정보)의 무결성 확인
    • 디지털서명의 생성
      • 메세지에 대한 디지털서명이 아니고, 그 해시 값에 대해서 만 디지털 서명을 함
    • 메세지인증코드의 생성
      • 메세지 내용의 무결성 확인 (변경 검출) 및 메세지 송신자가 진짜인지 인증 (인증 확인)
    • 일회용 패스워드(OTP)의 생성
    • 세션 키 도출
    • 소프트웨어 배포시 변경 검출

  • 알고리즘 예

    • MD5

      • 임의의 길이의 값을 입력 받아 128 비트 길이의 해시값을 출력하는 알고리즘이다.
      • 단방향 암호화이기 때문에 출력값에서 입력값을 복원하는 것은 불가능 하며 서로 다른 입력값에서 같은 출력값이 나올 확률은 극히 낮다.

    • SHA

      • 1993년부터 미국 NSA가 제작하고 미국 국립표준기술연구소(NIST)에서 채택한 암호학적 해시 함수이다.

  • 자바의 haschCode()

     public final class String
 	implements java.io.Serializable, Comparable<String>, CharSequence{
 
 	private final char value[];
 	
 	public int hashCode(){
 		int h = hash;
 		if(h == 0 && value.length > 0){
 			char val[] = value;
 			for(int i =0; i < value.length; i++){
				h = 31*h + val[i];
			}  
			hash = h;
 		}               
		return h;
 	}
 }

    String.java의 경우, hashCode()를 재정의하여 사용 하고 있다.
    => 계산 방법 : hashcode = s[0]31^(n-1) + s[1]31^(n-2) + ... + s[n-1]
    방법으로 hashcode를 계산한다. ( s[0]는 문자열의 0번 Index의 char 이다. )

Hash의 이용

정렬된 배열에 새로운 값 추가

위의 그림처럼 정렬된 배열에 새로운 값을 추가하게 될 경우

과정)

  1. 삽입할 위치를 이진 검색으로 조사한다.

  2. 인덱스 번호 6번 인덱스 요소 부터 모두 한칸씩 뒤로 이동한다.

  3. 6번째 인덱스에 값을 대입한다.
    => 위와 같은 과정을 통해

    • 이진 탐색 O(log n)

    • 요소 이동 O(n)

      ⇒ 결국 O(n) 시간복잡도를 가지게 된다.


해시를 이용하여 새로운 값 추가

해시를 이용하면

  • 데이터를 저장할 위치 검색
  • 데이터 추가
  • 데이터 삭제
    ⇒ 효율적 수행이 가능하다.

과정)

  1. 키값을 가지고 해시함수를 통해 해시값을 구한다.

  2. 구한 해시값을 인덱스 위치로 데이터를 추가한다.

    위와 같은 과정으로

    • 요소 삽입 O(1)

      ⇒ O(1) 시간복잡도를 가지게 된다.

    해시를 사용함으로써 이전 배열에 데이터를 삽입시 한칸씩 뒤로 옮겨야 하는 과정이 생략 되어 더 빠르게 데이터의 처리를 할 수 있다.

Hash Collision

정의 : 충돌(Collision) 은 서로 다른 문자열이 Hash function을 통해 Hash 한 결과가 같은 경우 (중복되는 경우)이다.
⇒ 위의 그림에서처럼 저장할 버킷이 중복되는 현상을 충돌 이라고 한다.

  • 해시 충돌의 문제점
    충돌이 많아질 수록 같은 해시값의 데이터들에서 찾아야할 데이터를 찾는 과정이 추가되어
    시간 복잡도가 O(1)에서 O(n)에 가까워지기 때문에
    ⇒ 충돌이 적을 수록 좋은 해시 함수가 된다.


  • 충돌의 해결 방안 (대표적인 2가지 방법)

    • Chaining 기법 : 같은 해시 값을 갖는 데이터를 쇠사슬(chain) 모양으로 연결리스트에서 연결하여 관리하는 방법
    • Open addressing 기법 : 빈 버킷을 찾을 때까지 해시를 반복하여 관리 하는 방법

Hash Collision 보안 기법

Chaining 기법

Chaining 기법 정의: 체이닝 기법은 동일 해시 값을 갖는 데이터를 쇠사슬 모양처럼 연결 리스트를 통해 관리하는 방법이다

  • 장점

    • 한정된 저장소(Bucket)을 효율적으로 사용가능 ( 정해진 Bucket범위만 사용 함 )

    • 해시 함수를 선택하는 중요성이 상대적으로 적음.

    • 상대적으로 적은 메모리를 사용. 미리 공간을 잡아 놓을 필요가 없다.

  • 단점

    • 해시 함수의 퀄리티에 따라서 한 주소에 쏠림 현상이 발생할 수 있다.

    • 성능이 좋지 않은 해시 함수로 인해 동일 주소에 여러 값이 들어가는 경우
      => 선형 구조에서의 탐색 시 최악의 경우 O(N)의 시간복잡도를 갖게 되어 탐색이 빠르다는 해시 테이블의 장점이 퇴색된다.

      • 단점의 보안
        • 버킷의 크기를 동적으로 늘리기
        • 비선형적 구조로 entry 저장하기
          (참고) Java Collection Framework의 HashMap은 먼저 list형태로 해시 충돌된 것들을 연결하다가 entry가 일정 수를 넘어가면 Red-Black Tree로 연결 형태를 전환한다.

Open Addressing 기법

Open Addressing 기법 정의 : 열린 주소 기법은 동일된 해시 값으로 충돌이 날 경우 일정 변수값을 더하여 재해싱을 통해 데이터를 저장하는 방법이다.

  • 재해싱 종류

    • 선형 탐색(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.
    • 제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)
    • 이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.

  • 장점

    • 체이닝처럼 포인터가 필요 없고, 지정한 메모리 외에 추가적인 공간이 필요 없다.
    • 삽입 삭제시 오버헤드가 적다.

  • 단점

    • 최악의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다.
    • 특정 위치에만 데이터가 몰리는 현상이 나타날 수 있다.
profile
개발하는 지용이의 쐬주집
지쐬 오픈 준비중~!!
다음 포스트

검색(Search) 알고리즘 이란?

0개의 댓글