2주차

HashMap / Set

개념

HashMap과 Set은 **해싱(Hashing)**을 사용해서 데이터를 빠르게 찾거나 저장할 수 있는 자료구조입니다. 해싱은 **키(key)**를 **해싱 함수(Hashing Function)**를 이용해 정수값인 해시코드(Hashcode)로 변환하는 것을 말합니다.

HashMap

HashMap은 **키(key)**와 값(value) 쌍을 저장하는 자료구조입니다. 각 키는 고유하며 키를 사용해 원하는 값을 빠르게 검색할 수 있습니다.
HashMap은 자료구조로 배열(Array)을 사용하는데, 해싱을 통해 변환된 해시코드는 배열의 각 요소인 버킷(Bucket)의 인덱스가 됩니다. 이 인덱스를 통해 값을 빠르게 찾을 수 있습니다.

특징

• 키를 사용해 빠른 액세스 가능
• 키의 순서 보장하지 않음
• 키 중복 불가, 값 중복 가능
• 해싱 충돌 발생 가능

키는 숫자뿐만 아니라 문장까지도 가능해 그 수는 무궁무진합니다. 그러나 인덱스는 배열의 크기보다 작은 정수로 한정되어 있어 많은 키가 있다면 서로 다른 키가 동일한 인덱스를 가질 가능성이 있습니다. 이렇게 서로 다른 키가 동일한 해시 코드를 갖는 것을 **해싱 충돌(Hashing Collision)**이라고 합니다.

해싱 충돌 해결 방법

• 체이닝(Chaining)
• 개방 주소법 (Open Addressing)
• 재해싱 (Rehashing)
• 버킷 확장 (Bucket Expansion)
• 커스텀 해시 함수 사용

Set

문제 패턴

예시 문제 기반 설명

Java

Python

JavaScript

실수 포인트