filter list fast

[Diez B. Roggisch]

> Both of these techniques are O(n^2).  You can reduce it to O(n log n)
> by using sets:
> 
>>>> set2 = set(list2)
>>>> [x for x in list1 if x not in set2]
> 
> Checking to see if an item is in a set is much more efficient than a
> list.

Is the set-lookup reliably O(log n)? I was under the impression that it is
hash-based, and this should be O(1) usually, but couldbve O(n) worst-case
(hash the same for _all_ entries).

Regards,

Diez