- 자바스크립트에서 해쉬테이블은 Object 객체이다. 자바에서는 map
- key와 value가 쌍으로 존재하는 객체이다.( key와 value의 쌍은 bucket이라고 부른다.)
- 일반 array은 선형검색을 해야하기 때문에 자료를 찾는데 기본적으로 시간이 오래걸린다. → O(n)
- 해쉬테이블을 사용하면 키만 알아도 value를 찾을수있기 때문에 시간복잡도가 대폭 줄어든다. → O(1)~ O(n)
사용법
- 찾고싶은 key값을 해쉬함수에 넣어서 해쉬테이블의 hash(indexkey)로 바꾼다.
ex) Fruit , Cake, Taco 를 key로 글자수를 hash(indexkey)로 바꾸는 해쉬함수에 넣고 변환해서 해쉬테이블에 넣으면, { 4: ["Cake","Taco"] , 5:"Fruit"} 와 같이되고, 중복되는 key가 발생 할 경우(해쉬충돌이락 부른다, 해쉬함수를 작성할 때 최대한 충돌이 나지않는 로직을 짜는게 중요하다.) 선형검색을 통해 값을 찾아줄 수 있다. (그래서 항상 시간복잡도 O(1)은 아니다!)
- 해쉬테이블에 변환한 index(key)를 통해 value값을 찾아준다
장점
- 적은 리소스로 많은 데이터를 효율적으로 관리 가능.
- 배열의 인덱스를 사용하기 때문에 빠른 검색, 삽입, 삭제
- Key와 Hash에 연관이 없어서 보안이 좋음.
- 데이터 캐싱에 많이 사용.
- 중복 제거 유용.
단점
- 충돌 발생 가능성
- 공간 복잡도 증가
- 순서 무시
- 해쉬함수에 의존
HashMap vs HashTable
HashTable :
- 동기
- key-value 값으로 null 미허용
- 비교적 충돌 덜 발생
HashMap
- 비동기
- key-value 값으로 null 허용