[면접 준비 - Java]해시, 그리고 해시 자료구조

Hash

 

배열은 빠른 검색 속도를 가지고 있으나 삽입/삭제 시 많은 비용이 소모된다.

 

이를 극복한 LinkedList는 삽입/삭제의 비용이 적지만 데이터가 많아질수록 검색에 비용이 많이 든다.

 

해시는 이를 극복하기 위해 도입된 개념이다.

 

해시, 해시 함수(Hash Function)란 임의의 길이를 갖는 임의의 데이터를 받아

 

고정된 길이의 데이터를 리턴하는 단방향 함수를 말한다.

 

가장 쉬운 예로는 나머지 연산자(%)가 있을 수 있겠다.

 

해시 함수의 특징은 아래와 같으며,

 

• 비교적 간단한 알고리즘으로 시스템 자원을 덜 소모한다, 즉 해시값 생성에 많은 시간이 들지 않는다.
• 해시값을 해독할 때는 많은 시간이 든다.
• 같은 입력 값에 대해선 같은 출력 값이 보장되며, 출력 값은 고르게 분포한다.
• 입력값이 아주 조금만 변해도(abcd1 → abcd2) 출력 값은 크게 달라진다(이를 눈사태 효과라 한다).
  
  
  • MD5("The quick brown fox jumps over the lazy dog") = 9e107d9d372bb6826bd81d3542a419d6
  • MD5("The quick brown fox jumps over the lazy dog.") = e4d909c290d0fb1ca068ffaddf22cbd0

이와 같은 특성 때문에 암호화에 많이 사용되는 알고리즘이기도 하다.

 

자료구조에서의 해시는 색인이 그 목표이기 때문에 더욱 간단한 알고리즘을 가지고 있으며,

 

데이터 삽입/삭제 시 기존 데이터에 영향을 주지 않기 때문에 색인을 통해 빠른 처리가 가능하고

 

역시 임의의 데이터를 고정된 길이로 매핑하는 특성상 빠른 검색이 가능해진다.

 

추가로 매핑 전의 데이터를 키, 매핑 이후의 데이터를 해시 코드, 이 과정을 통틀어 해싱이라고 부른다.

 

비교적 간단한 알고리즘의 특성상 데이터의 양이 많아질수록 충돌 확률이 빠르게 증가하며 성능이 떨어지는 특징이 있으며,

 

충돌 방지를 위해서는 충돌값 뒤에 노드를 만들어 LinkedList, 혹은 Tree를 구성하는 방법과(Separate Chaining, 자바)

 

다시 해싱을 해서 비어있는 값에 배정하는 방법이 사용되고(Open Addressing)

 

성능 하락을 방지하기 위서는 데이터 수용률이 일정 범위(0.75)를 넘어서면 버킷의 길이를 늘이도록 구성되어 있다.

 

다만 이는 새로운 인덱싱을 포함하고 비용이 굉장히 많이 드는 작업이기 때문에

실시간으로 빠르게 작업해야 하는 경우 메모리를 소모해 점진적으로 옮기는 방법,

혹은 분산 환경에서 일관성을 유지하기 위해 해시의 비트를 1 증가시키고 저장공간을 두 배로 늘린 뒤

점진적으로 옮기는 Consistent Hashing 방법을 사용한다.

 

Hash Data Structures

 

해시를 사용하는 대표적인 자료구조는 HashMap이 있다.

 

생성 시 특별한 설정을 하지 않으면 해시맵의 버킷은 기본적으로 크기가 16으로 배정되며,

 

위에서 봤듯이 내부적으로는 배열로 이루어져 있다.

 

계속해서 Thread-safe 한 해시맵이라 볼 수 있는 해시 테이블이 있으며 LinkedList와 결합된 Linked-HashMap, 

 

내부적으로 해시맵을 사용하는 HashSet, LinkedHashSet 등의 자료구조도 많이 사용된다.