코딩 테스트 합격자 되기 - 해시
스터디 : 코딩테스트 합격자 되기 - 3주 차
강의 출처 : 인프런 코딩 테스트 합격자 되기 - 해시
해시
해시는 키값을 기반으로 데이터의 저장위치를 직접 계산해서 탐색, 삽입, 삭제한다.
개별 원소 키값에 따른 절대적인 위치로 정의가 되기 때문에 직접적인 탐색이 가능하다.
해시 테이블로 데이터를 관리한다.
해시를 활용해서 풀어야 하는 문제
- 키-값 쌍으로 연관된 데이터가 존재하며, 해당 값에 대한 접근이 빈번한 경우 (사전, 연락처)
- 중복되지 않는 키를 사용하는 경우 (학번, 집주소)
해시를 사용하면 안되는 경우
- 특정 키에 여러 값을 매칭해야 하는 경우
해시 함수
임의의 키를 해시 테이블의 인덱스로 변경해주는 함수이다.
해시 테이블의 크기가 N이라면 해시 함수는 0~(N-1)사이 값을 내야한다.
둘 이상의 키가 해시 테이블의 같은 주소를 반환할 경우 충돌이 발생한다.
충돌이 발생하면 성능이 나빠지기 때문에 충돌을 적게 발생 시키는 해시 함수를 사용하는 것이 좋다.
해시 함수 - 나눗셈법
나눗셈 법은 키값이 정수 K로 주어지는 경우 키값을 테이블 크기 M으로 나눈 나머지를 주소로 이용하는 방법이다.
h(K) = K mod M
K로 나눈 나머지는 0 ~ K-1 이므로 해시 테이블의 크기는 K이다.
K가 소수인 이유는 충돌을 줄이기 위함이다.
해시 함수 - 곱셈법
나눗셈법은 K가 수소여야 하므로, 테이블 크기가 커지만 큰 소수가 필요한다.
곱셈법은 소수를 활용하지 않고 황금비를 곱하는 방식이다.
h(x) = (((x*A) mod 1)*m) x는 키, A는 황금비, m은 최대 버킷의 갯수
해시 함수 - 문자열 해싱
문자열의 아스키 코드 값을 활용한다.
해시 충돌 처리 - 체이닝
충돌 발생 시 해당 버킷에 링크드리스트로 데이터를 연결 한다.
특정 버싯에 데이터가 N개인 경우, 원하는 값을 찾는데 O(N)이 결릴 수 있다.
해시 충돌 처리 - 개방 주소법 (선형 탐사)
충돌 발생 시 다른 빈 버킷을 찾아 충돌 값을 삽입한다.
최대한 기존 테이블을 사용하자는 방식으로 메모리를 아낄 수 있다.
해시 충돌 처리 - 개방 주소법(이중해싱)
해시 함수를 2개 사용하는 방법이다. 경우에 따라 N개까지 확장할 수 있다.
기존에 i를 더했던 선형탐사와 다르게 2번째 해시 함수에 i를 곱하는 방식도 가능하다.
문제 풀기
function solution(record) {
let answer = [];
const map = new Map();
for (let i = 0; i < record.length; ++i) {
const [state, uid, name] = record[i].split(' ');
if (state == 'Leave') {
answer.push([uid, '님이 나갔습니다.']);
continue;
}
if (state == 'Enter') {
answer.push([uid, '님이 들어왔습니다.']);
}
map.set(uid, name);
}
return answer.map(ele => map.get(ele[0]) + ele[1]);
}