자료구조 - Searching

searching을 하기 위해서 가장 간단한 방법은 array의 가장 앞에서 부터 우리가 찾고 싶은 원소가 나올 때 까지 탐색하는 linear searching을 사용하는 것이다.

하지만 이는 최악의 경우 배열의 모든 원소를 다 봐야하기 때문에 효율성이 좋지 못하다.

따라서 linear searching을 개선하여 효율성을 높여야 하는데 최근에 호출된 요소는 다시 호출될 가능성이 높다는 아이디어를 활용하여 호출한 요소를 array의 가장 앞으로 불러오거나 한 칸씩 앞으로 오게 배치하는 방법이 있다.

만약 array가 정렬된 경우 binary search를 사용하면 모든 요소를 확인하지 않고 $\log_2 (N)$의 시간 복잡도로 탐색을 할 수 있어 좋다.

다만 정렬되어 있지 않다면 정렬도 따로 해줘야 하기 때문에 시간 복잡도가 더 많이 걸릴 가능성이 있다.

linear searcing의 경우 N번의 탐색이 필요하고, binary searching의 경우 정렬이 되어있지 않다면 정렬을 해줘야 하고 정렬이 되어있더라도 $\log_2 (N)$의 시간 복잡도가 걸리기 때문에 많은 시간이 탐색에 걸린다.

따라서 이러한 시간을 줄여 $O(1)$로 탐색을 하기 위해 hashing을 사용하면 된다.

hashing은 hash함수를 이용하여 원소들을 각각 특정 위치에 배치하여 searching을 할 때 바로 찾고자하는 원소가 있는 부분을 찾는 방식을 의미한다.

간단한 예시를 생각하면 숫자를 hashing한다고 생각했을 때 0부터 99까지의 index를 가지고 있는 배열이 있다고 하면 요소를 100으로 나눈 나머지에 해당하는 값의 위치에 요소들을 저장하면 된다.

즉, 만약 50704가 입력값으로 주어지면 100으로 나눈 나머지인 4에 해당하는 위치에 값을 저장하여 만약 50704를 searching하면 4번 인덱스를 확인하면 되는 것이다.

hashing을 수행하면서 가장 문제가 되는 부분이 collision으로 저장해야할 위치에 이미 원소가 저장되어있는 경우 이러한 문제가 발생한다.

충돌을 회피하는 가장 간단한 방법으로 만약 저장해야할 위치에 이미 다른 원소가 있으면 비어있는 위치가 나올 때 까지 저장하는 위치의 다음 index를 찾는다.

이러한 방법의 문제는 중간에 배열에서 원소를 지우게 될 경우이다.

특정 원소가 있는지 없는지 판단을 할 때 해당 원소를 나타내는 index에 접근을 하고 만약 다를 경우 이미 다른 원소가 있어 다른 곳에 저장되었을 가능성이 있어 비어있는 영역이 나올 때 까지 탐색을 하여 찾고자하는 원소가 있는지 없는지를 파악한다.

하지만 중간에 원소가 지워지면 배열안에 분명히 원소는 있지만 중간에 원소를 지워 연결이 끊겨져 원소가 배열에 있는지 없는지 확인을 할 수 없게 된다.

따라서 이러한 문제를 해결하기 위해서 만약 원소를 지우게 된다면 뒤에 연결되어있는 원소들을 한 칸씩 당겨서 이어지게 만들어야 한다.

다만 이러한 과정을 계속 반복할 경우 결과적으로 데이터들이 clustering되는 문제가 생겨 hash들은 기본적으로 고르게 분포해야 비어있는 영역이 가까이 있어 탐색에 유리한 장점이 있는데 이러한 장점이 사라져 않좋은 상황이 되는 문제가 생긴다.

rehashing은 말 그대로 충돌이 발생할 경우 새로운 hash함수를 사용하여 원소를 삽입하는 것을 의미한다.

linear probing도 일종의 rehashing이긴 하지만 이는 성질이 비슷한 hash함수를 사용하여 큰 이득을 보지 못한 경우로 다른 hash함수를 사용할 때 다른 성질의 함수를 사용하면 비어있는 공간이 많아져 clustering을 줄일 수 있다.

buckets은 단순히 hash함수를 통해 배정받은 영역에 하나의 원소만 저장하는 것이 아니라 bucket을 통해 여러개의 원소들을 해당 영역에 동시에 저장 가능하게 하는 구조이다.

이러한 구조는 bucket이 크면 사용하지 않는 메모리 공간이 커서 비효율적이 되고, 만약 bucket이 작으면 위의 방식을 또 사용해야 하기 때문에 큰 이점이 없는 방식이다.

chaining은 linked list를 통해서 할당 받은 영역의 원소들을 연결한 것으로 필요한 만큼만 이어주면 되기 때문에 메모리를 의미 없게 사용하는 부분이 적다.

활동바코