해시테이블 자료구조

해싱이란?

 해싱은 키값에 연산을 통해 해당 키값에 할당된 항목에 직접 접근 가능한 구조를 말하며 이러한 자료구조를 

해시테이블이라고 한다. 또한 해시테이블을 이용한 탐색을 해싱이라고 한다.

해시함수?

 해시테이블에 데이터를 저장할때 여러 알고리즘을 통해서 데이터의 고유한 숫자값을 만들어 인덱스로 사용하게 

되는데 이 알고리즘을 구현한 메소드를 해시 함수라고 한다. 

해시함수의 알고리즘은 여러가지가 있지만 가장 기본적인 것! 나머지 연산법에 대해 알아보자.

예를 들어  "a", "b", "c"의 해시코드가 각각 97, 98 ,99 라고 하고 해시테이블의 크기가 10이라고 했을 때 테이블에 

저장될 인덱스는 다음과 같다.

97 % 10 = 7

98 % 10 = 8

99 % 10 = 9

즉, Hash Table의 인덱스 7에는 "a"를 저장하고 8에는 "b", 9에는 "c"를 저장하는 방식이다.

이후에 "a"를 검색할 때에는 "a"의 hashCode를 가지고 나머지 연산을 한 결과인 7번 인덱스를 바로 참조하여 

데이터를 꺼낼 수 있다.

해시충돌?

 해시충돌이란 해시테이블의 동일한 인덱스에 값을 저장하려고 할때 생기는 충돌을 해시충돌이라고 한다. 예를 들어

4, 8, 12, 16, 20, 24, 28, 32 라는 해시코드를 가진 데이터가 있다고 했을 때 데이터를 저장하기 위해 해시테이블의 크기를 8로 지정했다면 테이블에 저장될 인덱스는 다음과 같다.

4 % 8 = 4

8 % 8 = 0

12 % 8 = 4

16 % 8 = 0

20 % 8 = 4

24 % 8 = 0

28 % 8 = 4

32 % 8 = 0

데이터를 저장하기 위한 인덱스가 0번과 4번에 집중되는 것을 볼 수 있다.

이처럼 해시코드가 다르더라도 나머지 연산을 한 결과는 같을 수 있으므로 해시테이블의 동일한 인덱스에 저장을 시도하려 할 경우 해시 충돌이 일어나게 된다.

이런 충돌을 최소화 하기 위한 방법으로는 나머지 연산의 값이 최대한 중복되지 않도록 테이블의 크기를 소수(prime number)로 만드는 것이다.

다음은 8보다 큰 소수인 11을 테이블의 크기로 지정했을 때 각 데이터들이 테이블에 저장될 인덱스 값이다.

4 % 11 = 4

8 % 11 = 8

12 % 11 = 1

16 % 11 = 5

20 % 11 = 9

24 % 11 = 2

28 % 11 = 6

32 % 11 = 10

이제는 충돌이 발생하지 않는다. 하지만 Hash Table의 크기를 소수로 만드는 것은 충돌을 줄이는 방법이지 해결하기 위한 방법은 아니다. 추가적으로 10을 저장하려고 한다면 10 % 11 = 10 로 되므로 이미 10번의 인덱스에는 32가 들어있기 때문에 충돌이 발생한다.

이처럼 충돌이 발생할 경우 이를 해결하기 위한 방법이 필요하며 충돌 해결 방법 중 분리연결법에 대해 알아보자

분리연결법?

 분리연결법은 해시테이블의 연결리스트에서 사용하는 노드 객체를 저장하는 것이다. 즉, 해시테이블의 버킷마다 

연결 리스트를 하나씩 저장하도록 하고 충돌이 발생하는 데이터는 연결리스트의 다음 노드로 계속 추가해 

가는 것이다.

      <분리연결법>

-끝-