선형 자료구조인 해시를 모두 들어보았을텐데 이번 시간에는 해시를 준비해보았습니다.
해시란?
해시는 데이터를 다루는 기법 중 하나로 검색과 저장이 아주 빠르게 진행됩니다. 여기서 빠르게, 해시는 어떻게 빠르게 진행될 수 있을까요? 해시는 Key와 Value로 이루어져있기 때문에 빠른 검색과 저장이 가능한 것입니다.
해시 관련 용어 정리
해시하면 어려 용어들이 떠오를법한데 그만큼 연관 용어가 많습니다.
1. 해시함수
해시 함수는 Key, Value 중 Value의 값을 배열의 인덱스의 정수로 변환하는 과정입니다. 간단한 말로 Key를 해시로 바꾸어주는 중간다리라고 생각하면 됩니다.
다음 사진과 같이 해시 함수는 매핑 전과 후로 나눌 수 있으며 매핑 전에는 Key, 매핑 후에는 해시코드라고 부르게 됩니다. 그리고 매핑하는 과정을 해싱이라고 부릅니다.
2. 해시코드
Key, Value 중 Value의 값을 배열의 인덱스의 정수로 변환된 고유 숫자 값입니다. 해시 함수를 통해 해시로 변환된 값이라고 보면됩니다.
3. Key&Value
- Key
: 고유한 값, 해시 함수의 input입니다. 해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성 추구 가능합니다. - Value
: 버킷에 최종적으로 저장되는 값 키와 매칭됩니다.
해시 테이블이란?
다음으로 해시에 대해 더 쉽게 이해하기 위해서 해시법에 사용되는 자료구조인 해시테이블에 대해 이해해봅시다.
해시 테이블이란 연관 배열 구조를 이용하여 키에 결과 값을 저장하는 자료구조입니다.
연관 배열 구조 ??
키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다.
따라서 키(key)를 이용하여 값(value)을 도출할 수 있다.
해시테이블은 키, 해시함수, 해시, 값, 버킷로 이루어져있습니다. (+ 버킷은 값을 저장하는 저장소라고 생각하면 됩니다.)
다음과 같은 사진에서 John Smith가 Key일 때 해시 함수를 거쳐 해시로 변경이 됩니다. 그리고 해시가 값과 매칭되어 버킷에 저장이됩니다.
해시 충돌
해시에서 충돌이 일어날 수도 있습니다. 서로 다른 키가 같은 해시가 되는 경우를 해시 충돌이라고 부릅니다. 우리는 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요합니다.
이 사진에서 John Smith와 Sandra Dee가 해시함수를 거쳐서 똑같은 02라는 해시를 가리키는 것을 볼 수 있습니다. 이렇게 되는 경우를 해시 충돌이라고 부릅니다.
그래서 우리는 해시 충돌을 예방하기 위해 체인법과 오픈 주소법을 사용합니다.
체인법
같은 해시 값을 갖는 데이터를 연결 리스트를 통해 사슬 모양으로 연결합니다. 이렇게 하게되면 한정된 저장소를 효율적으로 사용할 수 있지만 한 해시에 자료들이 계속 연결된다면 검색 효율을 낮출 수 있습니다.
오픈주소법
충돌이 발생한 지점 이후에 빈 공간이 있는 해시 테이블을 찾아 데이터를 삽입합니다.
저기 키 값이 5인 곳에서 충돌이 났으면 그 지점 이후에 빈 공간을 찾아나서게 됩니다. 하지만 다음 키 값 6도 빈 공간이 아니기때문에 또 한번 해시를 거칩니다. 그다음 7에선 빈 공간을 찾았기 때문에 7에 삽입을 할 수 있습니다.
오픈 주소법의 핵심은 재해시라고 생각하면 됩니다.
근데 만약 이 친구는 재해시를 몇번할지모르기 때문에 해시 함수의 성능에 따라 전체 성능이 좌지우지 됩니다.
해시 면접 질문
Q. 해시는 어떤 상황에서 어떻게 사용될까요?
A : 해시는 키와 값으로 이루어진 특정 때문에 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용됩니다. 해시 함수는 큰 파일에서 중복되는 레코드를 찾을 수 있기 때문에 DNA sequence에서 유사한 패턴을 찾는데 사용 or 암호학에서도 사용될 수있다고 합니다.
