해시테이블 개념

※이 자료는 공부를 목적으로 출처에 기입한 여러 자료를 단순히 정리한 것입니다.

해시테이블

해시테이블은 키를 값에 매핑할 수 있는 구조인 연관 배열 ADT를 구현하는 자료구조이다. 컴퓨터는 숫자를 해석하는 것으로 컴퓨터에서 숫자는 해석에 따라 숫자, 글자, 픽셀, 명령어 등으로 나뉜다. 해시테이블은 자료구조 컨테이너 중 모든 것은 숫자로 표현한다는 특성을 이용해 효율적인 삽입, 삭제, 탐색이 가능한 자료구조이다.

해시함수(hash function)

해시 함수는 임의 길이의 데이터를 고정된 길이로 매핑하는 함수이다. 해시 함수의 결과 값을 해시 값, 해시 코드, 해시 체크섬, 간단하게 해시라고 한다. 성능이 좋은 해시 함수의 특징은 아래와 같다.

• 해시 함수 값 충돌의 최소화
• 쉽고 빠른 연산
• 해시 테이블 전체에 균일하게 분포된 해시 값
• 키의 모든 정보를 이용한 해싱
• 해시테이블 사용 효율이 높은 것을

로드 팩터(Load factor)

해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것.
자바 10에서는 0.75를 디폴트로 하고 시간과 공간 비용의 적절한 절충안이라고 한다.

$load factor = n/k$

Key -> hashcode -> index -> list

해시 함수의 입력(Key)의 결과값(hashcode)은 index가 되고 각 인덱스를 이용해 저장하고 구현하는 방식에 따라서 해시테이블 구조가 개별 체이닝, 오픈 어드레싱 등으로 나뉜다. 유튜브 엔지니어대한민국 채널에서는 리스트에 누적되는 방식으로 설명했다.

해시충돌(collision)

해시 함수의 결과 값은 해시 테이블에 고르게 분포되는 것이 성능에 좋다. 예를 들어 n개의 자료가 한 곳에 모여있다면 리스트 검색시에 값이 존재하지 않거나 마지막에 있는 경우에 최대로 O(n)의 시간이 필요하기 때문이다.

개별 체이닝

개별 체이닝은 해시 값이 같은 경우 순차적으로 들어오는 자료를 linked list 방식으로 연결한다.

오픈 어드레싱

오픈 어드레싱은 같은 해시 값이 입력되는 경우 해시 테이블의 다음 인덱스로 입력된다.

장점

삽입, 조회, 삭제가 빠르다.

O(1) ~ O(n)

단점

버킷 사이즈 만큼의 용량 제한이 있다.

자료의 순서를 고려하기 위한 컨테이너가 아니다.

해시함수의 결과가 몰리는 경향이 있을 수 있다.

삽입, 삭제, 탐색의 구현 (추후 링크 업로드)

Python 구현
Java 구현
C 구현

출처 :

[자료구조 알고리즘] 해쉬테이블(Hash Table)에 대해 알아보고 구현하기 엔지니어대한민국, Youtube
해싱, 해시함수, 해시테이블, ratsgo's blog
해시 함수, 위키백과
파이썬 알고리즘 인터뷰 11장 해시 테이블, 박상길