해시 ( Hash )

youngkyu MIn·2023년 12월 7일

해시 (Hash)

해시(Hash) 알고리즘은 데이터 관리 및 검색에서 널리 사용되는 중요한 프로그래밍 기법이다. 이 알고리즘의 기본 아이디어는 데이터를 빠르게 저장하고 검색하기 위해 '키(Key)'에 해당하는 데이터를 '해시 함수(Hash Function)'를 통해 '해시 값(Hash Value)'으로 변환하고, 이 값을 인덱스로 사용하여 데이터를 배열이나 리스트와 같은 자료 구조에 저장하는 것이다.

해시는 다음과 같은 경우에 유용하다.

데이터 검색: 해시 테이블은 키를 사용하여 데이터를 빠르게 검색할 수 있다.
중복 제거: 데이터의 중복 여부를 효율적으로 체크할 수 있다.
데이터 인덱스: 대량의 데이터에서 특정 요소를 빠르게 찾기 위해 사용된다.

성능

해시 알고리즘의 성능은 해시 함수의 품질, 충돌 해결 메커니즘, 데이터의 분포 등에 따라 달라진다. 올바르게 구현된 해시 테이블은 평균적으로 상수 시간(O(1))의 검색 시간을 가진다. 하지만, 최악의 경우(예: 많은 충돌이 발생하는 경우)에는 선형 시간(O(n))이 걸릴 수 있다.

해시 함수 (Hash Function)

해시 함수는 임의의 길이의 데이터를 고정된 길이의 해시 값으로 매핑한다. 이때, 이상적인 해시 함수는 다음과 같은 특징을 가져야 한다.

일관성(Consistency): 동일한 입력에 대해 항상 같은 해시 값을 반환해야 한다.
빠른 계산(Speed): 데이터를 빠르게 처리할 수 있어야 한다.
분산성(Distribution): 해시 값이 균일하게 분포되어야 충돌(Collision)을 최소화할 수 있다.

충돌(Collision)과 충돌 해결

때때로 다른 데이터가 같은 해시 값을 가질 수 있는데, 이를 '충돌(Collision)'이라고 한다. 충돌을 해결하는 몇 가지 방법은 다음과 같다.

체이닝(Chaining): 같은 해시 값을 가진 요소들을 연결 리스트로 관리한다.
선형 탐사(Linear Probing): 충돌 발생 시, 다음 빈 인덱스에 데이터를 저장한다.
이중 해싱(Double Hashing): 두 번째 해시 함수를 사용하여 다른 인덱스를 찾는다.

HashSet 과 HashMap

java 에는 Hash 알고리즘을 따르는 HashSet 과 HashMap 이 있다. 이들은 내부적으로 해시 테이블을 사용하여 데이터를 저장하고 관리한다.

HashMap

HashMap은 키-값 쌍을 저장한다.
각 키는 해시 함수를 통해 해시 코드로 변환된다.
이 해시 코드는 데이터를 저장하고 검색할 위치(인덱스)를 결정하는 데 사용된다.
과정을 통해 HashMap은 빠른 검색, 삽입 및 삭제 작업을 제공한다.

HashSet

HashSet은 중복을 허용하지 않는 유일한 객체들의 집합을 저장한다.
내부적으로 HashSet은 HashMap을 사용한다. 여기서 객체가 저장되는 값이며, 각 객체는 해시 함수를 사용하여 해시 코드로 변환된다.
HashSet은 객체의 존재 여부를 빠르게 확인할 수 있도록 해시 테이블의 특성을 활용한다.

예시 문제

문제링크 - 프로그래머스 - 완주하지 못한 선수

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<>();

        for (String player : participant) {
            map.put(player, map.getOrDefault(player, 0) + 1);
        }

        for (String player : completion) {
            map.put(player, map.get(player) - 1);
        }

        for (String key : map.keySet()) {
            if (map.get(key) > 0) {
                return key;
            }
        }

        return null;
    }
}

HashMap 을 사용했다.

문제링크 - 프로그래머스 - 폰켓몬

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(int[] nums) {

        Set<Integer> set = new HashSet<>();
        
        for (Integer i : nums) {
            set.add(i);
        }
        
        if (nums.length/2 > set.size()) return set.size();
        
        return nums.length/2; 
    }
}