Searching (3)

[EKOO의 JAVA를 이용한 자료구조:9회] Searching (3)

저자:EKOO| 날짜: 2005년 06월 17일

 

Open-Address Hashing

 Hashing이란 각각의 원소들에 유일한 Key값을 하나씩 배당하여 보다 용이한 검색이 가능하도록 하는 알고리즘 입니다. Hashing은 data에 대해서 추가적인 정보(즉 Key)를 이용하여 더 빠른 검색을 할 수 있도록 하는 것 입니다. data에 대한 정보가 아무것도 없는 Serial Search 보다 더 빠른 검색시간을 제공하는 알고리즘 입니다. 이 강좌에서는 그 Key를 배열의 인덱스들중에서 고르도록 하겠습니다.

 배열에 넣는 key값은 배열 전체의 size와 data값을 이용하여 결정합니다. 이 강좌에서는 data % size 로 나눠서 나오는 나머지를 key값으로 배정합니다. 만약 100을 넣는다면? [0]에 100이 들어가게 되겠죠? 506이라면 [6]에 들어가게 될 것입니다. 789라면 [89] 에 값이 들어가게 되겠죠.

 문제는 나머지가 같은 데이터가 존재한다면 data를 넣을 공간이 없게 된다는 것입니다. 이런 경우를 Collision 이라고 하는데, 이것을 해결하기 위해서는 밑의 그림과 같은 방법을 사용합니다.

[그림 5] Hashing에서 Key값의 Collision이 발생한 경우
 위의 그림처럼 Collison을 해결할 수 있습니다. 그럼 찾을때는 어떻게 하면 될까요? 일단 찾는 데이터의 Key값을 구해내고 나서 해당 Key(index)부터 하나씩 순차적으로 내려가면서 찾으면 됩니다. Serial Search의 방법과 매우 비슷하지만, Key를 이용하여 Hashing을 하여 데이터를 저장하면 맨 처음부터 찾는 쓸데없는 수고를 덜 수 있으므로 검색하는데 더 적은 시간을 들여서 작업을 완료 할 수 있게 됩니다.

 물론 Collison을 해결하는 방법이 위처럼 Sequential한 방법만이 있는것은 아닙니다. 하지만 여기서는 Collison이 발생했을때 그것을 해결해야만 한다는것이 더욱 중요하기 때문에 더 많은 Collison해결 방법을 원하시는분은 더 찾아보시면 많은 도움이 되실 것 입니다.

&nsbp;하지만.. 이런식으로 Sequential한 방법을 사용하다가 만약에라도 더이상 값을 넣을 공간이 없다면 어떻게 될까요? 이런 자료구조를 사용한 프로그램은 동작을 제대로 하지 않게 되겠죠. 그렇기 때문에 미리 충분한 크기를(1.5 ~ 2배) 잡아주는 작업이 필요하게 됩니다.

 위와 같이 300이라는 데이터를 삽입한 후에 나머지가 1인 data (301, 401...)를 입력하게 되면 역시나 Collision이 발생하게 되겠죠? 그렇게 되면 역시 위와같은 방법을 이용하여 Collision을 해결하면 됩니다.

Chained Hashing

 Hashing에는 Collision이라는 문제가 있습니다. 자료의 수가 적다면 Collision이 많이 발생해도 나중에 검색할때 속도의 차이가 그다지 많지 않겠지만 자료가 많아질수록 그만큼 Collision도 많이 발생하여 Hashing을 이용하여 얻는 이득이 많이 사라지게 됩니다. 이것을 해결하기 위하여 하나의 key에 하나의 element만을 대응하던 기본 Hashing에서 Linked List를 이용한 Hashing을 사용할 수 있습니다. 이걸 바로 Chained Hashing 이라 하며 밑의 그림과 같은 구조로 이루어져 있습니다.

[그림 6] Chained Hashing의 기본 구조.
 전에 다뤘던 Open-Address Hashing에서는 하나의 Key에 하나의 element만이 들어가서 collison이 자주 발생하게 됩니다. 하지만 위와 같은 구조라면 Key가 중복되었을때 Linked List로 element들을 구성하게 됩니다. 이렇게 되면 Key값들에 대해서 Collision이 발생하였을때 더욱 효율적으로 List를 구성할 수 있습니다. 자료를 검색할 때도, 해당 Key의 Linked List만을 찾아보면 되므로 Open-Address Hashing보다 더욱 빠른 검색속도를 얻어낼 수 있게 됩니다.

 이건 좀 극단적인 경우긴 합니다만 Chained Hashing에서 Collision이 많이 발생해서 하나의 Node에 데이터가 주렁주렁 달려 있을 경우에는 Serial Search가 되어서 Chained Hashing을 쓰지 않은 것처럼 될 수도 있습니다.  실제 구현에 대해서는 여기서 따로 나타내는 것보다는 Linked List 를 다시 보셔서 스스로 구현해 보는것도 좋을 것이라고 생각됩니다.

강좌를 끝마치며...

 이번 강좌는 자료구조의 구현만을 다룬 강좌가 아니었습니다. 처음에 나온 Serial Search, Binary Search는 하나의 Algorithm이고, 뒤에 나온 Open-Address Hashing, Chained Hashing은 또 하나의 자료구조 라고 볼 수 있습니다.

 자료구조를 배우는 목적이, 자료들을 쉽게 관리하고 정리하는것이 목적 이라 한다면 "Search"역시 중요한 하나의 Subject이므로 이 강좌고 독자분들께 많은 도움이 되었으면 합니다. 그럼 다음강좌에서 뵙도록 하겠습니다. 그동안 건강하세요~.