[자료구조] 해시(Hash)

🎩 등장 배경

데이터는 날마다 늘어나고 있고 이러한 데이터를 효율적으로 저장하거나 탐색하기 위한 문제는 끊임없이 연구되고 있다. 데이터를 찾는데 가장 쉽게 떠올릴 수 있는 순차 탐색의 경우 최악의 경우에는 n개의 데이터 모두를 탐색해야하는 경우가 나오기에 효율적인 방법은 아니다. 즉 데이터가 어디에 위치해있는지 안다면 이것만큼 효율적인 방법은 없는 것이다. 이러한 효율적인 방법을 강구하여 나온 결과물 중 하나가 해시(Hash)이다.

 

 

🌳 해시의 개념

 어떠한 값이 저장되는 위치를 특정 규칙으로 정하여 탐색할 필요 없이 바로 데이터를 찾아낼 수 있는 자료구조
해시함수를 사용해 변환한 값을 인덱스로 삼아 키와 값을 저장하여 빠른 데이터 탐색을 제공한다. 
파이썬에서는 딕셔너리라는 자료형이 해시 테이블과 거의 동일하게 동작한다.

해시 테이블

• 단방향으로 동작한다: 키를 통해 값을 찾을 수 있지만 값을 통해서 키를 찾을 수 없다. (보안에 활용되기 좋다.)
• 찾고자하는 값을 바로 찾을 수 있다: 키 자체가 해시 함수에 의해 값이 있는 인덱스 역할을 하기에 탐색이 필요하지 않다.

해시를 사용하지 않는 경우

 

❄️ 활용되는 분야

• 코딩 테스트: 특정 데이터를 탐샣가는 횟수가 많을 경우 사용
• 실제 사례: 비밀번호 관리, 데이터베이스 인덱싱, 블록체인 

 

🪨 충돌 처리

만약 해시 함수에 의해 나온 결과 값이 같다면 어떻게 될까? 이러한 상황을 충돌이라고 부르며 하나의 버킷에는 2개의 값을 넣을 수 없기에 이러한 상황의 경우 충돌 처리를 반드시 해야한다.

• 체이닝으로 처리하기
  • 충돌이 발생한 경우 링크드리스트로 충돌한 데이터를 연결하는 방식으로 충돌을 간단히 해결하지만 해시 테이블의 공간을 덜 사용하여 공간 활용성이 떨어지고, 충돌 횟수에 따라 링크드리스크의 길이가 길어져 검색 성능(최악 O(N)의 시간복잡도)이 떨어진다는 단점이 있다.

체이닝으로 처리하기

 

• 개방 주소법으로 처리하기
  • 빈 버킷을 찾아 충돌값을 삽입하는 방식으로 체이닝보다 해시 테이블의 메모리를 효율적으로 사용 빈 버킷을 찾는 방법은 선형 탐사 방식으로 일정 간격으로 빈 버킷을 찾을 때까지 이동하는 방식과 이중 해싱 방식 두 개의 해시 함수를 사용해서 충돌이 발생 시 어떻게 위치를 정할지 결정하는 함수를 추가하는 것이 있다.

개방 주소법으로 처리하기