해시 테이블은 어떤 방식으로 조회에 시간복잡도 O(1)을 보장하나요?

[SW-H]

1. 키로 hash를 구한다.
2. hash로 값(value)를 찾는다.

• 키(key)는 고유한 값
• 해시함수(hash function)의 결과로 나온 해시(hash)에 매칭되는 값(value)을 찾으면 된다. 이 때, 해시함수의 시간복잡도는 함께 고려하지 않는다.
  • 최악의 경우 O(n) : 해시 충돌로 인해 모든 bucket의 value들을 찾아봐야 하는 경우 John과 Sandra의 hash가 같다. 이런 현상을 hash collision이라고 한다

[yerimstar]

해시 테이블은 탐색에 특화 된 자료구조로 탐색 시 평균 O(1)의 시간 복잡도를 갖는다. 이는 배열에서 index를 아는 상태에서의 접근하는 것과 동일한 시간 복잡도를 보인다. 하지만 주의해야 할 것은 평균 O(1)이라는 시간 복잡도는 해시 충돌이 일어나지 않는 이상적인 상황을 고려한 것이다. 해시 충돌이 일어날 수록 시간 복잡도는 최악인 O(N)에 수렴한다. 만약 수정된 Chaining방식을 이용하여 해시 충돌된 엔트리들을 Red-Black Tree로 연결한다면 최악의 경우라도 O(logN) (밑은 2)의 시간복잡도를 갖게 된다.

https://you88.tistory.com/38

[anuu0916]

O(1)의 뜻은 인풋 크기에 비례하지 않는다는 뜻일뿐 연산 횟수를 한번만 해야 O(1)인건 아닙니다. 어떤 알고리즘이 인풋 크기와 관계 없이 2^100번에 연산을 실행한다고 해도, 실제로는 엄청 느리겠지만 이론적으로 보자면 O(1) 알고리즘입니다.

해시 테이블의 경우 버킷마다 슬롯이 여러개 있다고 해도 평균적으로 그 슬롯 개수가 인풋 크기에 비례하지 않는다면 평균 시간복잡도도 O(1)이 되는겁니다.

출처 : https://okky.kr/articles/1271160