Hash 기본 개념과 구조

Hash의 정의

배열은 검색 속도가 빠르나 데이터 삽입/삭제 시 속도가 느립니다. LinkedList는 삽입 삭제 시 인근 노드의 참조 값만 수정해서 속도가 빠르나 순회 검색만 가능하여 데이터가 많아질수록 속도가 느려집니다. 이러한 한계를 극복하기 위해 제시된 방법이 Hash입니다.

 

특징

내부적으로 배열을 사용하여 데이터를 저장해 검색 속도가 빠릅니다. 데이터의 삽입/삭제 시 해시 알고리즘을 이용하여 데이터와 연관된 고유한 숫자를 만들어 인덱스로 사용합니다. 해시가 내부적으로 사용하는 배열을 HashTable이라고 하며 크기에 따라서 성능 차이가 납니다.

 

Hash Method(해시 메서드)

해시는 HashTable을 사용하여 데이터를 저장하는데, 이때 인덱스를 구하기 위해 해시 메서드를 사용하여 고유의 숫자 값인 해시 코드(Hash Code)를 얻습니다.

 

HashMethod 구현 방법

해시 메서드는 나머지 연산자를 이용하여 해시 코드를 구합니다.

//a=97, b=98, c=99 일때 HashTable의 크기가 10이면 다음과 같이 저장된다.
97 % 10 = 7
98 % 10 = 8
99 % 10 = 9

list[7]='a';
list[8]='b';
list[9]='c';

 

해시 충돌

해시 충돌을 최소화하기 위해 테이블의 크기를 소수로 사용해 만듭니다. 충돌을 해결하는 방법은 개방 주소법과 분리연결법이 있습니다.

 

개방주소법

배열만을 사용하여, 저장 인덱스가 겹 칠경 우 해당 인덱스의 옆 인덱스에 저장하는 방식입니다. 옆에 인덱스와 데이터 충돌이 일어나면 다시 옆 인덱스에 저장합니다. 충돌 데이터가 많이 발생하면 성능에 심각한 문제가 발생합니다.

 

분리 연결법

HashTable에 연결 리스트에서 사용하는 노드 객체를 저장합니다. HashTable의 셀마다 연결 리스트를 하나씩 저장하고 충돌이 발생하는 데이터는 연결 리스트의 다음 노드에 추가합니다. 데이터를 검색할 때는 HashTable의 인덱스를 찾은 후 셀에 연결된 리스트를 순차적으로 탐색하며 찾으려는 HashCode와 저장된 노드의 HashCode를 비교하는 것입니다.