Chaining을 쓰는 해시 테이블 시간복잡도 -탐색,삽입,삭제,

해쉬테이블 key 를 이용한 탐색

1. 원하는 key 를 가지고 있는 노드가 있는지 선형 탐색을 함
2. 원하는 데이터를 찾으면 value를 리턴
3. n개의 key-value가 동일한 인덱스에 저장될 경우 탐색하면 최악의 경우로 시간복잡도는 O(n)

해쉬테이블 key 를 이용한 삽입연산

1. 해쉬함수의 결과값을 이용해 배열의 인덱스에 접근
2. 저장된 링크드리스트에 원하는 키를 같는 노드를 탐색(같은 key에 저장되는 것을 막기 위해 탐색함)
3. 그후 링크드 리스트에 새로운 노드를 갖는 "강영훈"을 추가함

해쉬테이블 key 를 이용한 삭제연산

1. 해쉬함수의 결과값을 이용해 배열의 인덱스에 접근
2. 저장된 링크드리스트에 원하는 키를 같는 노드를 탐색(같은 key에 저장되는 것을 막기 위해 탐색함)
3. 그후 링크드 리스트에 새로운 노드를 갖는 "강영훈"을 삭제함

결국 한 인덱스에 여러 노드가 겹칠 일은 그렇게 자주 있는 일이 아니고 평균적으로 봤을 때 O(average) 시간 복잡도를 가지는데 average = n/m 계산 값으로써 해쉬테이블은 결국 O(1)의 시간복잡도를 가진다고 생각하면 된다. 하지만 최악의 경우 O(n)은 변함이 없다.