알고리즘 스터디 1주차. 해시

자몽·2022년 4월 11일

알고리즘

목록 보기

28/31

해시 테이블

해시의 특징
검색과 저장이 아주 빠르게 진행

검색과 저장이 빠르게 진행될 수 있는 이유는, key-value가 한 쌍으로 존재하고, key값이 배열의 인덱스로써 존재하기 때문에 평균적인 검색/저장의 시간 복잡도가 O(1)이 나온다.

충돌이 발생했을 경우 최악의 경우 시간 복잡도는 O(n)이 나온다.

장점

적은 리소스를 가지고도 많은 데이터를 효율적으로 관리할 수 있다.
데이터의 검색, 삽입, 삭제가 빠르다
데이터 캐싱에 많이 사용된다.

단점

순서가 있는 배열에는 어울리지 않음
공간 효율성이 떨어진다.
해시 함수의 의존도가 높다.
https://hee96-story.tistory.com/48

직접 주소 테이블

해시 테이블은 초창기에 직접 주소 테이블이라는 자료구조에서 시작되었다.

아이디어는 간단하다.

같은 배열일지라도 2라는 숫자를 찾기 위해서는 기존에는 연산이 0~6까지 총 6번 필요했던 반면, 직접 주소 테이블을 사용하면 배열의 index가 바로 key가 되었기 때문에 1번의 연산으로도 숫자를 찾을 수 있다.

하지만, 직접 주소 테이블에도 단점이 있는데, 저장하고자 하는 값이 클수록 배열은 무한정 늘어나게 된다.

해시 테이블

직접 주소 테이블의 단점을 해시 테이블로써 보완할 수 있다.

주어진 key가 들어오면 hash 함수를 통해 값을 저장시키는 형식이다.

여기서 해시 함수가 어떻게 동작하는지 의문이 들 수 있는데 의외로 간단하다.

function hashFunction (key){
  return key%7;
}

위의 코드와 같이 개발자는 임의로 해시 함수를 만들어 자료를 저장시킬 수 있다.(물론 언어마다 해시가 지원되므로 쓸일은 없다)

해시 테이블의 장점

해시 테이블을 사용하면 앞서서 말했던 직접 주소 테이블의 공간 낭비 단점을 해결할 수 있다.
또한, 해시 함수를 알지 않는 한, key만 보고 value를 알 수 없기 때문에 보다 보안이 뛰어나다.

해시 테이블의 문제점

해시 테이블은 공간이 한정되어 있다보니, 해시 함수를 돌려서 값을 할당해주다 보면, 어느순간 값이 저장되는 공간에서 충돌이 발생한다. 이를 해시 충돌이라 한다.

해시 충돌

해시가 충돌되면 이를 해결하기 위해 여러 방법을 사용한다.

개방 주소법

선형 탐색

해시가 충돌했을 경우, 다음 순서에 있는 빈 버킷에 값을 넣어준다.

제곱 탐색

해시가 충돌했을 경우, 현재 버킷 주소의 제곱 위치에 값을 넣어준다.

이중 해시

해시가 충돌했을 경우, 또다른 해시 함수에 해당 key를 넣어 새로운 주소를 구해준다.

선형 탐색은 1차 군집화 문제가 발생하고, 제곱 탐색은 2차 군집화 문제가 발생하는데 이러한 문제를 이중 해시가 해결해준다.

분리 연결법(체이닝)

연결리스트 형식으로, 충돌이 일어나면 해당 버킷과 연결된 리스트를 만든다.

테이블 크기 재할당

테이블이 꽉 차거나, 리스트가 너무 길어지면 탐색의 저하가 발생할 수 있다.

따라서 일정 수준 이상으로 버킷이 채워지면, 해시 테이블을 확장할 필요가 있는데 이를 리사이징이라고 한다. 대부분 사용률이 약 70%정도 되면, 해시 테이블을 약 2배정도로 확장시킨다고 한다.

해시 테이블 알고리즘 문제풀이

오픈채팅방

https://programmers.co.kr/learn/courses/30/lessons/42888

코드

function solution(record) {
    var answer = [];
    const user = new Map();
    
    record = record.map(el=>el.split(' '))
    
    record.map(el=>{
        if(el[0]==='Enter' || el[0]==='Change') user.set(el[1],el[2])
    })  
    
    record.map(el=>{
        if(el[0]==='Enter'){
            answer.push(`${user.get(el[1])}님이 들어왔습니다.`)
        }else if(el[0]==='Leave'){
            answer.push(`${user.get(el[1])}님이 나갔습니다.`)
        }
    })
    
    return answer;
}