HashMap?

키(Key) - 값(Value) 쌍으로 데이터를 저장하는 자료구조

• JavaScript에서는 Map, Object가 이와 유사하게 사용
• 해시 함수를 이용해 키를 인덱스로 변환, 그 인덱스에 값을 저장

HashMap 평균 시간복잡도

• 삽입 (Insert) : O(1)
• 삭제 (Delete) : O(1)
• 조회 (Get) : O(1)
• 단, 최악의 상황은 O(n)

Map()

const map = new Map();

map.set("name", "혜정");
map.set("age", 26);

console.log(map.get("name")); //혜정

Object

const obj = {
  name : "혜정",
  age : 26
};

console.log(obj["name"]); // 혜정

• 해당 객체에서 name, age는 key값이 된다.
• "혜정", 26 은 해당 키 값에 대한 value가 된다.

obj.email = "abc@naver.com";
obj.phone = "123-1234"

위와 같은 방법으로 객체의 프로퍼티 추가 가능

Object.keys(obj); // ['name', 'age', 'email', 'phone']
Object.values(obj); // ['혜정', 26, 'abc@naver.com', '123-1234']

• Object.keys(obj) : 객체의 모든 key들을 배열로 반환
• Object.values(obj) : 객체의 모든 value들을 배열로 반환

HashMap의 장점

• 빠른 데이터 검색 (Key 기반)
• 배열보다 유연한 키 설정 가능 -> Map 은 객체도 키로 가능
  

const key = {id : 1};
const map = new Map();

map.set(key, "혜정");

console.log(map.get(key)); // "혜정"
console.log(map); // Map(1) {size: 1, {id: 1} => 혜정}

• 이렇게 Map은 객체 자체를 key로 사용 가능, Object는 안됨!
• 문자열 키(obj['name'])는 이름표에 "홍길동"이라고 적는 것
• 객체 키는 홍길동의 주민등록증 전체를 이름표로 쓰는 것

HashMap의 단점

• 순서를 보장하지 않음 (Map은 삽입 순서 유지)
  • Map에 넣은 순서대로 키와 값이 저장되고, 순서가 바뀌지 않음.
  • Map을 사용할 때는 삽입 순서대로 데이터를 순회하고 싶을 때 유용함.
• 해시 충돌을 잘 관리하지 않으면 성능 저하 우려

Hash Collision?

서로 다른 키인데도, 해시 함수와 결과가 같은 인덱스가 나오는 상황

hash("apple") → 3
hash("pleap") → 3  // 서로 다른 키지만 같은 해시값

• 두 값이 같은 해시값을 가지고 같은 자리에 저장하려 해서 충돌

해시 충돌 해결 방식

1. 체이닝 (Chaining)

• 같은 인덱스에 여러 개의 값을 리스트로 연결해 저장
• 자바스크립트의 Map에서 주로 사용

Index 3: [ { key: "apple", value: "A" }, { key: "pleap", value: "B" } ]

2. 오픈 어드레싱 (Open Addressing)

• 충돌이 발생하면 빈 다른 인덱스 찾아 이동
• 대표 기법 : 선형 탐사(linear probing), 이차 탐사(quadratic), 이중 해싱(double hashing)

Index 3 : {}
Index 4 : {}

해시값 둘다 3 -> Index 3에서 충돌?
그러면 다음 값은 빈 인덱스인 Index 4에 추가

Index 3: { key: "apple", value: "A" }
Index 4: { key: "pleap", value: "B" }

iterable

• Object는 for...in만 사용 가능 -> 객체의 key (속성 이름)을 순회

const obj = { name: "혜정", age: 26 };

for (let key in obj) {
  console.log(key);       // name, age
  console.log(obj[key]);  // 혜정, 26
}

for (let v of obj) {
  console.log(v);  // TypeError: obj is not iterable
}

• Map은 for...of, spread 가능 -> 배열, 문자열, Map, Set 등의 값을 순회

const map = new Map();
map.set("name", "혜정");
map.set("age", 26);

for (let [key, value] of map) {
  console.log(key, value); // name 혜정, age 26
}

console.log([...map]); // spread
// 출력: [['name', '혜정'], ['age', 26]]