[알고리즘][탐색] - 선형 탐색 & 이진 탐색 & 해시 탐색

탐색 알고리즘이란?

저장된 데이터들 중 원하는 값을 찾는 알고리즘

 

 

선형 탐색 알고리즘

보편적으로 정렬되지 않은 배열이나 리스트에 사용되며

단순하게 맨 앞이나 뒤에서 시작하여 순차적으로 탐색하는 알고리즘

 

첫 번째 원소가 정답인 경우: 1

마지막 원소가 정답인 경우: n

∴  O(n) 의 시간 복잡도를 가진다

 

Linear Search Algorithm

 

이진 탐색 알고리즘

정렬된 배열이나 리스트에 사용되며 리스트의 중간값과 찾으려는 값의

대소를 비교하여 탐색 범위를 반으로 줄여가며 값을 탐색하는 알고리즘

 

(탐색하려고 하는 값이 정렬된 리스트의 중간값보다 크면 중간값을 포함한 하위값들은

탐색 대상에서 제외되며 중간값보다 작으면 상위값들은 탐색에서 제외된다)

 

첫 번째 원소가 정답인 경우: 1

마지막 원소가 정답인 경우: log2(n)

∴  O(log2(n)) 의 시간 복잡도를 가진다

 

Binary Search Algorithm

 

해시 탐색 알고리즘

Key 와 Value 로 매핑하는 데이터 구조인

해시 테이블을 이용하여 탐색하는 알고리즘

 

배열의 인덱스로 값을 저장하거나 검색하는 데 사용되는

Key 는 해시 함수를 통해 해시 값으로 변환된다

 

해시 함수

아래는 가장 기본적인 해시 함수의 예시이다

Key 와 해시 테이블의 크기를 매개 변수로 받고

Key 의 각 문자열의 유니코드 값을 더한 값을

해시 테이블의 크기로 나눈 나머지를 해시 값으로 사용

 

저장

계산된 해시 값에 따라 키와

그에 대응하는 값을 해시 테이블에 저장

 

탐색

탐색하고자 하는 키에 대해 해시 함수를 적용하여

해시 값을 계산하여 해시 테이블에서 대응하는 값을 탐색

Example of Basic Hash Function

public int hashFunc(String key, int hashTableSize) {
    int hashValue = 0;
    int keyLength = key.length();
    for (int i = 0; i < keyLength; i++) {
        hashValue += key.charAt(i);
    }
    return hashValue % hashTableSize;
}

String key = "exampleKey";
int hashTableSize = 10; 
int hashValue = hashFunc(key, hashTableSize);

// print result
System.out.print("The hash value of " + key + " is: " + hashValue);

 

하지만 해당 해시 함수는 충돌을 처리하지 않으므로

두 개의 다른 키가 같은 해시 값을 가질 수도 있다

 

이를 처리하기 위해 체이닝 또는 오픈 어드레싱 등

해시 충돌을 처리하는 추가적인 로직이 필요하다

 

일반적으로 Key 를 해시 함수로 변환하여

직접 인덱스에 접근하여 계산하기 때문에

이론적으로는 상수 시간에 데이터에 접근할 수 있다

 

첫 번째 원소가 정답인 경우: 1

마지막 원소가 정답인 경우: n

∴  O(n) 의 시간 복잡도를 가진다