CareTim

List 에서 특정원소를 찾기 위해서는 O(N)이 걸리지만 Set을 사용하게 된다면 set에서 원소검색은 O(1)의 시간복잡도를 가진다.

O(1)의 비결은?

해시테이블은 연관 배열(Associative array) 구조를 이용하여 키(Key)에 결과 값(value)을 저장하는 자료구조이다. 키와 값은 1:1로 연관되어 있고 키를 사용하여 값을 불러올 수 있다. 해당 키로부터 값을 도출하기 위해 해시함수가 사용된다. 

이는 Set에 활용되서 동일하게 해시함수를 거쳐서 동일하게 저장된다 대신 ! 

 Set에 원소를 저장할때는 기존의 리스트나 어레이처럼 앞, 뒤에 원소를 넣어주는 것이 아니라 해시함수를 거친 해시로 변경하여 저장소에 넣어준다는 것이다. 우리가 사용하는 set은 해시값으로 넣어주는게 아니라, 가변형으로 add나 remove로 값을 넣고 빼서 True와 False로 반환된다.

 Set에 존재하는지를 물어본다면 Set은 저장소의 앞 또는 뒤부터 검사를 시작하지 않는다. 특정원소를 해시함수를 통과 시킨 뒤 해당 해시가 저장소안에 있는지 없는지 검사만 하면 된다. 그렇기에 한번의 연산, O(1)만 일어나면 된다.