⚡ 자료구조 - 해시 테이블

🔹 해시 테이블

• 키를 해시 함수로 변환해 데이터를 저장하는 자료구조로, 배열 기반이며 충돌 해결 방법이 중요함
• 해시 함수의 역할과 충돌 해결 방법을 이해해야 함
• 장점: 평균적으로 검색, 삽입, 삭제가 매우 빠름
• 단점: 충돌이 발생하면 성능 저하가 있고 해시 함수 설계가 중요하며 메모리 사용이 많을 수 있음

▫️ 맵(Map)

• 키와 값의 쌍을 저장하는 자료구조로, 보통 해시 테이블로 구현됨
• 해시맵의 내부 구조와 키 중복 처리 방식을 이해해야 함
• 장점: 키를 통해 값에 빠르게 접근하고 수정할 수 있으며 키 중복을 허용하지 않음
• 단점: 키에 대한 해시 함수 성능에 크게 의존하며 메모리 사용량이 증가할 수 있음

▫️ 셋 (Set)

• 유일한 값만 저장하는 자료구조로, 내부적으로 맵과 유사하게 구현됨
• 셋의 중복 제거 기능과 멤버십 테스트가 중요한 상황을 설명할 수 있어야 함
• 장점: 중복된 값을 허용하지 않으며 멤버 존재 여부를 빠르게 검사할 수 있음
• 단점: 값 자체가 키 역할을 하기 때문에 복잡한 데이터 구조에는 부적합할 수 있음

▫️ 차이점 정리

구분	해시 테이블	맵	셋
저장 방식	키를 해시 함수로 변환해 저장	키와 값 쌍으로 저장	유일한 값만 저장
목적	키 기반 빠른 검색, 삽입, 삭제	키로 값에 접근하고 관리	중복 없는 값 저장 및 빠른 검색
중복 허용	없음	없음	없음
주요 연산	검색, 삽입, 삭제	키로 값 조회 및 수정	값 존재 여부 확인, 추가, 삭제
구현	배열 기반 해시 함수와 충돌 해결법	해시 테이블 기반이 일반적	해시 테이블이나 트리 기반

🔹 해시 함수 역할과 충돌 해결 방법(체이닝, 오픈 어드레싱 등)

• 해시 함수는 임의 크기 데이터를 고정 크기 값으로 바꾸는 함수
• 해시 테이블에서 키를 해시 함수에 넣어 배열 인덱스로 바꿔 저장하거나 검색
• 좋은 해시 함수는 서로 다른 키가 같은 인덱스로 가는 충돌을 최소화해야 함
• 충돌은 서로 다른 키가 같은 인덱스로 매핑될 때 생김.
• 해결 방법은 두 가지임.

▫️ 체이닝

• 같은 인덱스에 연결 리스트 같은 구조로 여러 데이터를 묶어 저장함
• 충돌 발생해도 각 버킷에 여러 원소 저장 가능해서 구현 쉬움

▫️ 오픈 어드레싱

• 충돌 나면 테이블 내 다른 빈 공간 찾아 저장함
• 선형 탐사, 이차 탐사, 이중 해싱 등이 있음
• 메모리 효율 좋지만 탐색 시간이 길어질 수 있음.

🔹 해시맵 내부 구조와 키 중복 처리 방식

• 해시맵은 키와 값을 쌍으로 저장하는 자료구조
• 내부는 해시 테이블 쓰고, 키를 해시 함수에 넣어 인덱스 계산 후 값 저장
• 충돌 나면 체이닝이나 오픈 어드레싱으로 해결
• 키 중복은 같은 키가 여러 번 삽입될 때 발생
• 대부분 해시맵은 새 값이 기존 키 값 덮어씀
• 즉, 중복 키 허용 안 하고, 삽입 시 기존 키 있으면 값 갱신함

🔹 셋의 중복 제거 기능과 멤버십 테스트 중요 상황

• 셋은 중복 허용 안 하는 데이터 집합
• 내부는 해시맵과 비슷하며 값이 키 역할
• 중복 값 들어오면 기존 값 유지하고 새 값 무시
• 중복 제거는 데이터 정제, 필터링, 집합 연산 등에 중요함
• 멤버십 테스트는 특정 값 집합 포함 여부 빠르게 확인하는 작업
• 예로 사용자 권한 검사, 방문 페이지 추적, 실시간 중복 체크 등에 사용