O(1) = constant time = independent of the number of items in the hash table
Take a look at http://en.wikipedia.org/wiki/Hash_table : In a well-dimensioned hash table, the average cost (number of instructions<http://en.wikipedia.org/wiki/Instruction_(computer_science)>) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at constant average (indeed, amortized<http://en.wikipedia.org/wiki/Amortized_analysis>[1]<http://en.wikipedia.org/wiki/Hash_table#cite_note-leiser-0>) cost per operation.[2]<http://en.wikipedia.org/wiki/Hash_table#cite_note-knuth-1>[3]<http://en.wikipedia.org/wiki/Hash_table#cite_note-cormen-2> Gordon Smith Adobe Flex SDK Team From: [email protected] [mailto:[email protected]] On Behalf Of d9_tech Sent: Wednesday, October 21, 2009 11:46 AM To: [email protected] Subject: [flexcoders] Re: Performance of associative array or dictionary lookup What's the big O of a lookup in the hash table? If I were to use an array and just iterate sequentially through the array looking for an item it would be O(n) in the worst case scenario (if what I'm looking for happens to be in the last position in the array). What's the worst case scenario for the hash table? --- In [email protected]<mailto:flexcoders%40yahoogroups.com>, Gordon Smith <gosm...@...> wrote: > > No, they aren't sorted. They use a storage technique called a hash table. > > Gordon Smith > Adobe Flex SDK Team > > From: [email protected]<mailto:flexcoders%40yahoogroups.com> > [mailto:[email protected]<mailto:flexcoders%40yahoogroups.com>] On > Behalf Of d9_tech > Sent: Thursday, October 15, 2009 2:50 PM > To: [email protected]<mailto:flexcoders%40yahoogroups.com> > Subject: [flexcoders] Performance of associative array or dictionary lookup > > > > I'm curious to know what the algorithm is behind an associative array or > dictionary look up. I'm assuming that associative arrays and dictionaries are > sorted when they are created and then something like a binary search is used > to do the look up. Can anyone confirm that this is true or offer additional > information? > > Thanks, > > christian >
