https://youtu.be/zFL29ydL9D8?si=Q12ECahx_Px3TtSu
1. 해시란 무엇인가?
해시는 '키(Key)'와 '값(Value)'의 쌍으로 데이터를 저장하는 자료 구조.
이 구조는 검색, 삽입, 삭제 작업을 매우 빠르게 수행할 수 있도록 설계되어 있다.
예를 들어, 전화번호부에서 사람의 이름(키)을 사용하여 전화번호(값)를 빠르게 찾는 것과 같습니다.
2. 왜 사용하는가
전통적인 배열에서는 인덱스를 통해서만 접근이 가능하므로,
비정수 기반의 데이터(예: 문자열)로 직접 접근할 수 없었다고 한다.
이를 해결하기 위해, 해시 테이블이나 해시 맵을 사용하면 문자열이나 다른 타입의 키를 사용하여 데이터에 빠르게 접근할 수 있습니다.
3. 해시의 작동 방식
해시 테이블은 해시 함수를 사용하여 주어진 키를 배열의 인덱스로 변환합니다.
이 인덱스를 사용하여 데이터를 저장하거나 검색할 수 있습니다.
충돌(Collision)이 발생할 경우, 체이닝(Chaining)이나
개방 주소법(Open Addressing)과 같은 방법으로 해결할 수 있습니다.
해시 테이블(Hash Table)
해시 테이블은 연관 배열구조를 이용하여 데이터를 Key와 Value로 저장하는 자료구조이다.
해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.
연관 배열구조란?
연관 배열은 자료구조의 하나로, 키 하나와 값 하나가 연관되어 있으며 키를 통해 연관되는 값을 얻을 수 있다.연관 배열은 일반적으로 다음의 명령을 지원한다.
- 키와 값이 주어졌을 때, 연관 배열에 그 두 값을 저장하는 명령
- 키가 주어졌을 때, 연관되는 값을 얻는 명령
- 키와 새로운 값이 주어졌을 때, 원래 키에 연관된 값을 새로운 값으로 교체하는 명령
- 키가 주어졌을 때, 그 키에 연관된 값을 제거하는 명령
이렇게 하나의 키 값이 존재할 때, 해시 함수를 통해서 데이터를 키값으로 바꾸어 버킷에 저장한다.
4. 코딩 테스트에서의 해시 활용
완주하지 못한 선수: 각 선수의 이름을 키로 하고, 출석 횟수를 값으로 사용하는 해시 맵을 만들어 관리합니다.
완주한 선수의 이름을 해시 맵에서 찾아 값을 감소시키고, 값이 0이 아닌 선수를 찾으면 그 선수가 완주하지 못한 선수입니다.
findNonCompleter(['Alice', 'Bob', 'Charlie'], ['Alice', 'Charlie'])
function findNonCompleter(participants, completers) {
const completionMap = new Map();
// 참가자들을 해시 맵에 추가
participants.forEach(participant => {
const count = completionMap.get(participant) || 0;
completionMap.set(participant, count + 1);
});
// 완주자 수를 차감
completers.forEach(completer => {
const count = completionMap.get(completer) - 1;
completionMap.set(completer, count);
});
// 완주하지 못한 선수 찾기
for (let [name, count] of completionMap.entries()) {
if (count > 0) {
return name;
}
}
}
// 사용 예:
5. 해시의 주요 메소드
getOrDefault : 키가 존재하면 해당 키의 값을 반환하고,
존재하지 않으면 기본값을 반환합니다.
put: 키와 값을 해시 맵에 저장합니다. 키가 이미 존재하면, 값을 업데이트합니다.
