해시(Hash) 기본 개념과 구조

1. 해시(Hash) 정의

 - 배열은 검색 속도가 빠르나 데이터 삽입/삭제 시 속도가 느립니다.

 - 링크드 리스트는 삽입 삭제시 인근 노드의 참조 값만 수정해서 속도가 빠르나 순회 검색만 가능하여 데이터가 많아질수록 속도가 느려집니다.

 - 이러한 한계를 극복하기 위해 제시된 방법이 해시(Hash)입니다.

 

2. 특징

 - 내부적으로 배열을 사용하여 데이터를 저장하여 검색 속도가 빠릅니다.

 - 데이터의 삽입/삭제 시 해시 알고리즘을 이용하여 데이터와 연관된 고유한 숫자를 만들어 인덱스로 사용합니다.

 - 해시가 내부적으로 사용하는 배열을 Hash Table 이라고 하며 크기에 따라서 성능 차이가 납니다.

 

3. 해시 메서드(Hash Method)

 - 해시는 Hash Table을 사용하여 데이터를 저장합니다.

 - 이때 인덱스를 구하기 위해 해시 메서드(Hash Method)를 사용하여 고유의 숫자 값인 해시 코드(Hash Code)를 얻습니다.

 

4. 해시 메서드 구현 방법

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

 

  * a=97, b=98, c=99 일때Hash Table의 크기가 10이면 다음과 같이 저장됩니다.

   97 % 10 = 7

   98 % 10 = 8

   99 % 10 = 9

  

   list[7] = 'a';

   list[8] = 'b';

   list[9] = 'c';

 

5. 해시 충돌

 - 해시 충돌을 최소하 하기 위해서 테이블의 크기를 소수로 사용해서 만듭니다.

 

 * 4 % 11 = 4

   8 % 11 = 8

   32 % 11 = 10 충돌!

   10 % 11 = 10 충돌!

 

 - 이러한 충돌을 해결하는 방법은 개방 주소법과 분리 연결법이 있습니다.

 

6. 개방 주소법

 - 배열만을 사용하며, 저장 인덱스가 겹칠 경우 해당 인덱스의 옆 인덱스에 저장하는 방식입니다.

 - 옆에 인덱스와 데이터 충돌이 일어나면 다시 옆 인덱스에 저장합니다.

 - 충돌 데이터가 많이 발생하면 성능에 심각한 문제가 발생합니다.

 

7. 분리 연결법

 - Hash Table 에 연결 리스트에서 사용하는 Node 객체를 저장합니다.

 - Hash Table의 셀마다 연결 리스트를 하나씩 저장하고 충돌이 발생하는 데이터는 연결 리스트의 다음 노드에 추가합니다.

 - 데이터를 검색할 때는 Hash Table의 인덱스를 찾은 후 셀에 연결된 리스트를 순차적으로 탐색하며 찾으려는 Hash Code와 저장된 Node의 Hash Code를 비교하는 것입니다.