1 registered members (TedMar),
1,420
guests, and 3
spiders. |
Key:
Admin,
Global Mod,
Mod
|
|
|
Hashtable vs. Array
#382081
09/04/11 11:30
09/04/11 11:30
|
Joined: Jul 2009
Posts: 1,198 Berlin, Germany
Liamissimo
OP
Serious User
|
OP
Serious User
Joined: Jul 2009
Posts: 1,198
Berlin, Germany
|
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
Last edited by Liamissimo; 09/04/11 11:32.
"Ich weiss nicht genau, was Sie vorhaben, aber Sie können keine Triggerzonen durch Ihr Level kullern lassen." -JCL, 2011
|
|
|
Re: Hashtable vs. Array
[Re: Liamissimo]
#382085
09/04/11 12:40
09/04/11 12:40
|
Joined: Apr 2007
Posts: 3,751 Canada
WretchedSid
Expert
|
Expert
Joined: Apr 2007
Posts: 3,751
Canada
|
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.
Shitlord by trade and passion. Graphics programmer at Laminar Research. I write blog posts at feresignum.com
|
|
|
Re: Hashtable vs. Array
[Re: WretchedSid]
#382086
09/04/11 13:29
09/04/11 13:29
|
Joined: Jul 2009
Posts: 1,198 Berlin, Germany
Liamissimo
OP
Serious User
|
OP
Serious User
Joined: Jul 2009
Posts: 1,198
Berlin, Germany
|
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.
"Ich weiss nicht genau, was Sie vorhaben, aber Sie können keine Triggerzonen durch Ihr Level kullern lassen." -JCL, 2011
|
|
|
Re: Hashtable vs. Array
[Re: Liamissimo]
#382089
09/04/11 13:47
09/04/11 13:47
|
Joined: Apr 2007
Posts: 3,751 Canada
WretchedSid
Expert
|
Expert
Joined: Apr 2007
Posts: 3,751
Canada
|
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).
Shitlord by trade and passion. Graphics programmer at Laminar Research. I write blog posts at feresignum.com
|
|
|
Re: Hashtable vs. Array
[Re: WretchedSid]
#382090
09/04/11 13:53
09/04/11 13:53
|
Joined: Jul 2009
Posts: 1,198 Berlin, Germany
Liamissimo
OP
Serious User
|
OP
Serious User
Joined: Jul 2009
Posts: 1,198
Berlin, Germany
|
Wow. Thanks a lot for this great explanation, it really helped to understand the differences and the excursion to understand Landau was great too!
"Ich weiss nicht genau, was Sie vorhaben, aber Sie können keine Triggerzonen durch Ihr Level kullern lassen." -JCL, 2011
|
|
|
Re: Hashtable vs. Array
[Re: Superku]
#382094
09/04/11 14:12
09/04/11 14:12
|
Joined: Apr 2007
Posts: 3,751 Canada
WretchedSid
Expert
|
Expert
Joined: Apr 2007
Posts: 3,751
Canada
|
@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!
Shitlord by trade and passion. Graphics programmer at Laminar Research. I write blog posts at feresignum.com
|
|
|
Re: Hashtable vs. Array
[Re: Superku]
#382098
09/04/11 14:31
09/04/11 14:31
|
Joined: Apr 2007
Posts: 3,751 Canada
WretchedSid
Expert
|
Expert
Joined: Apr 2007
Posts: 3,751
Canada
|
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)
Shitlord by trade and passion. Graphics programmer at Laminar Research. I write blog posts at feresignum.com
|
|
|
|