정의

key와 값을 받아 key를 해싱하여 나온 값(인덱스)을 저장하는 선형 자료구조 O(1). 대부분 O(1), 1 step으로 끝나므로 매우 빠르지만 가끔 동일 key값 collision이 발생해서 완벽한 O(1)은 아님. 배열/리스트: O(n) 보다 빠름.
자바스크립트 - Map, Set, 객체 / 파이썬 - Dictionary

탄생 설명

직접 주소 테이블의 공간의 효율성이 좋지 않음을 해결하기 위해 나온 자료구조. 해시 테이블은 담고자 하는 데이터의 개수보다 테이블의 크기를 작게하고 싶다는 의지에서 나온 자료구조이기 때문에 충돌을 해결할 수 있는 방법 또한 같이 고안되었다.

해시=index=key값

키 값이 해시 함수로 변환된 것

해시함수

key값을 고정된 길이의 해시로 변경해주는 역할

좋지 않은 해시 함수

어떤 값을 넣어도 똑같은 해시를 뱉어내는 해시 함수는 좋은 함수가 아니다. 따라서, 최대한 충돌을 방지해야 좋은 해시 함수이다.

해시 테이블

key(해시)와 value값을 가진 자료구조

해시 테이블 사용이유 예시: 빠르게 정보를 파악할 때!

1. 연결 리스트: O(n) - 정보 추가 및 삭제는 빠르지만 찾고 싶을 때 O(n) 시간복잡도
2. 배열: O(n) - 인덱스 값을 모를 경우 선형 탐색 해야하기 때문에
   ["A", "B", "C", "D", "E"] - D 찾아줘: 탐색해야함 O(n)
3. 해시 테이블: O(1) - 이름을 key로 설정하여 탐색,삽입,삭제가 모두 O(1)

활용 예시

1. 중복 서로 비교
2. 애너그램 -> 정렬 후 비교
3. 같은 카테고리끼리 정리 및 조합, 비교 후 정렬

Collision 해결법

1. 선형 탐사법 - 충돌된 값을 옆으로 한칸 이동
2. 제곱 탐사법 - 충돌된 값을 제곱만큼 옆으로 이동
3. 이중 해싱 - 충돌 발생시 다른 해시 함수를 사용
4. 분리 연결법 - 연결 리스트처럼 충돌 발생시 리스트에 값을 추가

JS의 해시 (Map, Set)

Map은 key가 있는 데이터를 저장하는데 쓰이는 자료구조이다. 이때 key 값은 문자열 또한 가능하다. 따라서 이를 가지고 hash에 이용할 수 있다.

• new Map()
  -> Map 객체를 만들때 쓰인다.
• map.set(key,value)
  -> key를 이용해 value값을 저장한다.
• map.get(key)
  -> key에 해당하는 value를 반환한다.
• map.has(key)
  -> key가 존재한다면 true, 없다면 false를 반환한다.
• map.delete(key)
  -> key에 해당하는 값을 삭제한다.
• map.size
  -> 요소의 개수를 반환한다.

Map객체 예시 코드 (해시는 이것들 사용하면 됨!!!!)

// Map을 통해 해쉬 테이블 생성
const hashMap = new Map();

// set함수를 통해 key, value 값 대입
hashMap.set("나이", 25);
hashMap.set("직업", "개발자");
hashMap.set("가족", ["부","모","남동생"]);
hashMap.set("account", {id:"aaa",password:1111});

console.log(hashMap); //{ "나이" => 25, "직업" => "개발자", "가족" => ["부","모","남동생"], account => {...}}

console.log(hashMap.size); // 4

// has, get을 통한 if문
if (hashMap.has("나이")) {
  (hashMap.get("나이")); // 23
  (hashMap.get("가족")[0]); // "부"
  (hashMap.get("account").id) // "aaa"
}

hashMap.delete("전화번호");

if (!hashMap.has("전화번호")) {
  console.log("전화번호가 삭제되었습니다.",  hashMap.size); // 전화번호가 삭제되었습니다.
}

// Map객체 순환하기
for(let[k, v] of map){ 
    console.log(k); 
}

// Map객체 정렬하기 (해시에서 정렬된 keys, values값 가져오기)
 let hash = new Map();
  hash.set(1, 0.1);
  hash.set(2, 0.5);
  hash.set(3, 0.3);
  hash.set(4, 0.4);

 let sortedHash = [...hash].sort((a, b) => b[1] - a[1])
 sortedHash.map((num) => num[0]); // [2, 4, 3, 1] 정렬된 keys
 sortedHash.map((num) => num[1]); // [0.5, 0.4, 0.3, 0.1] 정렬된 values

 let newHash = new Map(sortedHash); // 정렬된 해시테이블
// {2 => 0.5, 4 => 0.4, 3 => 0.3, 1 => 0.1,}

Set객체

Map과 달리 key가 없고 value만 있다.

//예시
const set = new Set();

set.add({id:"aaa",password:1111}); // key가 없다
set.add({id:"bbb",password:2222});
set.add({id:"ccc",password:3333});

for(let value of set){ 
    console.log(value.id); 
}