[whatwg] DOMTokenList is unordered but yet requires sorting
Maciej Stachowiak
mjs at apple.com
Tue Jun 16 12:37:57 PDT 2009
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
More information about the whatwg
mailing list