Part of your World

해싱(Hashing)은 키-값 쌍을 저장하고 검색하는 데 사용되는 방법이다. 해싱은 데이터 구조인 해시 테이블을 사용하여 데이터를 저장하고 검색한다.

해싱의 핵심 개념은 해시 함수이다. 해시 함수는 키를 입력으로 받아 정수인 해시 코드를 반환한다. 이 해시 코드는 저장된 데이터의 인덱스로 사용된다. 따라서 해시 함수는 키-값 쌍을 해시 테이블의 특정 위치에 연결한다.

해싱은 일반적으로 다음과 같은 시나리오에서 매우 효과적이다:

1. 데이터의 크기가 매우 큰 경우: 해싱은 키에 대한 고정 크기의 해시 코드를 생성하므로, 데이터의 크기에 관계없이 데이터를 저장하고 검색하는 데 매우 효율적이다.
2. 빠른 검색이 필요한 경우: 해싱은 평균적으로 O(1)의 시간 복잡도를 가진다. 즉, 데이터의 크기에 관계없이 일정한 검색 시간을 보장한다.

그러나 해싱에는 몇 가지 단점도 있습니다. 먼저, 해시 충돌이 발생할 수 있다. 이는 두 개 이상의 키가 동일한 해시 코드를 가질 때 발생하는데, 이 문제를 해결하기 위한 여러 전략이 있다. 또한 해시 테이블은 메모리를 많이 사용하는 경향이 있으며, 이는 메모리가 제한적인 시스템에서 문제가 될 수 있다.

Java에서는 HashMap이라는 내장된 클래스를 사용하여 해싱을 구현할 수 있다. HashMap 클래스는 키와 값을 저장하는 데이터 구조로서, 키는 고유한 값이어야 한다.

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        // HashMap 객체 생성
        HashMap<String, Integer> map = new HashMap<>();

        // 키-값 쌍 추가
        map.put("Apple", 10);
        map.put("Banana", 20);
        map.put("Cherry", 30);

        // 키를 사용하여 값을 검색
        int value = map.get("Banana");
        System.out.println("Banana의 값: " + value);

        // 키를 사용하여 값 수정
        map.put("Banana", 25);

        value = map.get("Banana");
        System.out.println("수정된 Banana의 값: " + value);
    }
}

HashMap 객체인 **map**은 문자열 키와 정수 값 쌍을 저장한다. put 메소드를 사용하여 키-값 쌍을 추가하고, get 메소드를 사용하여 키에 해당하는 값을 검색한다. 해시맵에서는 키를 사용하여 값을 직접 접근할 수 있으므로, 검색 작업은 빠르게 수행된다.

이진 검색(Binary Search)은 정렬된 배열에서 특정 값을 효율적으로 찾는 검색 알고리즘이다.

이진 검색의 작동 원리는 다음과 같다:

1. 먼저, 배열의 중간 인덱스에 위치한 값을 확인한다.
2. 이 값이 찾고자 하는 값과 동일한지 확인한다.
3. 만약 동일하다면, 검색을 종료하고 해당 인덱스를 반환한다.
4. 만약 찾고자 하는 값이 중간 값보다 크다면, 중간 인덱스를 기준으로 왼쪽 부분(작은 값들이 있는 부분)을 버리고 오른쪽 부분(큰 값들이 있는 부분)에서 검색을 계속한다.
5. 만약 찾고자 하는 값이 중간 값보다 작다면, 중간 인덱스를 기준으로 오른쪽 부분(큰 값들이 있는 부분)을 버리고 왼쪽 부분(작은 값들이 있는 부분)에서 검색을 계속한다.
6. 이렇게 반복하면서 검색 범위를 반으로 줄여가며 찾고자 하는 값을 찾는다.

이진 검색은 데이터가 정렬되어 있어야 사용할 수 있으며, 그 특성상 선형 검색보다 훨씬 빠르게 검색을 수행할 수 있다. 이진 검색의 시간 복잡도는 O(log n)이다. 이는 n개의 요소를 가진 리스트에서, 이진 검색이 한 번 실행될 때마다 검색해야 할 요소의 수가 절반으로 줄어들기 때문입니다. 이는 큰 데이터셋에서 매우 효율적이다.

class BinarySearch {
    // 이진 검색 메소드
    int binarySearch(int arr[], int x) {
        int l = 0, r = arr.length - 1;
        // 왼쪽 인덱스(l)가 오른쪽 인덱스(r)보다 작거나 같을 동안 반복
        while (l <= r) {
            // 중간 인덱스(m)를 계산
            int m = l + (r - l) / 2;
 
            // x가 배열의 중간 요소와 같은지 확인
            if (arr[m] == x)
                return m; // 같으면 x의 인덱스인 m 반환
 
            // x가 중간 요소보다 크면, 왼쪽 절반을 무시
            if (arr[m] < x)
                l = m + 1;
 
            // x가 중간 요소보다 작으면, 오른쪽 절반을 무시
            else
                r = m - 1;
        }
 
        // 위 반복문을 통과했는데도 리턴이 안되었다면, x는 배열에 없는 것
        return -1; // 그래서 -1 반환
    }
 
    public static void main(String args[]) {
        BinarySearch bs = new BinarySearch();
        int arr[] = {2, 3, 4, 10, 40}; // 검색 대상 배열
        int x = 10; // 찾고자 하는 값
        // binarySearch 메소드를 사용하여 x의 위치 검색
        int result = bs.binarySearch(arr, x);
        // x의 위치에 따라 결과 출력
        if (result == -1)
            System.out.println("배열에 원소가 없습니다."); // x가 배열에 없다면
        else
            System.out.println("원소가 " + result + "번째 인덱스에 있습니다."); // x가 배열에 있다면
    }
}

주어진 배열 **arr**에서 값 **x**를 찾는 binarySearch 메소드를 정의하고 있다. **x**가 배열에 있으면 해당 인덱스를, 없으면 **-1**을 반환한다.

binarySearch 메소드는 배열의 중앙에 있는 값이 **x**와 같은지 확인하고, **x**가 중앙값보다 크면 왼쪽 반을 무시하고, **x**가 중앙값보다 작으면 오른쪽 반을 무시하는 방식으로 동작한다. 이런 방식으로 검색 범위를 절반씩 줄여나가면서 **x**를 찾는다.

선형 검색(Linear Search)은 가장 간단한 형태의 검색 알고리즘이다.

이 알고리즘은 주어진 데이터 집합에서 특정 값을 찾기 위해 처음부터 끝까지 순차적으로 검색하는 방식을 사용한다. 순차적으로 하나씩 확인하기 때문에 선형 검색이라는 이름이 붙었었다.

아래는 선형 검색의 단계이다.:

1. 배열의 첫 번째 요소부터 시작하여, 특정 값이 발견될 때까지 각 요소를 차례대로 확인한다.
2. 만약 해당 값이 발견되면, 그 위치(또는 인덱스)를 반환한다.
3. 만약 배열의 끝까지 검색하고도 해당 값이 없다면, 검색 실패를 의미하는 값을 반환한다. (예: -1)

선형 검색의 가장 큰 단점은 시간 복잡도가 O(n)이라는 점이다. 즉, 데이터의 양이 증가함에 따라 검색 시간도 비례하여 증가하게 된다. 따라서 큰 데이터 집합에서는 효율적이지 않을 수 있다. 하지만 데이터가 작거나, 데이터가 정렬되어 있지 않은 경우에는 간단하고 효율적으로 사용할 수 있는 알고리즘이다.

class LinearSearchExample {
    // 선형 검색 메소드
    static int linearSearch(int[] arr, int x) {
        int n = arr.length;
        for(int i = 0; i < n; i++) {
            if(arr[i] == x)
                return i; // 요소가 발견되면 해당 인덱스 반환
        }
        return -1; // 요소가 발견되지 않으면 -1 반환
    }

    public static void main(String args[]) {
        int[] arr = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170};
        int x = 110; // 찾고자 하는 값
        int index = linearSearch(arr, x);
        if(index == -1)
            System.out.println("Element is not present in the array");
        else
            System.out.println("Element found at position: " + index);
    }
}

linearSearch 메소드는 배열과 찾고자 하는 값을 인수로 받아서 배열의 각 요소를 처음부터 끝까지 순차적으로 비교한다. 만약 찾고자 하는 값이 배열의 요소와 일치하면 해당 요소의 인덱스를 반환한다. 만약 배열을 모두 탐색했음에도 찾고자 하는 값이 없으면 -1을 반환한다.