해시, Hash, 해시테이블

wkdgusrhkd·2021년 4월 21일
0

자료 구조?

목록 보기
2/3
post-thumbnail

해시, Hash에 대해서 공부해보고 정리한 자료입니다.

해시테이블이란

검색하고자 하는 key 값을 입력받아서 해시함수(F)를 돌려서 반환받은 해시코드(Hash Code)를 배열의 인덱스(Index)로 환산해서 데이터(Value)에 접근하는 자료 방식.

사진 출처 : 유튜브-엔지니어대한민국, [자료구조 알고리즘] 해쉬테이블

여기서 key값은 문자, 숫자 혹은 파일도 될 수 있다고 한다.
해시 함수는 입력받은 값의 길이나 크기에 상관없이 동일한 길이의 해시 코드를 만들어준다.

왜 생겨났을까

Before:

초창기의 컴퓨터 공학자들은 데이터를 순차적으로 저장하고, 삭제하고, 읽는 방식부터 시작했나보다.

위 그림처럼 key: value 쌍이 저장되어 있다고 생각하자.

누군가가 key 값이 104인 데이터의 value를 알고 싶다면 0번에서 부터 순서대로 조회해 나가야 한다.

혹은 빈 공간을 찾아 새로운 데이터를 저장하고 싶다면, 역시 처음부터 순서대로 조회해 나가야 한다.

이런 불편함을 해소하기 위해 만들어진 것이 해시 테이블이라고 한다.

After:

사진 출처 : 유튜브- Chan-Su Shin, 자료구조 해시테이블 - 소개, 해시 함수

해시 테이블에서는 앞서 말했듯이 key 값을 받아 해시 함수를 돌리고, 이를 배열의 index로 환산한다고 했다.

사진의 왼쪽을 보면 2019317: "신창수", 2019209: "홍길동"이라는 데이터가 있고 이들의 key값을 받아 / 10 이라는 해시 함수를 돌린다. 그 결과의 나머지를 배열의 index로 환산하면 각각 7번과 9번 자리에 들어가게 되는 것이다.
이러한 방식으로 만들어진 배열을 해시 테이블이라고 보면 될 것 같다.

Before에서의 접근 방식과 달리 이제 데이터들을 순서대로 일일이 조회 할 필요가 없다. key값이 2019317인 데이터의 value를 알고 싶다면 해시 함수를 돌리고 그 결과를 해시 테이블에서 조회해 보면 된다.

의문

여기서 해시를 처음 공부하는 사람들에게 모두 같은 의문이 생길 것이다.
다른 key값을 넣었는데 해시 함수의 결과가 같다면 어떻게 될까.

충돌

20193172018007key 값은 서로 다르지만 같은 Index를 가지게 되는데, 이 상황을 충돌(Collision)이 발생했다고 말한다.

충돌에는 두 가지 경우가 있다.

  1. 각기 다른 키에서 같은 해시 코드가 생성된 경우
  2. 해시 코드는 다르지만 같은 인덱스를 배정받은 경우

충돌이 발생하면 어떻게든 해소를 해줘야 한다. 이 해소 역시도 일정한 규칙에 따라서 진행이 되어야 하는데 충돌 해소를 collision resolution, 충돌 해소의 방법을 collision resolution method라고 부른다.

해시 함수

Perfect hash function

가장 이상적인 해시 함수는 key - slot1-1의 관계를 가지는 것이다. 충돌이 전혀 일어나지 않는 상황이다. 하지만 현실에서 이런 이상적인 상황을 맞는것은 매우 힘들다.

Universal hash function

현실에서 이상적인 해시 함수를 대체하는 개념이 Unversal hash function 혹은 Universal hashing이다.

사진 출처 : 유튜브- Chan-Su Shin, 자료구조 해시테이블 - 소개, 해시 함수

key x, y에 대하여 f(x)f(y)와 같을 때(충돌이 발생한 상황), 이 확률이 m에 대하여 반비례하도록 하는 것이다.

m은 전체 슬롯의 개수, 슬롯은 해시 테이블 내의 각각의 저장공간을 의미한다.

이런 조건을 만족하도록 해시 함수를 설계했다면 그런 함수를 universal hash function이라 한다. 하지만 이것 역시도 힘들기 때문에 1/m대신에 c/m으로 조건을 대체하기도 하며, 이러한 경우 c-universal h.f.이라 부른다.

Division h.f.

Multiplication h.f.

Folding h.f.

Mid-squares h.f.

Extraction h.f.

정리

결국 해시 테이블에서 중요한 건

  1. 테이블의 형성
  2. Hash function => 해시 함수를 어떻게 설정할 것인가
  3. Collision resolution method => 충돌이 발생할 수 밖에 없는데, 이를 어떻게 해결할 것인가.

크게 이 3가지라고 보면 된다.
이것들에 의해 해시 테이블의 성능이 결정된다.

참고자료

유튜브 - Chan-Su Shin, 자료구조 해시테이블 - 소개, 해시 함수

유튜브 - 엔지니어대한민국, [자료구조 알고리즘] 해쉬테이블(Hash Table)에 대해 알아보고 구현하기

profile
프론트!

관심 있을 만한 포스트

0개의 댓글