자료구조 ] Hash Table

자료구조 ] Hash Table

정의

key-value 의 map 자료구조이다.

hash table은 해시함수를 통해 얻은 해시를 배열의 인덱스로 환산해서 데이터에 접근한다.

특징 / 특이사항

인덱스를 가져오기 위한 해시함수는 해시 충돌(hash collision)이 발생할 수 있는데,

두개 이상의 다른 key에 대해 해시함수가 같은 index를 리턴하는 것을 의미한다.

이 충돌을 해결하기 위해 linked list를 이용해 구현하는 방법을 사용하곤 한다.

같은 index를 가지는 key-value 쌍을 linked list에 넣고 충돌이 발생할 경우 각 노드를 일일이 비교함으로 해결 할 수 있다.

시간복잡도

해시 충돌이 발생하지 않는다면 O(1)의 접근시간을 가진다. 최악의 경우, 모든 노드를 일일이 비교하며 찾아야 한다면 O(n)의 시간복잡도를 가질 수 있다.

용어

이름 설명 key 데이터를 찾을 키 hash function key를 받아 데이터가 들어있는 index를 리턴해주는 함수 bucket(slot) 데이터가 들어있는 장소

활용

데이터의 순서가 중요하지 않을 때 이용 한다.

한다. index를 사용하여 검색, 삽입, 삭제를 빠르게 계산해야 할 때 이용한다.

from http://jibsun-i.tistory.com/14 by ccl(A) rewrite - 2021-10-08 17:26:34