chaeyoung

[Data Structures] 해시맵

배열과 연결리스트는 순차적으로 데이터를 탐색해야 하기 때문에 특정 값을 찾는 데 시간이 오래 걸린다.

만약 수백만 개의 데이터 중에서 특정 값을 찾는다면? 이런 문제를 해결하기 위해 등장한 것이 바로 해시맵이다.

🗂️ 해시맵이란?

🔑 기본 개념

해시맵(HashMap)은 키(Key) 와 값(Value) 의 쌍으로 데이터를 저장하는 자료구조다. 마치 사전처럼 단어(키)를 찾으면 그에 해당하는 뜻(값)을 빠르게 찾을 수 있다.

  • 키(Key): 데이터를 식별하는 고유한 값
  • 값(Value): 실제 저장하고자 하는 데이터
  • 해시 함수: 키를 배열의 인덱스로 변환하는 함수

hashmap

// 해시맵 예시
const phoneBook = new Map();

phoneBook.set("김철수", "010-1234-5678"); // 키: "김철수", 값: "010-1234-5678"
phoneBook.set("이영희", "010-9876-5432"); // 키: "이영희", 값: "010-9876-5432"
phoneBook.set("박민수", "010-5555-1234"); // 키: "박민수", 값: "010-5555-1234"

console.log(phoneBook.get("김철수")); // "010-1234-5678" 즉시 반환!

🔧 해시 함수의 동작 원리

해시 맵의 핵심은 해시 함수(Hash Function) 다. 이 함수는 키를 받아서 배열의 인덱스로 변환한다.

hash-function

function simpleHash(key, arraySize) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i); // 문자의 ASCII 코드 값을 더함
  }
  return hash % arraySize; // 배열 크기로 나눈 나머지를 인덱스로 사용
}

// 예시: "김철수"의 해시값 계산
// '김' = 44608, '철' = 52384, '수' = 49688
// 합계: 44608 + 52384 + 49688 = 146680
// 146680 % 10 = 0 (인덱스 0에 저장)

simpleHash("김철수", 10); // 결과: 0
simpleHash("이영희", 10); // 결과: 7

이렇게 계산된 인덱스 위치에 데이터를 저장하고, 나중에 같은 키로 검색할 때도 동일한 인덱스에서 바로 찾을 수 있다.

⏱️ 시간 복잡도

해시맵의 가장 큰 장점은 빠른 검색 속도다!

연산 시간 복잡도
삽입 O(1)
삭제 O(1)
검색 O(1)

배열이나 연결리스트에서 특정 값을 찾으려면 O(n)의 시간이 걸리지만, 해시맵은 평균적으로 O(1)의 시간만 걸린다!

⚠️ 해시 충돌과 해결법

💥 해시 충돌이란?

서로 다른 키가 같은 해시 값을 가지는 경우를 해시 충돌(Hash Collision)이라고 한다.

simpleHash("A", 5); // 결과: 0 (A의 ASCII = 65, 65 % 5 = 0)
simpleHash("F", 5); // 결과: 0 (F의 ASCII = 70, 70 % 5 = 0) - 충돌!

아무리 좋은 해시 함수라도 완전히 충돌을 피할 수는 없다. 따라서 충돌이 발생했을 때 이를 해결하는 방법이 필요하다.

🔗 체이닝

같은 인덱스에 여러 데이터가 들어올 경우, 연결리스트를 사용해서 데이터들을 연결하는 방식이다.

chaining

  • 입력 데이터: "A" → "Apple", "F" → "Fruit", "B" → "Banana"

  • "A"와 "F"는 모두 인덱스 0으로 해시된다.

  • 인덱스 0에 연결 리스트를 만들어 두 데이터를 차례로 연결해서 저장한다

🏃 개방 주소법

충돌이 발생하면 다른 빈 공간을 찾아서 데이터를 저장하는 방식이다.

선형 탐사

충돌이 발생하면 다음 인덱스를 차례대로 확인하여 빈 공간을 찾는다.

linear-probing

  • 처음에는 인덱스 0에 "Apple", 인덱스 2에 "Banana"가 저장되어 있다.

  • "Fruit"는 인덱스 0으로 해시되지만, 이미 데이터가 있어 충돌이 발생한다.

  • 다음 인덱스인 1을 확인해 비어 있으므로 "Fruit"를 인덱스 1에 저장한다.

✅ 해시맵의 장단점

👍 장점

  • 빠른 검색: 평균 O(1) 시간에 데이터를 찾을 수 있다.

  • 유연한 키: 문자열, 숫자 등 다양한 타입을 키로 사용할 수 있다.

  • 동적 크기: 필요에 따라 크기를 조절할 수 있다.

  • 직관적: 키-값 쌍으로 데이터를 관리하여 이해하기 쉽다.

👎 단점

  • 메모리 사용량: 해시 테이블을 위한 추가 공간이 필요하다.

  • 해시 충돌: 최악의 경우 O(n) 시간이 걸릴 수 있다.

  • 순서 보장 안됨: 데이터의 삽입 순서가 보장되지 않는다.

  • 해시 함수 의존성: 좋은 해시 함수 설계가 성능에 큰 영향을 미친다.

💡 언제 사용할까?

해시맵이 유리한 경우

  • 빠른 검색이 필요할 때
  • 키-값 쌍으로 데이터를 관리할 때
  • 중복 검사나 빈도수 계산이 필요할 때
  • 캐시 구현이 필요할 때

다른 자료구조가 유리한 경우

  • 데이터의 순서가 중요할 때 → 배열, 연결리스트
  • 범위 검색이 필요할 때 → 이진 검색 트리
  • 메모리 사용량을 최소화해야 할 때 → 배열

Leave a comment

You may also enjoy