Kotlin 연습하기(12) - 해시 테이블

데이터를 빠르게 검색하거나 저장하는 일은 개발에서 필수적이다. (항상 이걸 어떻게 하면 잘할까 고민한다..) 이러한 작업을 가장 효율적으로 수행하는 자료구조 중 하나가 바로 해시 테이블(Hash Table) 이다.

 

해시 테이블은 키-값(Key-Value) 쌍으로 데이터를 저장하며, 거의 상수 시간(평균 O(1))에 데이터에 접근할 수 있는 강력한 도구이다.

 

 

해시 테이블이란?

해시 테이블은 위에서 언급한것과 같이 키(key)와 값(value)의 쌍으로 데이터를 저장하는 구조이다. 여기서 중요한 개념은 해시 함수(hash function)로, 입력된 키를 고정된 크기의 인덱스로 변환한다. 이 인덱스는 데이터를 저장할 배열의 위치를 결정한다.

 

예를 들어 "apple"이라는 키를 입력하면, 해시 함수는 "apple"을 정수 42와 같이 특정 인덱스로 변환한다. 그러면 해시 테이블은 "apple"에 대응하는 값을 저장하게 된다.

 

 

해시 함수(Hash Function) 

해시 함수는 키를 받아서 배열의 인덱스로 변환하는 역할을 한다. 좋은 해시 함수는 다음 조건을 만족한다.

• 결정론적 : 동일한 키는 항상 같은 해시 값을 반환해야 한다.
• 균등 분포 : 가능한 모든 키에 대해 인덱스가 균등하게 분포되어 충돌을 최소화한다.
• 빠른 계산 : 해시 함수는 빠르게 계산되어야 하며, 전체 성능에 큰 영향을 주지 않아야 한다.

 

해시 함수가 서로 다른 키에 대해 같은 인덱스를 반환하는 경우 이를 충돌(collision)이라고 한다. 충돌은 해시 테이블에서 피할 수 없는 문제이지만, 다양한 해결 기법을 통해 이를 효과적으로 관리할 수 있다.

 

충돌 해결 전략

• 체이닝(Chaining) : 각 인덱스에 연결 리스트(또는 다른 자료구조)를 사용하여, 동일한 해시 값을 가진 여러 요소를 저장한다.
• 오픈 어드레싱(Open Addressing) : 충돌이 발생하면, 해시 테이블 내에서 다른 빈 공간을 찾아 데이터를 저장한다. 대표적인 방법으로는 선형 탐사 (Linear Probing), 이차 탐사(Quadratic Probing) 등이 있다.

 

 

해시 테이블의 장단점 및 사용 시 고려사항

 

장점  : 

• 빠른 검색 및 삽입 : 평균적으로 O(1)의 시간 복잡도로 데이터 접근이 가능하다.
• 유연성 : 키와 값의 쌍으로 데이터를 관리하므로, 다양한 데이터 타입에 쉽게 적용할 수 있다.
• 효율적인 메모리 사용 : 적절한 해시 함수와 충돌 해결 기법을 사용하면, 메모리 낭비 없이 효율적으로 데이터를 저장할 수 있다.

단점 및 고려사항 : 

• 충돌 발생 가능성 : 해시 함수의 품질에 따라 충돌이 많이 발생하면 성능이 저하될 수 있다.
• 동적 크기 조절 : 해시 테이블은 데이터의 양이 증가하면 크기를 동적으로 조절해야 하며, 이 과정에서 비용이 발생할 수 있다.
• 해시 함수 선택 : 좋은 해시 함수를 선택하는 것은 해시 테이블의 성능과 직접적으로 연결되므로 매우 중요하다.

 

이런 해시테이블은 어디에 사용할 수 있을까?

1. 데이터베이스 인덱싱 : 대규모 데이터베이스에서 해시 테이블은 빠른 검색과 데이터 접근을 위한 인덱스로 활용된다.
2. 캐시(Cache) : 웹 애플리케이션에서 사용자 데이터를 캐싱하거나, 자주 사용하는 데이터를 임시 저장해주더 빠른 응답을 제공하는 데 해시 테이블을 사용한다.
3. 집합 구현 : 집합은 중복 없는 데이터를 저장하는 자료구조이다. 해시 테이블을 기반으로 구현된 HashSet은 데이터의 중복 여부를 빠르게 판단할 수 있다.

 

Kotlin에서는 표준 라이브러리에서 HashMap을 제공하여, 해시 테이블을 쉽게 사용할 수 있다.

fun main() {
    // HashMap 생성: 키는 String, 값은 Int
    val hashMap = HashMap<String, Int>()
    
    // 데이터 삽입
    hashMap["apple"] = 5
    hashMap["banana"] = 3
    hashMap["cherry"] = 7
    
    // 데이터 조회
    println("사과의 수: ${hashMap["apple"]}") // 출력: 사과의 수: 5
    
    // 데이터 존재 여부 확인
    if (hashMap.containsKey("banana")) {
        println("바나나가 존재합니다.")
    }
    
    // 모든 키와 값 순회
    for ((key, value) in hashMap) {
        println("$key : $value")
    }
}

 

HashMap의 내부 동작 원리에 대해 살짝 알아보면

• 해시 함수 적용 : 입력된 키에 대해 내부 해시 함수를 적용하여 인덱스를 계산하고
• 충돌 처리 : 동일한 인덱스가 발생한 경우, 체이닝(LinkedList 등)을 사용하여 여러 값을 저장한다
• 동적 크기 조절 : 데이터가 많아지면 자동으로 크기를 확장하여 성능 저하를 방지한다.

HashMap 내부적으로 처리를 해주기 때문에 그냥 가져다 쓰기만 하면 된다...!

 

 

해시 테이블 응용 문제

 

1. 중복된 문자 제거

문자열에서 중복된 문자를 제거하고, 결과를 유지하는 문제는 해시 테이블을 활용하여 해결할 수 있다.

fun removeDuplicates(s: String): String {
    val seen = HashSet<Char>()
    val sb = StringBuilder()
    
    for (ch in s) {
        if (seen.add(ch)) {  // add()는 중복된 문자가 없으면 true를 반환합니다.
            sb.append(ch)
        }
    }
    return sb.toString()
}

fun main() {
    val input = "banana"
    println("중복 제거 결과: ${removeDuplicates(input)}") // 출력 예: "ban"
}

 

 

2. 캐시 구현 예제

간단한 캐시를 해시 테이블로 구현하여, 자주 사용하는 데이터를 빠르게 검색하는 방법을 보여준다.

class SimpleCache<K, V> {
    private val cache = HashMap<K, V>()
    
    fun put(key: K, value: V) {
        cache[key] = value
    }
    
    fun get(key: K): V? {
        return cache[key]
    }
    
    fun contains(key: K): Boolean {
        return cache.containsKey(key)
    }
}

fun mainCache() {
    val cache = SimpleCache<String, Int>()
    cache.put("apple", 5)
    cache.put("banana", 3)
    println("apple: ${cache.get("apple")}")  // 출력: apple: 5
}