>However, in general w cannot be considered a constant: if all n keys are distinct, then w has to be at least log n
We can't ignore the log n, unless the number of distinct elements is small with respect to n. Since this wouldn't be known a priori, we can't make that assumption.
Also, note that if we know, a priori, that the number of distinct elements is small wrt N, we can simply use the hash set for O(N) without any of the problems he goes to outline in the article.