CS자료구조

[자료구조] HASH 정리

DATA STRUCTURE, HASH, HASH TABLE

HASH 자료구조의 사용처

특정한 값을 수많은 값들 사이에서 찾아야 할 때 사용한다.

보안적 측면이나 Collision 및 세부내용은 타 블로그를 참조하고
여기서는 탐색 알고리즘 문제를 풀기위한 기본개념만 잡는다.

물론 탐색은 여러가지 방법이 있다. 그중에서 HASH를 사용하는 장단점을 추려보면

장점

  • 평균 case에서 O(1)의 시간복잡도를 가진다

단점

  • 메모리 영역을 일정부분 차지한다
  • 충돌이 발생할 수 있다.

HASH란?

HASH 란 용어 자체는 [고기와 감자를 잘게 다져 섞어 요리하여 따뜻하게 차려 낸 것] 이란 영단어 뜻에서 시작하면 된다.

어떤 내용물들을 잘 섞어서 특정한 형태로 만든다는 것이다.

짜장면을 두그릇 사서 '똑같은 위치와 힘으로' '왼손으로 5번' '오른손으로 6번' 비비면 두그릇은 완벽히 똑같은 짜장면이 나온다.
이때 오른손으로 8번을 비비면 다른 짜장면의 모양새가 된다.

컴돌이들은

  • 면+소스(입력값) 를
  • 같은 방법으로 섞으면(해시함수)
  • 완전히 같은 짜장면(해시값)이 된다는 점에 주목했다.

문제가 [가장 맛있는 짜장면] 을 탐색하는 것이라면, 면과 소스를 특정한 방법으로(5번,6번) 섞기만 하면 된다.

굳이 왼손으로 1번~5번, 오른손으로 1번~6번을 전부 다 탐색해볼 필요가 없게 된것이다.

HASH 사용법

HASH 자료구조는 몇가지 용어가 나온다.

  • Hash Function(해시함수)
  • Hash Table(해시 테이블)
  • Hash Value, Hash Code, Hash Checksum… (해시값)

우리가 알고싶은 탐색은 해시테이블을 보면 된다.

name phone number
John Smith 521-1234
Lisa Smith 521-8976
Sandra Dee 521-9655

이런 입력값을 주고 “Sandra Dee”의 전화번호를 찾으라고 하면, Hash를 사용하지 않을경우 “John Smith”부터 하나하나 찾아가는수밖에 없다.

하지만 이런식으로 테이블을 만들어두면

keys(입력값)이 hash function(해시함수)를 통해 Hash Value(해시값)으로 변환되어 해시값의index(색인) 을 가진 해시테이블이 완성된다.

  • 해시테이블
    index(Hash Value) Data
    01 (Lisa Smith, 521-8976)
    02 (John Smith, 521-1234)
    … …
    14 (Sandra Dee, 521-9655)

이렇게 모두 저장해두면 나중에 ‘Sandra Dee’ 라는 입력값을 찾기위해서는

  1. Sandra Dee를 해시함수에 넣는다
  2. Sandra Dee가 14인 해시값으로 변환된다.
  3. 0번주소값에서 14만큼 떨어진 주소로 바로 넘어가서 값을 가져온다

결국 탐색을 단 한번에 끝낼수 있으므로 시간복잡도는 O(1)이다.

공유하기