해시(Hash)

해시(Hash)란

- 데이터를 고정된 크기의 값으로 변환하는 함수 또는 그 값을 저장하는 자료구조입니다.

- 해시 함수는 데이터를 일정한 규칙에 따라 변환하여 빠르게 조회할 수 있도록 도와주며, 해시 테이블은 이를 활용하여 데이터를 저장하는 자료구조입니다.

 

해시의 주요개념

• 해시 함수 (Hash Function): 입력 데이터를 고정된 크기의 해시 값으로 변환하는 함수입니다. 입력값에 대해 고유한 해시 값을 생성하려고 하지만, 동일한 해시 값을 가질 가능성도 있습니다. 이를 충돌(Collision)이라고 합니다.
• 해시 값 (Hash Value): 해시 함수의 결과물로, 일반적으로 고정 길이의 숫자 또는 문자열입니다.
• 해시 테이블(Hash Table): 데이터를 키와 값의 쌍으로 저장하는 자료구조로, 키를 해시 함수에 전달하여 얻은 해시 값에 따라 데이터를 빠르게 저장하고 검색할 수 있습니다.

해시의 주요연산

1. 삽입(Insert): 주어진 키와 값을 해시 테이블에 삽입
2. 검색(Search): 주어진 키에 해당하는 값을 해시 테이블에서 검색
3. 삭제(Delete): 주어진 키에 해당하는 값을 해시 테이블에서 삭제

해시의 특징

특징	설명
메모리 구조	선형 구조(배열 또는 연결 리스트 기반)
시간 복잡도	O(1) (이론상으로 해시 함수가 잘 설계되면, 삽입, 검색, 삭제 연산 모두 상수 시간이 걸립니다.)
충돌 해결	해시 값이 중복되는 경우를 처리하는 방법은 여러 가지가 있으며, 대표적으로 체이닝과 오픈 어드레싱이 있습니다.

 

해시의 충돌 해결 방법

1. 체이닝 (Chaining): 각 해시 버킷에 연결 리스트를 사용하여 충돌을 해결합니다. 같은 해시 값을 가진 여러 항목을 하나의 버킷에 연결 리스트 형태로 저장합니다.
2. 오픈 어드레싱 (Open Addressing): 충돌이 발생하면 다른 빈 슬롯을 찾아 데이터를 삽입합니다. 충돌 해결 방식에는 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있습니다.

 

해시의 활용 예시

1. 데이터베이스 인덱싱
   - 데이터베이스에서 특정 키를 빠르게 검색하기 위해 해시 테이블을 사용하여 인덱스를 관리합니다.
2. 비밀번호 저장
   - 사용자 비밀번호를 해시 함수를 사용하여 암호화하여 안전하게 저장합니다. 입력된 비밀번호도 동일한 해시 함수로 암호화하여 비교합니다
3. 중복 데이터 처리
   - 동일한 데이터를 중복해서 저장하지 않기 위해 해시 값을 이용해 데이터의 중복을 쉽게 확인 할 수 있습니다.
4. 캐시 구현
   - 해시 테이블을 활용하여 데이터를 캐싱하여 빠르게 접근할 수 있습니다. 예를 들어, 웹 서버의 요청 처리 시 캐시를 사용하여 동일한 요청에 대해 빠르게 응답할 수 있습니다.

해시를 이용한 코딩 테스트 예제

1. 두 수의 합 (Two Sum)

• 문제 설명: 주어진 정수 배열에서 두 숫자의 합이 특정 타겟 값이 되는 두 인덱스를 찾으세요.
• 예시: nums = [2, 7, 11, 15], target = 9
• 출력: [0, 1] (2 + 7 = 9)
• 풀이: 해시 테이블을 사용하여, 현재 수와 타겟에서 현재 수를 뺀 값을 해시 테이블에 저장하고, 다음 숫자를 순차적으로 확인하여 차이가 해시 테이블에 존재하면 결과를 반환합니다.

function twoSum(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
}

 

2. 두 배열의 교집합 (Intersection of Two Arrays)

• 문제 설명: 두 배열이 주어졌을 때, 두 배열의 교집합을 구하세요. 결과는 중복 없이 반환되어야 합니다.
• 예시: nums1 = [1, 2, 2, 1], nums2= [2, 2]
• 출력: [2]
• 풀이: 첫 번째 배열의 각 요소를 해시 테이블에 저장한 뒤, 두 번째 배열의 각 요소가 해시 테이블에 있는지 확인하여 교집합을 구합니다.

function intersection(nums1, nums2) {
    const set1 = new Set(nums1);
    const result = [];
    for (const num of nums2) {
        if (set1.has(num)) {
            result.push(num);
            set1.delete(num); // 중복 방지
        }
    }
    return result;
}

 

3. 단어 빈도수 (Word Frequency Count)

• 문제 설명: 주어진 문장에서 각 단어의 빈도수를 구하고, 빈도수가 높은 순서대로 정렬하여 출력하세요.
• 예시: sentence = "the day is sunny the day is bright"
• 출력: ["the", "day", "is", "sunny", "bright"] (빈도수: the:2, day:2, is:2, sunny:1, bright:1)
• 풀이: 해시 테이블을 사용하여 각 단어의 빈도수를 카운팅하고, 그 빈도수를 기준으로 정렬합니다.

function mostCommonWords(sentence) {
    const words = sentence.split(' ');
    const wordCount = {};
    for (const word of words) {
        wordCount[word] = (wordCount[word] || 0) + 1;
    }
    return Object.keys(wordCount).sort((a, b) => wordCount[b] - wordCount[a]);
}

 

4. Anagram 그룹 (Group Anagrams)

• 문제 설명: 주어진 단어 리스트에서 에너그램이 되는 단어들을 묶어서 그룹화하세요.
• 예시: strs=["eat", "tea", "tan", "ate", "nat", "bat"]
• 출력: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
• 풀이: 각 단어를 알파벳 순서대로 정렬하여 같은 알파벳을 가진 단어끼리 같은 키 값을 가지도록 해시 테이블을 사용합니다.

function groupAnagrams(strs) {
    const map = new Map();
    
    for (const str of strs) {
        const sortedStr = str.split('').sort().join('');
        if (!map.has(sortedStr)) {
            map.set(sortedStr, []);
        }
        map.get(sortedStr).push(str);
    }
    
    return Array.from(map.values());
}