Hashtable vs. Array

Hey Guys,

I just learned about hashtables and how they work.
I've already read some comparisons of array(lists) vs. hashtables but I can't find a big advantage of using hashtables.

As far as I understood, I could also rush through a associative array with an index as number when I am using a hashtable Not able to express myself properly.
Can anyone of you explain me the difference/advantages? Would be greatly appreciated

The advantage of a hash table is that random access, insertion and deletion can be performed in O(1) (or at least with a strong bias towards it) while an array has a O(log N) complexity for these tasks. However, a array is good if you access known indexes all the time and don't care about insertion and deletion, the complexity for this is guaranteed O(1), best case, average case and worst case. Plus, arrays maintain a order and can be sorted, but you don't need this all the time.
A common use case for hash tables are dictionaries of any kind (for example just as a lookup table) and a data store where you don't need to maintain an order.

I was hoping for your answer, thanks.

The only thing I don't quite get are the expressions O(1) and O(log N), the rest is pretty clear.

Wenn du willst, schreib es gerne in Deutsch, dann geht es sicher noch besser.

That O() is the so called Landau Symbol, its a way to express the performance complexity of an algorithm. For example, the complexity to search for something in an array is O(log N) where N is the number of elements in the array. This means that the complexity grows logarithmic with the number of elements in the array. O(1) means that the complexity is constant no matter what.
When talking about data structures and algorithms, an easy way to understand the difference is to use the landau symbol and based on this choose the appropriate algorithm and data structure to work with.

A few examples:
Accessing something randomly from an hash table is O(1) in the average case because its just an access to a known index determined by the computed hash. A random access into an array is O(log N) in the average case because you first have to crawl the array to find the object, though the best case is O(1) if the searched element is at the beginning of your search and the worst case is O(N) if the element at the end of the list (because then you first have to search through every element in the array). However, if you access a known position in an array through its index, it suddenly becomes also O(1) because then you don't have to search for the element first.
Same with deletion and insertion, a hash table needs O(1) for this in the average case (read; No overflow buckets due to hash collisions, but still then the bias is strongly towards O(1) because the overflow buckets are usually very limited). A array on the other hand needs also for this O(log N) average because again, you have to rearrange the array after the deletion/before the insertion to avoid either gaps or overwritting an existing element. But yeah, depending on the position this can also become O(1) or O(N).

Wow. Thanks a lot for this great explanation, it really helped to understand the differences and the excursion to understand Landau was great too!

@JustSid: How is the complexity of O(log N) on average for the array computed?

@Superku: You got me there, the average case for a linear search is expected to be O(N) and not O(log N). (Sorry, I was thinking of a binary search while writing, which again would also be wrong because it has O(log N) in the worst case instead of O(N)). Sorry!

http://doc.qt.nokia.com/latest/containers.html#algorithmic-complexity

Ok, I did not know how the average case is calculated but I've assumed it would be O(N).

Btw, the Gamestudio Wiki has also a list of data structures and their complexity together with how they work and what their advantages/disadvantages are: http://www.opserver.de/wiki/index.php/Data_Structures (although its way from being complete, but feel free to add more stuff)

http://www.daniweb.com/software-development/computer-science/threads/44665