해시맵(Hash Map)은 “키(key)”와 “값(value)”을 한 쌍으로 저장하고, **키를 해시 함수(hash function)**로 매핑해 내부 배열의 인덱스로 변환함으로써, 평균적으로 O(1) 시간 만에 값에 접근·삽입·삭제할 수 있는 자료구조입니다.

해시맵의 핵심 개념

1. 키와 값의 쌍
   • 각각의 원소는 (key, value) 형식으로 저장됩니다.
   • 예: { "apple": 3, "banana": 5 } 라는 해시맵은 "apple"이라는 키에 3이라는 값을, "banana"라는 키에 5라는 값을 연결합니다.
2. 해시 함수 (Hash Function)
   • 키를 내부 저장소(버킷)의 인덱스(주소)로 변환하는 함수입니다.
   • 예: "apple" → hash("apple") % capacity → 저장소의 0~(capacity-1) 사이 인덱스로 매핑
3. 버킷과 충돌 처리
   • 두 키가 같은 인덱스로 매핑되면 “충돌(collision)”이 발생합니다.
   • 주로 체이닝(chaining)(연결 리스트)이나 **오픈 어드레싱(open addressing)**으로 해결합니다.
4. 시간 복잡도
   • 평균: 삽입·삭제·조회 모두 O(1)
   • 최악: 충돌이 심해지면 O(n) (충돌 관리 방식에 따라 다름)
5. 사용 예시
   • 빈도 계산: 배열에서 각 원소가 몇 번 나왔는지 세기
   • 캐시 구현: 최근에 접근한 결과를 저장하여 빠르게 재사용
   • 집합(Set) 구현: 값의 존재 여부만 체크할 때

자바스크립트에서의 해시맵: Map

ES6부터는 내장 객체 Map이 해시맵 역할을 합니다.

• 생성: const map = new Map();
• 삽입: map.set(key, value);
• 조회: map.get(key);
• 삭제: map.delete(key);
• 크기: map.size

완성된 예제 코드

아래는 정수 배열에서 각 숫자의 등장 빈도를 해시맵(Map)으로 계산한 뒤, 가장 많이 등장한 숫자를 찾는 예제입니다.

/**
 * 배열에서 가장 자주 등장하는 숫자를 반환하는 함수
 * @param {number[]} nums - 정수 배열
 * @return {{value: number, count: number}} { value: 최빈값, count: 등장 횟수 }
 */
function mostFrequent(nums) {
  const freqMap = new Map();
  let maxCount = 0;
  let maxValue = null;

  // 1) 빈도 계산
  for (const num of nums) {
    const count = (freqMap.get(num) || 0) + 1;
    freqMap.set(num, count);

    // 최빈값 갱신
    if (count > maxCount) {
      maxCount = count;
      maxValue = num;
    }
  }

  return { value: maxValue, count: maxCount };
}

// 사용 예시
const data = [2, 3, 2, 5, 2, 3, 4];
const result = mostFrequent(data);
console.log(`가장 많이 등장한 값: ${result.value}, 횟수: ${result.count}`);
// 출력: 가장 많이 등장한 값: 2, 횟수: 3