알고리즘

[알고리즘 고득점 kit] 해시 (개념, 문제풀이)

팝삐 2024. 9. 6. 00:38

해시의 개념

  • 해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다.
  • 보통은 인덱스를 활용해서 탐색을 빠르게 만들지만 해시는 키를 사용해 데이터 탐색을 빠르게 한다.
  • 해시는 키와 데이터를 일대일 대응하여 저장하므로 키를 통해 데이터에 바로 접근할 수 있다. 사람에게는 숫자로 데이터를 관리하는 배열보다 조금 더 접근성이 좋은 자료구조이다.

키워드

  • 값
    • 최종적으로 얻고자 하는 정보
  • 키
    • 값을 검색하기 위해 활용하는 정보
  • 해시 함수
    • 키를 이용해 해시값 또는 인덱스로 변환하는 함수

해시의 특징

  • 해시는 단방향으로 동작한다.
    • 키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾을 수는 없다.
    • 단방향으로만 동작하는 해시의 특성은 외부에 정보를 안전하게 제공한다는 특징이 있어 네트워크 보안에서 많이 활용된다.
  • 찾고자 하는 값을 O(1)에서 바로 찾을 수 있다.
    • 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없다.
  • 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 한다.

해시 분야

  • 해시는 단방향으로만 검색할 수 있는 대신 빠르게 원하는 값을 검색할 수 있다.
  • 그래서 해시는 데이터를 저장하고 검색하거나 보안이 필요할 때 활용된다.
  • 비밀번호 관리
    • 해시 함수를 활용해 해싱한 비밀번호를 저장한다. 비밀번호가 맞는지 확인할 때도 마찬가지이다.
  • 데이터베이스 인덱싱
    • 데이터베이스에 저장된 데이터를 효율적으로 검색할 때 해시를 활용한다.
  • 블록체인
    • 블록체인에서 해시 함수는 핵심 역할을 한다. 각 블록은 이전 블록의 해시값을 포함하고 있으며, 이를 통해 데이터 무결성을 확인할 수 있다.

해시 구현

  • 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안 된다.
  • 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 한다.
    • 충돌 : 서로 다른 두 키에 대해 해싱 함수를 적용한 결과과 동일한 것을 의미

자주 사용하는 해시 함수

  • 나눗셈법
    • 가장 떠올리기 쉬운 단순한 해시 함수
    • 나눗셈법 : 키를 소수로 나눈 나머지를 활용
      • h(x) = x mod k
    • 위와 같이 계산하는 경우 자연스레 나눗셈법의 해시 테이블 크기는 K가 된다. 왜냐하면 K에 대해 모듈러 연산을 했을 때 나올수 있는 값은 0 ~ 9(K - 1)이기 때문이다.
  • 곱셈법
    • 나눗셈법과 비슷하게 모듈러 연산을 활용하지만 소수는 활용하지 않는다.
    • 황금비를 사용한다.
      • h(x) = (((x * A) mod 1) * m
      • m은 최대 버킷의 개수, A는 황금비이다.
  • 문자열 해싱
    • 키의 자료형이 문자열일 때도 사용할 수 있는 해시 함수인 문자열 해싱
    • 문자열 해싱은 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱한다.
      • hash(s) = (s[0] + s[1] * p + s[2] * p^2 + … + s[n-1] * p^n-1) mod m
    • p는 31이고, m은 해시 테이블의 최대 크기이다.
      • p를 31로 정한 이유는 홀수이면서 메르센 소수이기 때문이다.
        • 메르센 소수는 해시에서 충돌을 줄이는데 효과적이라는 연구 결과가 있다.

해시 함수 적용시 중요한 점

  • 해시 함수를 적용한 값이 해시테이블 크기에 비해 너무 클 수 있다는 점.
  • 그래서 해시 함수가 내는 결과의 크기를 해시 테이블 크기에 맞도록 하는 작업이 필요하다.
    • hash(s) = (s[0] % m + s[1] * p % m + s[2] * p^2 % m + … + s[n-1] * p^n-1 % m) mod m
    • 위처럼 중간 중간 모듈러 연산을 해 더한 값을 모듈러 연산하면 오버플로우를 최대한 방지할 수 있다.

충돌처리

  • 서로 다른 키에 대해서 해시 함수의 결괏값이 같으면 충돌이라고 한다. 하나의 버킷에 2개의 값을 넣을 수는 없으므로 해시 테이블을 관리할 때는 반드시 충돌 처리를 해야 한다.
  • 체이닝으로 처리하기
    • 해싱한 값이 같은 경우 충돌을 해결하는 간단한 방법
    • 체이닝은 충돌 발생 시 해당 버킷에 연결 리스트로 같은 해시값을 가지는 데이터를 연결한다.
      • 충돌이 많아지면 그만큼 연결 리스트의 길이가 길어지고 다른 해시 테이블의 공간은 덜 사용하므로 공간 활용성이 떨어진다.
      • 충돌이 많으면 연결 리스트 자체의 한계 때문에 검색 성능이 떨어진다. 연결리스트는 맨 앞의 데이터부터 검색해야 하기 때문
  • 개방 주소법으로 처리하기
    • 체이닝에서 연결 리스트로 충돌값을 연결한 것과 다르게 빈 버킷을 찾아 충돌값을 삽입한다.해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용할 수 있다.
    • 선형 탐사 방식
      • 선형 탐사 방식은 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동한다.
      • h(k, i) = (h(k) + i) mod m
        • m은 수용할 수 있는 최대 버킷. 선형 탐사 시 테이블의 범위를 넘으면 안 되므로 모듈러 연산을 적용한 것.
    • 이중 해싱 방식
      • 말 그대로 해시 함수를 2개 사용하는 방식
      • 해시 함수를 N개로 늘리기도 한다.
      • 두번째 해시 함수의 역할은 첫번째 해시 함수로 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치를 정할 지 결정하는 역할을 한다.

JS에서의 해시

  • 자바스크립트에서는 주로 Map을 사용하여 객체를 생성해 해시 테이블을 만든다.
  • // 맵 객체 생성 let hash = new Map(); // 객체에 키:값을 삽입 hash.set("key1", 1234); hash.set("key2", "hi"); // 객체에 삽입된 값을 가져오는 법 console.log(hash.get("key1")); //1234 console.log(hash.keys()); //{"key1", "key2"} console.log(hash.values()); //{1234, "hi"} // 객체의 값을 모두 삭제 hash.clear(); // 객체의 특정 값 삭제 hash.delete("key1");

해시 문제 풀이

1. 폰켓몬

  1. 해시 카테고리에 있는 문제임은 알았으나 아직 자바스크립트로 해시를 구현한다는 것이 잘 감이 잡히지 않아 지금까지 풀어왔던 것처럼 단순하게 풀어봤다. 문제를 읽어보니 결론적으로 필요한 것은 N/2의 값인 것 같아 num으로 값을 미리 구한 후, 중복 된 값을 모두 없애버린 answer에서 if문으로 상황에 따른 처리를 해주었다. 풀이 후에 Set()과 해시 테이블 코드가 결국 비슷하게 돌아간다고 생각해서 찾아보니 둘은 기본적으로 다른 개념이지만 실제 구현에서는 해시 테이블을 기반으로 한 Set을 많이 사용하게 되므로 이를 Hast Set이라고 부르기도 한다는 것을 알았다.
function solution(nums) {
    var answer = [...new Set(nums)];
    let num = nums.length / 2;
    if (num > answer.length) {
        return answer.length;
    } else {
        return num;
    }
  return answer;
}

2.  해시 알고리즘을 이해하고 싶어서 다른 분의 풀이를 참고했다. 그리고 이 코드를 이해하면서 대충 이해했다. nums에 들어온 각 값들이 해시테이블에 존재하지 않는다면 우선 넣고, 존재할 때마다 해당 포켓몬의 수를 하나씩 늘리는 것.

function solution(nums) {
    let answer = 0;
    let bag = new Map();
    nums.forEach((monster) => {
        if(bag.get(monster)) bag.set(monster, bag.get(monster) + 1);
        else bag.set(monster, 1);
    });
    
    if (bag.size < nums.length / 2) answer = bag.size;
    else answer = nums.length / 2;
    
    return answer;
}

 

 

 

3. 파이썬도 어느 정도 함께 이해하고 싶어서 파이썬 코드로도 풀이해보았다. 파이썬도 set 으로 중복을 없앨 수 있고, 다시 배열 형태로 사용하고 싶다면 list()안에 넣어서 사용해야 한다.

def solution(nums):
    num = len(nums) // 2
    answer = list(set(nums))
    return len(answer) if num > len(answer) else num

2. 완주하지 못한 선수

  1. 해시 코드 
    function solution(participant, completion) {
    var answer = new Map();

    for (let i = 0; i < participant.length; i++) {
        if (answer.get(participant[i])) {
            answer.set(participant[i], answer.get(participant[i]) + 1);
        } else {
            answer.set(participant[i], 1);
        }
    }

    for (let i = 0; i < completion.length; i++) {
        if (answer.get(completion[i])) {
            answer.set(completion[i], answer.get(completion[i]) - 1);
        }
    }

    for (let [key, value] of answer) {
        if (value > 0) {
            return key;
        }
    }
}
    해시 쓴다고 쓴건데 다른 사람들 코드 보면서 빨리 이 길을 접어야 하나 진지하게 고민할 정도의 코드가 나온 것 같다 ^_^ 

2. 둘러보던 중 가장 마음에 들었던 코드

  • 내가 작성한 첫번째 for문을 forEach로 바꿔서 각 배열에 쉽게 접근하고 if 문 대신 or의 경우 왼쪽의 값이 false이면 오른쪽 값이 된다는 것을 이용해 이름이 있는 경우 기존 값 + 1, 없는 경우 0 + 1이 되어 1로 세팅된다.
  • 두번째 for문 대신 find() 메소드를 사용해 completion 배열 안에 이름이 있다면 값을 줄이고 없는 경우 해당 인덱스의 사람 이름을 return 한다.
var solution = (participant, completion) => {
    let completionCount = {};
    completion.forEach(name => {
        completionCount[name] = (completionCount[name] || 0) + 1;
    });

    return participant.find(name => {
        if (!completionCount[name]) {
            return true;
        }
        completionCount[name]--;
    });
};

 

3. 파이썬으로 작성한 코드

def solution(participant, completion):
    par = sorted(participant)
    com = sorted(completion)
    for i in range(len(com)):
        if par[i] != com[i]:
            return par[i]
        
    return par[-1]

js 답변들 둘러보다보니 정렬 후 다르거나 마지막 사람이 미완주자가 되는 것을 이용해서 풀이한 코드가 많아서 그대로 파이썬에 적용했다.

3. 전화번호 목록

  1. 해시를 사용하지 않고 정렬과 startsWith 메소드를 사용해서 풀이한 방법.
    • 예시로 나온 phone_book의 element들이 ["119", "97674223", "1195524421"] 라고 가정하는 경우 접두사가 되는 요소는 접두사가 포함되는 요소보다 짧을 것이고, sort로 정렬하면 비슷한 요소들이 가깝게 정렬이 될 테니 정렬 후에 근처에 있는 요소를 확인하면 된다.
    • function solution(phone_book) { phone_book.sort(); for (let i = 0; i < phone_book.length - 1; i++) { if (phone_book[i + 1].startsWith(phone_book[i])) { return false; } } return true; }
  2. 해시를 사용해 풀이하는 방법
    • 해시 사용 방법을 통한 풀이를 제대로 이해 못해서 추후 수정 예정
  3. 파이썬 코드
    • 파이썬에도 startswith 메소드가 있다는 점! 
      def solution(phone_book):
    sorted_arr = sorted(phone_book)
    for i in range(len(sorted_arr) - 1):
        if sorted_arr[i + 1].startswith(sorted_arr[i]):
            return False
    return True
    • 1번 풀이를 파이썬으로 똑같은 방식을 사용해 풀이한 과정이다.
    • 이건 파이썬 해시를 사용한 다른 분의 코드이다. 
      def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer
    • 우선 hash 사용을 위해 hash 객체 하나를 생성한다. phone_book에 주어진 번호를 도는 동안 hash_map에 키로 저장하고 값을 1로 할당한다. 그리고 안에 있는 값을 바로 하나씩 꺼내어서 사용할 것이다. 우선 temp 변수를 초기화한다. 각 번호 묶음의 번호 한 자리씩을 꺼내어 temp에 저장한다. 만약 temp가 hash_map에 존재하면서 temp가 phone_number은 아니라면 전체 전화번호와는 동일하지 않다는 뜻이므로 다른 번호의 접두사가 된다는 의미이다.

 

4. 의상

추후 수정 예정

5. 베스트 앨범

추후 수정 예정