[whatwg] DOMTokenList is unordered but yet requires sorting

[Maciej Stachowiak]

On Jun 15, 2009, at 4:19 PM, Kristof Zelechovski wrote:

> The complexity of using a set implemented as hash table is quadratic  
> in the
> number of elements because of hash collisions.

Removing duplicates from a list of length N using an auxiliary set is  
average-case O(N) because insertion and membership testing in a hash- 
implemented set is amortized average-case O(1). With a good hash  
function, the worst case does not usually need to be considered,  
because it is exceedingly unlikely to occur for a large data set by  
chance, and cannot feasibly be constructed by an attacker.

Regards,
Maciej