[etc.] 해시 테이블과 해시 함수

해시 테이블 (Hash Table)

F(key) → Hash Code → Index → Value

검색하고자 하는 key값을 입력받아서 해시 함수를 돌려서 반환받은 해시 코드를 배열 index로 환산을 해서 데이터에 접근하는 방식의 자료구조이다

• 여기서 key값은 문자열이 될 수도 있고 숫자, 파일 데이터도 될 수 있다.
• 해시 함수는 어떤 특정한 규칙을 이용해서 입력받은 key값으로 (그 key값이 얼마나 큰 지는 상관 없이) 동일한 해시 코드를 만들어 낸다.
• 원본으로 비교하려면 정보 노출의 위험도 있고 용량도 어마어마하게 커질 수 있다. 그래서 해시코드를 사용하는 것.
• 해시 함수는 key의 점 하나 또는 공백 하나만 달라도 전혀 다른 해시 코드를 만들어 낸다.
• 입력 데이터가 완벽하게 일치해야만 동일한 해시 코드를 만들어 낸다.

example

만약 누군가가 youtube에 있는 video를 다운로드 받아서 본인 채널에 그대로 올리게 되면 “중복되는 영상”이라고 에러가 발생하고 업로드 되지 않는다.

이는 해시 테이블을 이용한 것이다.

해시 테이블 장점

• 검색 속도가 매우 빠르다(O(1))

  • 해시 함수를 이용해서 만들어 낸 해시 코드는 정수다.
  • 배열 공간을 고정된 크기만큼 미리 만들어놓고 해시 코드를 배열의 갯수로 나머지 연산을 해서 배열에 나눠 담는다.
  • 해시 코드 자체가 배열의 인덱스로 사용되기 때문에 검색 자체를 할 필요가 없고 해시코드로 바로 데이터의 위치에 다이렉트로 접근할 수 있기 때문에 검색 속도가 빠른 것이다.

해시 알고리즘

• 알고리즘이 효율적이지 않으면 하나의 방에 데이터가 여러 개 들어가야 되니까 충돌 현상이 생길 수 있다. (collision)
• 비효율적일 경우 O(1)이 아니라 O(n)까지 걸릴 수도 있다.
• 입력받은 key를 가지고 얼마나 골고루 잘 분배를 하느냐에 따라 좋은 알고리즘인지 결정이 된다.

Hash Algorithm Collision

• different keys → same code

  • 서로 다른 key값으로 동일한 해시 코드를 만들어 내기도 한다. key값으로 들어갈 수 있는 데이터의 가짓수가 무한한 데에 반해서 해시 코드는 정수 개밖에 제공하지 않기 때문에 알고리즘이 아무리 좋아도 중복되는 해시 코드를 가질 수 있다.

• different code → same index

  • 다른 해시 코드를 갖더라도 동일한 인덱스에 들어갈 수 있다.
• Collision을 최소화 하기 위해서 좋은 해시 알고리즘을 만드는 일은 해시 테이블에서 매우 중요한 이슈다.

해시 테이블 구현 simple example

• 문자열의 각 문자 ASCII을 더해서 Hash Code를 만들어보자.

  • “sung” → 115 + 117 + 110 + 103 = 445
  • “jin” → 106 + 105 + 110 = 321
  • “hee” → 104 + 101 + 101 = 306
  • “min” → 109 + 105 + 110 = 324

• Convert to index

  • 해시 테이블의 필수 조건 중에 하나가 고정된 크기의 배열을 미리 만들어 놓는 것이다.
  • 길이 3을 가진 배열을 만들었다고 가정하자.

  • hash code를 index로 변환할 때는 arrayLength(나머지 연산) 로 계산한다.

    • sung (445 % 3 === 1) : index 1에 저장
    • jin (321 % 3 === 0) : index 0에 저장
    • hee (306 % 3 === 0) : index 0에 저장
    • min (324 % 3 === 0) : index 0에 저장
    • 이 해시 알고리즘의 경우 index가 골고루 분배 되지 않는 것으로 보아 이 해시 알고리즘은 그리 좋은 알고리즘은 아닌 것으로 보인다.
• 해시 알고리즘 Collision이 생기는 것을 대비해서 배열 index 각각에 바로 저장하는 것이 아니라 linked list로 저장된다.
• 검색할 때는 key로 해시코드를 만들고 그걸 index로 환산해서 배열의 해당 index의 linked list를 돌면서 내가 찾는 데이터를 가져온다.
• 해시 충돌의 확률이 높을수록 서로 다른 데이터를 구별하기 어려워지고 검색하는 비용이 증가하게 된다.

해시 함수 종류

• 암호학적 해시함수의 종류로는 MD5, SHA(Secure Hash Algorithm)계열 해시함수가 있으며 비암호학적 해시함수로는 CRC32등이 있다.

해시(Hash) 와 암호화(Encryption) 비교

• 공통점 : 둘 다 암호화 기법

• 차이점

  • 해시(Hash)

    • 단방향 암호화 기법
    • 평문 -> 암호화된 텍스트(복호화 안 됨, 무결성 체크만 한다.)
    • 데이터 변조가 없었는지 무결성을 확인하는 것이 주 목적.
    • 사용자 비밀번호 저장 시 사용된다.

  • 암호화(Encryption)

    • 양방향 암호화 기법
    • 평문 -> 암호화된 텍스트(비밀 키가 있다면 복호화를 통해 원래의 데이터로 복원이 가능함)
    • 인가되지 않은 제 3자에게 데이터 노출을 막는 것이 주 목적.
    • 평문을 추가적인 정보와 함께 암호화 알고리즘을 사용하여 인코딩 하는 과정.
    • 암호화된 메세지를 받은 수신자는 복호화 키를 사용하여 이를 평문으로 복원할 수 있다.
    • 특정 데이터에 접근이 가능한 사용자인지 확인할 때 사용 된다.

reference

• Hash Table에 대해 알아보고 구현하기
• Hash와 Encryption의 차이점