8주차 배운 내용

해시테이블(hash table) , 셋(set), 맵(map)에 대해 배웠습니다.

해쉬테이블

정의

해쉬테이블은 연관배열구조를 가지는 자료구조로 배열의 인덱스 같은 키(key)와 그 키에 해당하는 값(value)를 가지고 있다. 해쉬테이블의 장점은 빠른 데이터 읽기, 삽입, 삭제이며 점근표기법 비용이 O(1)이다. 공간을 효율적으로 사용하는 편이나 키를 인덱스처럼 그대로 사용할 경우 메모리를 많이 차지하고, 중복되는 키로 인해 충돌 위험이 생긴다.

해쉬함수

해쉬 함수는 임의의 크기를 가진 키를 고정된 해쉬값으로 변환하여 데이터로 맵핑하는 함수로, 고정된 길이를 가지고 있기 때문에 안정적이고 효율적으로 저장 공간을 운영할 수 있다.

가장 이상적인 해쉬 함수는 키들이 균듕하게 해시 테이블의 인덱스로 변환하는 함수이다.

대표적인 해시 함수

1. 중간 제곱(Mid-square) 함수

키를 제곱한 후, 적절한 크기의 중간 부분을 해시 값으로 사용

2. 접기(Folding) 함수

큰 자릿수를 갖는 십진수를 키로 사용하는 경우
몇 자리씩 일정하게 끊어서 만든 숫자들의 합을 이용해 해시값 생성

3. 곱셈(Multiplicative) 함수

1보다 작은 실수 δ를 키에 곱하여 얻은 숫자의 소수 부분을 테이블 크기 M과 곱해서 나온 값의 정수 부분을 해시 값으로 사용

4. 나눗셈(Division) 함수

키를 소수(Prime) M으로 나눈 뒤, 나머지를 해시 값으로 사용
h(key) = key % M. 따라서 해시 테이블의 인덱스는 0에서 M-1
가장 널리 사용되는 해시 함수

해쉬충돌

해쉬 함수를 사용하더라도 결국 중복되는 키는 생성될 수 있으며, 같은 키를 가지는 다른 값을 가진 요소가 생겼을 때를 해쉬 충돌이라고 한다.

해결방법

1. 개방 주소법(Open Addressing)

해시 테이블 전체를 열린 공간으로 가정하고 충돌된 키를 일정한 방식에 따라서 찾아낸 empty 원소에 저장
선형 탐색(순차적 탐색) : 해시 충돌 시 다음 버킷에 저장
제곱 탐색 : 해시 충돌 시 제곱만큼 건너 뛴 버킷에 데이터를 저장
이중 해시 : 해시 충돌 시 다른 해시함수를 한 번 더 적용한 결과 저장

2. 폐쇄 주소법(Closed Addressing)

키에 대한 해시 값에 대응되는 곳에만 키를 저장
충돌이 발생한 키들은 한 위치에 모여 저장
이를 구현하는 가장 대표적인 방법 : 체이닝(Chaining)

3. 체이닝

충돌 시 연결 리스트에 추가하는 방식
중복된 해시 값이 있는 경우, 해당 슬롯을 연결 리스트로 저장 (충돌 해결)
연결 리스트로 인해 최악의 경우 수행 시간이 O(n)이 됨

셋(Set)

데이터의 중복이 존재하지 않고 고유의 키와 값을 갖는다. 해쉬 테이블을 사용해서 해쉬 셋이라고도 불린다.

• 입력된 키를 해쉬로 변환
• 해시 코드를 인덱스로 한 배열에 해당 인덱스를 찾아 값 저장
• 배열 길이가 초과되는 경우에는 길이의 나머지를 구해 링크드 리스트로 추가

특징

• 인덱스가 존재하지 않고 오직 키만 사용한다.
• 충돌 발생 경우가 없다
• 빠른 속도의 검색이 가능하다.

해쉬 테이블 VS 해쉬 셋

	해시 테이블	해시 셋
데이터 추출 형태	Data추출은iterator이동	Data추출은Key-Value를 이용
중복허용	O	X
index	O	X
키 값에 null 허용	O	X
동기화	비동기화(스레드로부터 안전X)	동기화(스레드로부터 안전O)

Map VS Object

	Object	Map
키의 타입	string, symbol	모든 값
크기	수동으로 추적	내부 프로퍼티(Size)
사용 경우	적용해야 하는 로직이 있는 경우 (Object.defineProperty)	실행 시 키를 알 수 없고 모든 키와 값들이 동일한 경우

• Map은 삽입된 순서대로 반복된다.
• Map의 경우 이터러블 객체가 반환되어 for ... of 함수를 사용할 수 있고, 배열 스프레드 오퍼레이터와 배열 비구조화 할당을 사용할 수 있다.