![[자료구조] Hash Table 의 hash collision 과 Worst Case Lookup Time](https://img.zoomtrend.com/2018/03/22/a0272856_5a7c01457c184.png)
해시 테이블은 Key,Value 형태로 데이터를 저장하는 자료구조이다. 저장시에 입력받은 Key 는 Hash Function 을 거쳐 Hashed Value가 되고,이를 고유 키값으로삼아 Hash table 은 최종적으로 해당 Value 를 저장한다. 일반적인 경우, Hash Table 에서 특정 Key를 찾아내는 시간복잡도(Lookup Time Complexity) 는 O(1) 이다. 그러나, 최악의 경우 Hash Table에 넣고자 하는 데이터의 Hashed Key Collision 현상이 연속적으로 발생하면 아래 이미지의 152번 bucket 과 같이 linked list 형식으로 이루어진 내부 자료구조를 O(N) 시간복잡도를 가지고 탐색해야 원하는 데이터를 얻을 수 있다.끝 !!