Set, Dictionary가 lists보다 탐색이 빠른 이유

List는 O(n)

학생이 20명 있는 반에서 특정 학생이 있는 지 확인하려면 한 명씩 대조하여 20번 확인하면 되기 때문에 List가 O(n) 인 것은 자연스럽다.

Hash table은 O(1)

그런데 어떻게 Set, Dictionary는 O(1) 에 확인할 수 있을까?
이는 Hash table 구조이기 때문이라고 한다.

쉽게 말하면 모든 학생들이 무작위로 있는 것이 아니라 지정 좌석이 있는 것이다. 그러면 A 학생이 있는 지 확인하려면 A 학생 자리만 확인하면 되므로 O(1)에 확인이 가능하다.

지정 좌석을 정하는 방법이 Hash 함수이다.

궁금한 점

• 그렇다면 Hash 함수는 어떻게 작동하는가?
• Hash 함수는 input은 임의의 길이의 자료들이다. 그렇다면 일대일함수가 되려면 output이 무한이므로 효율적이지 못할 것이다. 그러면 서로 다른 자료가 같은 Hash 값을 가지는 일이 있을텐데, 이를 어떻게 처리할까?
• Hash 함수의 output의 길이는 가변적일까 고정적일까? 그 길이를 어떻게 정하는 것이 가장 효율적일까?