Kirupa.com - Hashtables vs. Arrays

#1

by kirupa | 10 December 2011

Have questions? Discuss this HTML5 / JavaScript tutorial with others on the forums.

This is a companion discussion topic for the original entry at http://www.kirupa.com/html5/hashtables_vs_arrays.htm
#2

Hi, I think there may be some question here:
Inserting (array) O(1) - Constant

Can you explain this please ?

#3

@kirupa doesn’t describe what he means by ‘inserting’ for the array case, so I wouldn’t worry about it too much. If you look at the table here:

…you can see that he probably means appending to the end of a dynamic array takes O(1) on average. A short explanation is that the length of the array is known, so it’s easy to calculate address of where the newly appended element goes. Memory-wise, either there’s going to be space available immediately after the end of the array, in which case the operation takes constant time, or there’s not space, in which case some sort of reallocation occurs and could take a non-constant amount of time.

1 Like
#4

Basically , if you are searching for a particular item in a long data, hashtable becomes a clear winner, which is a major part of any application that handles data