Searching

메모리에 저장된 데이터를 탐색하는 방법은 여러 개가 있지만, 오늘은 아래 세 가지 경우만 고려해보자.

 

1. Serial Search

382759461

위 숫자에서 6을 탐색해보자.

순차탐색은 0번째 인덱스부터 6이 등장하는 7번째 인덱스까지 총 8번의 탐색과정을 거쳐야 6을 찾을 수 있다.

정렬되어 있지 않은 데이터 조합에 대해 사용할 수 있지만,

n개의 데이터에 대해 최대 n번의 탐색 시간이 걸린다는 치명적인 단점이 있다.

 

2. Binary Search

123456789

위 숫자에서 6을 탐색해보자.

이진 탐색의 경우 검색을 시작할 인덱스와 종료할 인덱스의 중간을 우선 탐색한다.

arr[(0+8)/2] = arr[4] = 5

이때, 6은 5보다 크기 때문에 4번째 인덱스의 왼쪽에서 다시 탐색한다.

arr[(5+8)/2] = arr[6] = 7

이때, 6은 7보다 작기 때문에 6번째 인덱스의 오른쪽에서 다시 탐색한다.

arr[(5+5)/2] = arr[5] = 6

결국 6을 찾아냈다.

이진탐색은 정렬되어있는 데이터 조합에 대해서만 사용할 수 있다는 단점이 있지만,

n개의 데이터에 대해 최대 logn번의 탐색 시간밖에 걸리지 않는다는 장점이 있다.

 

3. Hashing

해싱은 입력받은 데이터를 임의의 난수로 변환하는 방식으로

key value -> Hash Function -> index value로 변환되는 과정을 이용해 데이터에 접근한다.

이론적으로는 한 번의 탐색으로 데이터에 접근할 수 있다.

하지만, 서로 다른 key value이 같은 index value로 변환될 수 있다는 단점이 존재한다. (Collision problem)

이 단점을 극복하고자 나온 방법이 Open-Address Hashing Storage Algorithm이다.

 

3-A. Open-Address Hashing

Hash Function이 int(key/100) - 1과 같다고 해보자. (실제로는 이렇게 하면 안됨..!)

예로 들어 345라는 키 값이 들어오면 결과로 2가 출력되는 함수이다. (345는 인덱스 2에 저장한다는 뜻)

 

기존의 Hashing은 345, 346이라는 값이 들어오면 이미 인덱스 2에 345라는 값이 들어가 있기에

346이라는 값을 저장하는데 문제가 있었다.

하지만 Open-Address Hashing은 이미 인덱스 2에 345라는 값이 들어가 있다면

2의 다음(3번 인덱스)이 비어있는지를 검사하고, 비어있다면 인덱스 3에 346을 추가하는 방식으로 진행한다.

 

하지만 이 방식에는 데이터의 삭제 후 데이터를 탐색할 때 문제가 발생할 수 있다.

이 예시를 살펴보자.

 [2]   [3]   [4]
345 346 347

이 저장되어있다고 가정해보자.

346을 제거하는 경우 해시 함수에 의해 2가 반환되고,

인덱스 2에는 찾고자 하는 값이 없기에 다음 인덱스인 3을 탐색하여 값을 찾으면 제거한다.

 [2]   [3]   [4]
345         347

346을 제거한다면 3번 인덱스가 비어있는 상태가 되는데,

연속적으로 347을 제거한다고 해보자.

마찬가지로 해시 함수에 의해 2가 반환되고, 인덱스 2에는 찾고자 하는 값이 없기에 다음 인덱스인 3을 탐색하게 된다.

이때, 인덱스 3에는 값이 비어있으므로 탐색 효율을 위해 탐색을 중단하고 347은 없다고 판단한다.

즉, 인덱스 4번에 값이 존재함에도 불구하고 없다고 판단하는 논리 오류가 발생한다.

 

따라서 값이 비어있는 상태를 2개로 나누어서 관리해야 한다.

처음에는 모든 배열의 값을 NEVER_USED로 초기화한다.

그리고 값을 추가한 후 삭제된 값은 PREVIOUSLY_USED로 바꿔준다.

이렇게 하면 탐색을 할 때, PREVIOUSLY_USED를 읽을 경우 이어서 탐색하고,

NEVER_USED를 읽을 경우 탐색을 종료하면 된다.

 

이렇게 하면 빠르게 데이터를 읽고 쓰는 것이 가능해진다.

하지만, 사용하면 사용할수록 PREVIOUSLY_USED가 많아지기 때문에 탐색 시간이 점차 늘어날 수 있다는 단점이 존재한다.

이를 해결하기 위한 갖은 방법이 존재하지만, 본질적으로 O(1)의 탐색 시간을 구현하는 것은 불가능에 가까워 보인다.

 

우선 해시함수를 잘 설계하는 것이다.

어떠한 키 값이 들어오더라도 모두 다른 값이 나오는 해시함수를 구현한다면 가장 이상적일 것이다.

하지만, 아직까지 성공한 함수는 없고, 가장 널리 사용되는 방법만 소개하도록 하겠다.

a. Division Hash Function

    이 해시 함수는 간단히 key % table_size로 구성되어 있는데, 만약 table_size가 4k+3와 같은 소수 크기를 갖는다면,

    이론적으로 table_size보다 작은 키 값에 대해 유니크한 결과물이 도출된다.

b. Mid_Square Hash Function

c. Multiplicative Hash Function

 

다음으로는 Open-Address 방식을 설계하는 것이다.

앞서 설명했던 방법은 Linear Probing 방식으로 키 값에 해당하는 인덱스에 값이 이미 존재한다면 다음 인덱스를 탐색하는 방법이다.

하지만, 이 경우에는 특정 인덱스에 중복해서 충돌이 발생할 경우 성능이 점차 저하된다는 단점이 있다.

이를 극복하기 위해 나온 방법이 Double Hashing 방식이다.

이 방식은 해시함수를 2개 사용하는 방식인데,

첫 번째 해시함수는 데이터를 넣을 위치를 우선 정해주는 함수로 위에 소개한 해시함수와 같다.

두 번째 해시함수는 데이터를 넣을 위치에 이미 데이터가 들어있는 경우

다음을 탐색하는 것이 아닌, n스탭 다음을 탐색할 때 그 스탭의 길이 n을 정해주는 해시함수이다.

즉, 데이터의 충돌 시 그 충돌 위치를 분산하는 역할을 해시함수2가 수행하게 된다.

 

아래의 예시를 예로 들어보자.

 [2]   [3]   [4]
345 456 567

해시함수1: int(key/100) - 1
해시함수2: int(key/100) + 2

이때 346 값을 추가한다고 가정해보자.

해시함수1에 의해 2라는 값이 나와 인덱스 2에 추가해야 할 것이다.

하지만 인덱스 2번에 이미 값이 들어있기 때문에 해시함수2를 실행한다.

해시함수2에 의해 5라는 값이 나오게 되므로 2+5 = 7번째 인덱스를 탐색하고 비어있다면 346을 넣어주고,

비어있지 않다면 다시 7+5 = 12번째 인덱스를 탐색하게 된다.

 

하지만, 만약에 배열의 길이가 10이라면?

12%10 = 2이므로 2, 7을 무한 탐색하는 문제가 발생할 것이다.

이를 해결하기 위해 해시함수2의 결과는 테이블의 길이와 서로소여야 한다는 조건이 붙는다.

따라서 테이블의 길이를 4k+3의 소수 길이로 설정하면 반드시 서로소이기 때문에 테이블의 길이를 4k+3으로 설정하는 것이 좋다.

 

이 외에도 Chain Hashing이란 방법도 있는데, 단순히 배열에 다음에 데이터를 추가하는 것이 아닌,

배열에는 포인터만 저장하고, 그 아래로 연결 리스트를 주렁주렁 매다는 방법이다.