[Tech, etc.] Hash 검색 시간 복잡도(Search Time complexity)

 Hash에서 특정 key에 대한 value를 확인할 때 걸리는 시간 복잡도가 O(1) - Constant time 이라는 것에 대한 이해가 되지 않아 확인해보니 실제로는 O(1)보다는 오래 걸리지만 거의 그 즈음 걸리기에 O(1)으로 표기한다는 것을 알았다. 내가 잘못 이해하고 있었던 부분은 Search와 Index(Access)의 차이다.

 Search는 한 자료 구조(Data Structure) 안에서 특정 요소(element)를 검색하는 것을 의미하는 반면,

Index(Access)는 이미 어디 있는지 알고 이를 접근한다는 차이를 가지고 이해를 해야했다.

 List의 경우에도 Index를 알고 있다면 바로 접근이 가능 하기에 O(1)의 시간 복잡도를 갖지만, 특정 데이터(data)를 검색한다는 것은 List를 순회(Traverse)하며 일일이 찾아야 하기에 경우에 따라 O(n) 혹은 O(log n)의 시간 복잡도를 갖는 것이고, Hash는 Key와 Value라는 특성이 있기에 실제 Key에 대한 접근은 O(1) 이상의 시간이 걸리지만 Key만 접근하면 바로 Value를 반환(return)할 수 있기에 O(1)의 시간 복잡도를 갖는 것이다. 

 

참고

- https://cs.stackexchange.com/questions/150847/why-do-hash-tables-have-no-access-indexing-complexity-but-have-o1-search-com

- https://stackoverflow.com/questions/4363539/how-does-hashing-have-an-o1-search-time

- https://www.quora.com/Why-does-a-hash-table-have-O-1-search