📌 해시 Hash

어떠한 데이터를 고정된 크기의 특정 숫자로 바꿔주는 방법

• 이렇게 바뀐 숫자가 데이터가 저장될 위치(index)가 된다.
• Object, Map, Set 등 → 해시 구조 기반

📌 해시 테이블 Hash Table

(Key, Value) 쌍을 저장할 수 있는 자료구조
내부적으로 해시 함수를 통해 Key를 인덱스로 변환하고, 해당 위치에 데이터를 저장

장점

• key를 통해 바로 인덱스를 계산하므로 탐색 속도가 O(1)로 빠르다
• 문자열, 숫자, 객체 등 다양한 자료형을 key로 사용 가능하다
• 특정 key만 골라서 손쉽게 삭제 가능하다

예시

const map = new Map();
map.set("apple", 100);
map.set("banana", 200);

console.log(map.get("apple")); // 100

📌  해시 충돌 Hash Collision

해시 함수에 입력할 수 있는 데이터는 무한한데, 출력으로 나올 수 있는 해시 값은 유한하기 때문에(비둘기집 원리) 서로 다른 Key가 같은 인덱스를 가지는 현상이 발생한다. 이를 해시 충돌이라고 한다.

"apple" -> 3
"banana" -> 3 

이를 해결하기 위해서는 다음과 같은 방법이 있다.

• 체이닝 Chaining: 같은 인덱스에 여러 값을 리스트로 저장
• 개방 주소 방법 Open Addressing: 빈 자리를 찾아서 저장

📌 시간 복잡도

평균적으로는 매우 빠르지만, 해시 함수가 불균형하거나 충돌이 많으면 성능이 저하된다.

연산	평균	최악 (충돌 심할 때)
검색	O(1)	O(n)
삽입	O(1)	O(n)
삭재	O(1)	O(n)