📌 해시 테이블과 해시 함수
🧠 해시 테이블이란?
해시 테이블(hash table)은 쌍으로 이뤄진 값들의 리스트다.
- 첫번째 항목을 키(key), 두번째 항목을 값(value)이라 부른다.
- 해시 테이블은 배열처럼 내부적으로 데이터를 한 줄로 이뤄진 셀 묶음에 저장한다.
🧠 해싱과 해시 함수
- 해싱(hasing): 문자를 가져와 숫자로 변환하는 과정
- 해시 함수(hash function): 글자를 특정 숫자로 변환하는 데 사용한 코드
- 해시 함수의 조건
: 동일한 문자열을 해시 함수에 적용할 때마다 항상 동일한 숫자로 변환해야 한다. 주어진 문자에 대해 반환하는 결과가 일관되지 않으면 그 해시 함수는 유효하지 않다. - 해싱하는 과정
1. '키'에 해시 함수를 적용하여 해싱한다.
2. 해당 숫자의 인덱스에 '값'을 저장한다.
👀 해시 테이블 룩업
- 해시 테이블의 대전제 - "키가 값의 위치를 결정한다"
- 룩업 시 키를 해싱해서 숫자로 바꾼 후, 그 수의 인덱스로 바로 가서 저장된 값을 추출한다.
- 값으로 한 번에 키를 찾을 순 없다. (단방향 룩업)
💥 충돌 해결과 효율적인 해시 테이블 만들기
- 충돌(collision): 이미 채워진 셀에 데이터를 추가하려 할 때 발생한다.
→ 셀에 '하나'의 값을 넣는 대신 '배열'로의 참조를 넣는 방법으로 해결 (분리 연결법, separate chaining)
- 해시 테이블 효율성의 세 가지 요인
- 해시 테이블에 얼마나 많은 데이터를 저장하는가
- 해시 테이블에서 얼마나 많은 셀을 쓸 수 있는가
- 어떤 해시 함수를 사용하는가
- 특히 3번에 관해서,
좋은 해시 함수란 사용 가능한 모든 셀에 데이터를 분산시키는 함수다. 데이터를 넓게 퍼뜨릴수록 충돌이 적다. - 좋은 해시 테이블은, 많은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌을 피한다.
📌JS에서의 해시 테이블과 해시 맵
- 자바스크립트에서 해시테이블 기반으로 동작하는 주요 자료구조로는
Map,Object,Set이 있다.
※ 해시테이블은 저수준의 자료구조, Map/Object/Set은 그걸 활용한 고수준 자료구조
- 해시 맵(Hash Map)은 해시 테이블의 구현 방식 중 하나로, 내부적으로 해시 테이블을 사용하여 데이터를 저장한다.
→ 자바스크립트에서는 Map 객체가 해시 맵의 기능을 한다.
MapvsObject- 자바스크립트에서
Object와Map은 모두 키-값 쌍을 저장할 수 있지만,Map이 해시 맵의 특성을 제대로 갖춘 자료구조 Object는 문자열 키만 사용 가능하고, 순서를 보장하지 않으며, key 개수 세기나 순회가 번거롭다.Map은 모든 값을 키로 쓸 수 있고, 입력 순서를 유지하며, 해시 테이블 기반으로 더 빠르고 안정적인 성능을 제공한다.
- 자바스크립트에서
- 추가적인 내용(해시맵 문법 등)은 참고한 블로그에서 더 확인할 수 있다.
- 참고한 블로그
[자료구조] 해시테이블(HashTable), 해시맵(HashMap) in Javascript
[JS] 📚 자바스크립트 자료형 Map 🚩 정리 - 참고한 책: 누구나 자료구조와 알고리즘(개정2판)(제이 웬그로우)
- 참고한 블로그
