Почему множества в Python работают быстрее списков при проверке наличия элемента?

Множества в Python работают быстрее списков при проверке наличия элемента, потому что в множестве проверка производится по хэшу элемента, который преобразуется в адрес элемента в памяти. ru.stackoverflow.com

Если у разных элементов одинаковый хэш, есть механизм разрешения коллизий. ru.stackoverflow.com В простейшем случае это список элементов с одинаковым хэшем, в котором дальше идёт поиск. ru.stackoverflow.com В целом при небольшом числе коллизий поиск во множестве имеет сложность О(1). ru.stackoverflow.com

В списке, чтобы проверить наличие элемента, нужно последовательно перебрать его элементы, пока не найдётся нужный. ru.stackoverflow.com Это занимает время, пропорциональное размеру списка, то есть имеет сложность О(n). ru.stackoverflow.com pyhub.ru