algorithm - Amortized performance of LinkedList vs HashMap -

algorithm - Amortized performance of LinkedList vs HashMap -

the amortised performance of hash tables said o(1) operations.

what amortized performance search operation on standard linkedlist implementation? o(n)?

i'm little confused on how computed, since in worst-case (assuming hash function collides), hash table pretty much equivalent linkedlist in terms of search operation (assuming standard bucket implementation).

i know in practise never happen unless hash function broken, , average performance constant time on series of operations since collisions rare. when calculating amortized worst-case performance, shouldn't consider worst-case sequence worst-case implementation?

there no such thing "amortized worst-case performance". amortized performance kind of "average" performance on long sequence of operations.

with hash table, hash table need resized after long sequence of inserts, take o(n) time. but, since happens every o(n) inserts, operation's cost spread out on inserts o(1) amortized time.

yes, hash table o(n) every operation in worst case of broken hash function. but, analyzing such hash table meaningless because won't case typical usage.

performance algorithm data-structures computer-science