초보 자바 프로그래밍(28) - 해시검색 (Hash Search)

해시 검색 대표 이미지

🔖 INDEX

 

 

해시 검색(hash search)은 해시 테이블(hash table)이라는 자료 구조를 사용하여 빠르게 원하는 값을 찾을 수 있는 검색 방법입니다. 해시 테이블은 키(key)와 값(value)을 저장하는 데 사용되며, 해시 함수(hash function)를 사용하여 키를 해시 값으로 변환합니다. 해시 값은 해시 테이블 내의 인덱스로 사용되어 효율적인 검색, 삽입 및 삭제를 가능하게 합니다.

 

해시 검색의 작동 방식 및 구현 예제

해시 검색의 작동 방식은 다음과 같습니다:

1. 해시 함수를 사용하여 키를 해시 값으로 변환합니다.
2. 해시 값으로 해시 테이블 내의 인덱스를 찾습니다.
3. 인덱스에 저장된 값을 검색, 삽입 또는 삭제합니다.

자바에서 해시 검색 알고리즘을 구현할 때, HashMap 클래스를 사용할 수 있습니다. HashMap은 키-값 쌍을 저장하고 검색하는데 사용되는 자바의 기본 해시 테이블 구현입니다.

 

자바에서 HashMap을 사용하여 간단한 해시 검색 알고리즘을 구현하는 예제 코드는 다음과 같습니다:

import java.util.HashMap;

public class HashSearchExample {
    public static void main(String[] args) {
        // HashMap 객체를 생성합니다.
        HashMap<String, Integer> hashMap = new HashMap<>();

        // 데이터를 HashMap에 추가합니다.
        hashMap.put("Alice", 25);
        hashMap.put("Bob", 30);
        hashMap.put("Cathy", 35);
        hashMap.put("David", 40);

         // HashMap에서 key를 검색합니다.
        String searchKey = "Cathy";

        if (hashMap.containsKey(searchKey)) {
            int value = hashMap.get(searchKey); // key에 해당하는 값을 가져옵니다.
            System.out.println("The value for the key '" + searchKey + "' is: " + value);
        } else {
            System.out.println("The key '" + searchKey + "' is not in the HashMap.");
        }
    }
}

이 예제에서는 String을 키로, Integer를 값으로 사용하여 HashMap을 생성합니다. put 메서드를 사용하여 키-값 쌍을 해시 테이블에 삽입하고, containsKey 메서드를 사용하여 특정 키가 해시 테이블에 존재하는지 확인합니다. 만약 키가 존재하면, get 메서드를 사용하여 해당 키에 연결된 값을 검색합니다.

 

 

해시 검색의 특징

해시 검색의 장점은 다음과 같습니다:

• 빠른 검색 속도: 해시 검색의 시간 복잡도는 평균적으로 O(1)입니다. 즉, 해시 테이블이 충분히 크고 해시 함수가 좋은 성능을 보이는 경우 거의 일정한 시간 안에 검색이 가능합니다. 이는 큰 데이터 세트에서도 효율적입니다.
• 키-값 쌍 저장: 해시 테이블은 키와 값을 함께 저장하므로, 키에 대응하는 값을 쉽게 찾을 수 있습니다. 이는 매핑 관계를 가지는 데이터를 다루기에 적합합니다.
• 삽입 및 삭제 효율: 해시 테이블은 검색뿐만 아니라 삽입 및 삭제 작업도 평균적으로 O(1)의 시간 복잡도로 수행할 수 있습니다.

 

해시 검색 사용 시 다음과 같은 내용을 주의해야 합니다:

• 충돌(Collision) 처리: 해시 함수가 서로 다른 키에 대해 동일한 해시 값을 생성하는 경우, 충돌이 발생합니다. 충돌을 해결하기 위한 여러 가지 방법이 있지만, 처리 방법에 따라 해시 테이블의 성능에 영향을 줄 수 있습니다. 대표적인 충돌 해결 방법으로는 개별 체이닝(separate chaining)과 개방 주소법(open addressing)이 있습니다.
• 해시 함수의 중요성: 좋은 해시 함수는 키를 고르게 해시 테이블에 분포시켜 충돌을 최소화하고 성능을 최적화합니다. 반면에 나쁜 해시 함수는 충돌이 빈번하게 발생하여 해시 테이블의 성능이 저하될 수 있습니다.
• 공간 효율성: 해시 테이블은 충분한 공간을 가지고 있어야 충돌을 줄이고 성능을 높일 수 있습니다. 그러나 높은 공간 효율성을 위해서는 해시 테이블의 크기를 적절하게 조절해야 합니다. 너무 큰 해시 테이블은 메모리 낭비를 초래할 수 있고, 너무 작은 해시 테이블은 충돌이 빈번하게 발생하여 성능이 저하될 수 있습니다.
• 해시 테이블 리사이징: 테이블의 크기를 증가시키거나 줄이는 작업을 리사이징(resizing)이라고 합니다. 리사이징은 해시 테이블의 로드 팩터(load factor)에 따라 수행됩니다. 로드 팩터가 지정된 임계값보다 높으면 테이블의 크기를 증가시키고, 낮으면 테이블의 크기를 줄입니다. 리사이징은 해시 테이블의 성능에 영향을 주는 중요한 작업이지만, 잘못 관리되면 성능 저하를 초래할 수 있습니다.
• 순서 보장이 없음: 해시 테이블은 키-값 쌍을 저장할 때 순서를 보장하지 않습니다. 따라서 키-값 쌍이 저장된 순서대로 검색이 필요한 경우, 해시 검색이 적절하지 않을 수 있습니다. 이런 경우에는 다른 자료 구조(예: TreeMap)를 사용해야 합니다.

 

 

해시 검색의 충돌 해결 방법

개별 체이닝과 개방 주소법 중 어떤 방법을 사용할지는 해시 테이블의 특성, 데이터의 분포, 성능 및 메모리 요구사항에 따라 결정해야 합니다. 각 충돌 해결 전략은 다음과 같은 상황에서 적합합니다:

 

개별 체이닝(Separate Chaining)

• 데이터의 분포가 불균형하거나 예측이 어려운 경우
• 메모리 사용에 대한 제약이 덜 중요한 경우
• 해시 테이블의 로드 팩터가 높아도 성능 저하를 최소화하려는 경우

2023.05.02 - [JAVA] - 초보 자바 프로그래밍(29) - 개별체이닝 (Separate Chaining)

초보 자바 프로그래밍(29) - 개별체이닝 (Separate Chaining)

 

개방 주소법(Open Addressing)

• 데이터의 분포가 균일하고 예측 가능한 경우
• 메모리 사용에 대한 제약이 중요한 경우
• 캐시 지역성을 최적화하여 성능을 높이려는 경우

2023.05.02 - [JAVA] - 초보 자바 프로그래밍(30) - 개방주소법 (Open Addressing)

초보 자바 프로그래밍(30) - 개방주소법 (Open Addressing)

 

충돌 해결 전략을 선택할 때 각 방법의 장단점을 고려하여 해시 테이블의 요구 사항과 목표에 가장 적합한 방법을 사용하면 됩니다. 또한, 해시 함수의 품질과 해시 테이블의 크기를 적절하게 조절하여 충돌을 최소화하고 전체적인 성능을 높일 수 있습니다.