[2020. 10. 26 TIL] Data Structure - Hash Table

Hash table이란?

해시 테이블(해시 맵이라고도 한다)은 키와 값 쌍을 저장하기 위해 사용되는 자료구조이며, 키를 저장할 때 메모리 공간을 절약할 수 있도록 키를 '해시 함수'를 통해 특정 숫자값의 인덱스로 변환한다. 해시테이블은 필요할 때만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.

Hash table의 특징 정리

• 내부에 hash 함수를 가지고 있으며, 해시 함수를 통해 키를 특정 정수로 만들고 그것이 인덱스 값이 되어 배열에 넣어진다
• 배열의 크기(size)가 정해져있다.
• 출력값과 입력값을 1:1로 매핑할 수 있다.

유튜버 "엔지니어 대한민국"님의 설명이 이해하는데 많은 도움이 되었다.

Hash Function

해시 함수: 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

• 배열의 크기 안에 있는 값만 반환할 수 있어야 한다
• 입력값이 같으면, 항상 결과값이 같아야 한다
• 입력받은 key들을 직접 저장하지 않고 정수로 반환한다.

용어 정리

• storage : 데이터를 저장하는 배열
• bucket : 데이터가 들어갈 공간이며, 배열의 인덱스에 담겨있다

Collision

해시 함수를 통해 무한한 문자열을 한정된 인덱스에 할당하기 때문에, 필연적으로 중복된 값이 나오게된다. 이를 해시 충돌 (Collision)이라고 한다.