- 해시 테이블 : (key, value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있다.
- 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.
- 해시 테이블은 각각의 key 값에 해시함수를 적용해 배열의 고유한 index를 생성하고 이 index를 활용해 값을 저장하거나 검색한다.
- 따라서, 이러한 해싱 구조로 데이터를 저장하면 index를 통해 key 값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다.
- 해시테이블의 평균 시간복잡도는 O(1)이지만, 데이터의 충돌이 발생하는 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로 O(N)까지 시간복잡도가 증가할 수 있다.
- 해시 함수 : 해시 테이블의 고유한 인덱스 값을 설정하는 함수이다. 대표적인 해시 함수로는 아래의 3가지가 있다.
1. Divistion Method : 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.
2. Digit Folding : 각 key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
3. Multilplication Method : 숫자로 된 key 값과 0과 1 사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 계산한다. h(k)=(kAmod1) x m
- 해시 테이블에서는 해시 함수를 통해 설정한 고유한 인덱스 값이 충돌하는 경우가 있다. 해시 테이블에서는 충돌에 의한 문제를 분리연결볍(Separate Chaining)과 개방 주소법(Open Addressing) 크게 2가지로 해결하고 있다.
1. 분리 연결법(Separae Chaning)
- 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메로리를 사용하여 다음 데이터의 주소를 저장하는 방법이다.
- 해시 테이블의 확장이 필요 없고 간단하게 구현이 가능하며 손쉽게 삭제할 수 있다는 장점이 있지만, 데이터의 수가 많아지면 동일한 버킷에 chaining 되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소한다는 단점이 있다.
2. 개방 주소법(Open Addressing)
- 분리 연결법과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다.
- 개방 주소법을 구현하는 대표적인 방법으로는 3가지가 있다.
1. Linear Probing : 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
2. Quadratic Probing : 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방법이다.
3. Double Hashing Probing : 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다.
'이것저것 스터디📚 > JavaScript' 카테고리의 다른 글
| 리액트에서 list 태그에 key 값을 추가해야하는 이유 (0) | 2023.11.21 |
|---|---|
| useReducer를 활용한 상태관리 흐름 (1) | 2023.11.21 |
| Prototype을 이용해서 상속을 구현하는 방법 (1) | 2023.10.24 |
| this (0) | 2023.10.24 |
| 이벤트 위임 (0) | 2023.10.24 |
