1. 개념 : 왜 필요한가

• 배열에서 값을 찾으려면 처음부터 하나씩 훓어야 한다.

const arr = [7,3,9,1];
arr.includes(9); // 내부적으로 7 - 3 - 9 순서로 비교 O(n)

데이터가 100만개이면 최악의 경우 100만번을 비교한다. 해시맵은 "값의 위치를 계산으로 바로 알아낸다." 그래서 평균 1번에 찾는다. -> O(1)

비유 : 도서관에서 책을 찾을 때 책장을 처음부터 훓는 게 배열 방식 , 이 책은 3번 서가 5번째 칸이라고 청구 기호로 바로 가는게 해시 맵

2. 동작 방식(내부 원리)

• 해시맵의 내부는 배열(버킷) + 해시 함수

단계별 동작

저장 : set("apple", 100)

1. 해시 함수가 키 "apple"을 숫자로 변환 : hash("apple") = 48291

2. 배열 크기로 나눈 나머지로 인덱스를 정한다. : 48291 % 8 = 3

3. 배열의 3번 칸에 (apple, 100)을 저장한다.

조회 : get(apple)

1. 같은 해시 함수로 같은 인덱스(3)을 계산한다.

2. 3번 칸을 바로 열어 값을 꺼낸다. 훓지 않는다.

키 "apple - hash -> 48291 - %8 -> 3
버킷 배열 : [0],[1],[2],[3] = ("apple",100) ,[4], [5], [6], [7]

• 핵심은 같은 키는 항상 같은 인덱스가 나온다.

간단한 해시 함수 예 (이해용)

function hash(key, size){
 let sum = 0;
 for (const ch of key) sum += ch.charCodeAt(0); // 글자 코드를 더함.
 return sum % size;
}

hash("apple", 8); // 항상 같은 값

문제 1 : 글자에서 한번만 등장하는 가장 첫 문자

문제 1 (워밍업): 문자열에서 처음으로 한 번만 등장하는 문자의 인덱스를 반환하세요. 없으면 -1.

"leetcode"     → 0   (l)
"loveleetcode" → 2   (v)
"aabb"         → -1

코드

export function firstUniqChar(s) {
  // TODO
  let hashMap = new Map();
  for (let i = 0; i < s.length; i++) {
    hashMap.set(s[i], hashMap.get(s[i]) ? hashMap.get(s[i]) + 1 : 1);
  }
  console.log(hashMap);
  // 이건 해당 키 값을 찾는 법
  // for (let [key, value] of hashMap) {
  //   if (value === 1) {
  //     return key;
  //   }
  // }
  for (let i = 0; i < s.length; i++) {
    if (hashMap.get(s[i]) === 1) {
      return i;
    }
  }
  return -1;
}

해석

문제2.