인덱스를 알고 있는 상태에서의 배열 탐색속도와, 키 값을 알고 있는 상태에서의 해시 테이블 탐색속도는 누가 더 빠를까.
배열에서 인덱스를 통해 배열 요소에 접근하는 시간 복잡도는 O(1) 이다.
해시 테이블에서의 평균 시간 복잡도 또한 O(1) 이다. 하지만 해시테이블에서는 안좋은 경우 해시 충돌이 발생 할 수 있다. 이 케이스에서는 O(n)이 걸릴 수 있다.
또한, 해시 테이블같은 경우에는 키 값을 이용해서 해시함수를 수행하여 해시(코드) 값을 생성해야 하기 때문에 (미미하지만)추가적인 오버헤드가 있을 수 있다.
해시 테이블에서 두 개 이상의 서로 다른 키 값이 해시함수를 통해서 동일한 해시값을 반환하게 된다면, 데이터가 저장될 위치를 결정하기 위한 추가적인 메커니즘이 필요한데, 이를 해시 충돌이라고 한다.
이때, 사용되는 기법으로는 Chaining, Open Addressing 등이 있다.
