☑️ Hash 종류
해시(hash), 해시 함수(hash function), 해싱(hashing), 해시 테이블(hash table)
해시 Hash
전화번호부, 탐색에 용이
Key-value를 쌍의 형태로 데이터를 저장하는 자료구조, 알고리즘
Key값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어나게 된다.
해시 함수 Hash Function & 해싱 Hashing
Key값을 고정된 길이의 Hash로 변환하는 역할 → 해시함수
해시 함수에서 Key값을 Hash(Hash Value, Hash Code)로 변환하는 과정 → 해싱
변환된 Hash 값이 데이터 저장위치(주소값)가 된다
해시 충돌 : 서로 다른 Key가 같은 Hash값을 가지게 되는 것. 최대한 줄이는 코드를 작성해야한다.
해시 테이블 hash table
연관 배열구조를 이용하여 데이터를 Key와 Value로 저장하는 자료구조
배열에서? Key값에 숫자만 가능
그러나? Hash Table에서는 문자열 또한 Key (Map에서는 함수도 가능)
Hash Function을 통해 빠른 탐색이 가능 -> O(1)
hash(key) {
let id = 0;
for (let i = 0; i < key.length; i++) {
id += key.charCodeAt(1) * 100;
}
return id % this.size;
}ex) 해시함수로 해시 테이블 구현
key를 받아서, 새로운 id 값의 주소를 return 해준다. 문자열을 key 값으로 하여 저장!
☑️ 자바스크립트 Map 객체
자바스크립트에서는 일반 배열의 Key 값에 문자열 String을 사용할 수 있다.
const hashArr = [];
hashArr["나이"] = 23;
hashArr["직업"] = "개발자";
console.log(hashArr["나이"]);
///23
console.log(hashArr);
///[ '나이': 23, '직업': '개발자' ]Hash 테이블을 더 쉽게 사용할 수 있도록 하는 자료구조
key가 있는 데이터를 저장하는데 쓰이는 자료구조
키-값 쌍과 키의 원래 삽입 순서를 기억하고, 활용한다.
Map - JavaScript | MDN
Map 객체는 키-값 쌍과 키의 원래 삽입 순서를 기억합니다. 모든 값(객체 및 원시 값 모두)은 키 또는 값으로 사용될 수 있습니다.
developer.mozilla.org
메서드 new Map(), .set, .get, .has, .delete, .size
// Map 객체 생성
const map = new Map();
// key를 이용해 value값을 저장
map.set('a', 1);
map.set('b', 2);
map.set('c', 3);
// key에 해당하는 value를 반환, 1
console.log(map.get('a'));
// key값 탐색 true
console.log(map.has('a'));
// false
console.log(map.has('aa'));
// 삭제 true
map.delete("a");
// 크기 1 -> b,c
console.log(map.size);map 탐색 + 출력
//key, value 쌍으로 출력
for (let [key, value] of map) {
console.log(key + ' = ' + value)
}
//key만 출력
for (let key of map.keys()) {
console.log(key)
}
//value만 출력
for (let value of map.values()) {
console.log(value)
}
☑️ 배운점
해시를 자바스크립트로 풀면서 생긴 궁금증을 풀 수 있었다.
직접 문제에 적용하고 싶다.
#참고
유튜브 - 해시 Hash 알고리즘 설명 5분만에 이해하기