HASH TABLE

HASH TABLE ?

해시 테이블은 키를 값에 매핑할 수 있는 구조인 연관 배열 추상 자료형(ADT)을 구현하는 자료구조이다.

 

특징으로는 대부분의 연산이 시간복잡도 O(1)을 가진다.

데이터 양에 관계 없이 빠른 성능을 기대할 수 있다.

 

파이썬에서는 해시테이블 대신 딕셔너리를 이용해 사용한다.

HASH FUNTION ?

임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수

ABC -> A1

1234BC -> CB

AB23D -> D5

위와 같이 화살표 왼쪽 값들은 각각 다른 크기를 지닌 문자열이지만 특정 함수를 통과하면 고정 크기 값으로 매핑된다.

여기서 화살표 역할을 하는 함수가 해시 함수이다.