Easily Learn And Understand Hashtables

[X-Death]

This video helped me understand how hashtables work. I figured I would share with everyone else.

Here:
http://www.youtube.com/watch?v=h2d9b_nEzoA

 

[IcemanBo]

Should not this be more in tutorial section?

 

[edo494]

"pros and cons" I dont know if hashtable has any real pros, that would outweigth cons. Hashtable's speed is so bad that you are better off with dynamically allocated array

Also she says bullshit even on the start: "Because array store data contiguously, you must specify the array's size when you declare the array". Thats true, but "there is no guarantee that no memory that is adjestant(this is really spelled wrongly) to your array will be available to use later, so arrays can not easily grow". This would be true, if we were living in like 80's maybe

For the speed of insert/delete, here is a nice table from wikipedia:

Average Worst case
Space O(n) O(n)
Search O(1) O(n)
Insert O(1) O(n)
Delete O(1) O(n)

edit: It is nice to know how hash tables can be implemented, and how they work, but they are not that great in reality, just like Linked Lists

 

[GhostWolf]

Actually a good implementation is close to O(1), and everything she says is right. You are not guaranteed anything.

Even if you get a bad hashing function, do note that O(n) is the same notation-wise as O(nk+c), or in other words any linear function. So yes, if you get a k below 1, it's still O(n) for the pure mathematics, but it's certainly not for your practical code.

Either way, hash tables are great, linked lists are great, arrays are great, and every other data structure is great, you just need to use them where it is appropriate. You saying that one should use a vector instead of a hash table makes no sense, how is a vector, which is a random access array-like structure, even remotely the same as a key-value mapping structure?

I don't understand the point of this thread though.

 

[Chaosy]

I didn't found it rather hard to make this translate into wc3's hashtable. Firstly they only use 1 key while wc3 use 2. Also even if you somehow understands how a hashtable work perfectly you still need to head to another tutorial to learn how to practically use them. In most cases we use GetHandleId(someunit) as a key but that's something you wont know by looking at that video.

edit:

but they are not that great in reality, just like Linked Lists

are you high or something? how can you code without lists? I can not even imagine the pain.. "ok guys we need an array with unlimited size to store our enemies, even though we maybe wont use a lot of units until the game has been going on for 40 minutes" very efficient kappa.

edit2: why don't they mention normal lists btw? in c# lists seems to be a mix of linked lists and arrays.

 

[GhostWolf]

Because the notion of a "list" in the standard libraries of languages can be implemented in any way they so desire, as long as it acts like a list.

 

[edo494]

I didn't found it rather hard to make this translate into wc3's hashtable. Firstly they only use 1 key while wc3 use 2. Also even if you somehow understands how a hashtable work perfectly you still need to head to another tutorial to learn how to practically use them. In most cases we use GetHandleId(someunit) as a key but that's something you wont know by looking at that video.

edit:

are you high or something? how can you code without lists? I can not even imagine the pain.. "ok guys we need an array with unlimited size to store our enemies, even though we maybe wont use a lot of units until the game has been going on for 40 minutes" very efficient kappa.

edit2: why don't they mention normal lists btw? in c# lists seems to be a mix of linked lists and arrays.

if you store the units inside array with indexes mapped to units(UnitIndexer anyone?) you still get better performance than linked list

 

[Chaosy]

I was speaking of coding in general, not wc3 exactly. In wc3 that would work fine since you more or less got a unlimited amount of spots in your array. (not really, but close enough) Meanwhile in c# for example you need to set the size of the array. Which means you need to take a guess on the array size. While the list is perfect all the time.

 

[edo494]

hmm..why did I say dynamically allocated array hmm...

Biggest drawback of List the fact that the nodes are all over the ram, which means that when you want to get to another node, you have to access the RAM and ask for the address, whereas in contiguous block, you dont need to, because you know the next element is right next to yours, which means you can place the addresses of objects into cache, and you can iterate over the array with no RAM access required. I had one post ready, but hive backup was against me

Basically, List(Linked one) is outperforming dynamic array with decently big size AND decently big structures(I think it was something like after 10,000 elements, each being roughly 500 - 1,000 bytes)

"ok guys we need an array with unlimited size to store our enemies, even though we maybe wont use a lot of units until the game has been going on for 40 minutes"

this is perfect example from wc3

are you high or something? how can you code without lists?

I dont know about your language's standard, but the language I use and write in(C++) has something nice called vector

 

[Zeatherann]

If we talk about Warcraft III's JASS language then there are two containers; arrays and hashtables. We can manipulate these two structures however we want (such as to turn the array into a linked list). Arrays have been shown to have faster read-write times than hashtables (I've heard hashtables are 2.5x times slower than arrays before). The reason we still use hashtables is because it creates less global variables, and/or that the index range isn't limited to 0-8191, but from -2,147,483,648-2,147,483,647. This not only allows for more elements to be placed into it, but to use larger index numbers (such as handle and object ids, as well as coordinates. The lower number of globals is only beneficial for make development or if the map has enough globals to make the global hash search slower than the hashtable access (assuming the use of the hashtable doesn't require the same global hash search because they are stored in the hashtable instead of in globals). The development part only matters if one gets tired of searching through metric tons of globals in the globals block, or variable editor.However, in the real programming world there are many containers that (usually) all revolve around the use of array (usually dynamically allocated). They all have their uses depending on the situation and the way they are used. Lists (which are linked) are great for their constant insert and remove methods; and fail when it comes to random access. Maps (associative containers) are great as you can map any orderable type as the access key with a log base 2(N) access time. However, they have constant speed insert and remove methods. Vectors (arrays/dynamic arrays) are amazing at their constant access methods, but require a continuous block of memory to be effective, and have to reallocated when they grow larger than their allocated size, which is a slow operation. Hashtables (containers accessed based on a hashing function), with a good hashing algorithm, can yield better access times than an associative container and can be better than associative containers for random access. Rehashing can be a problem though as, like array reallocation, can be a heavy and slow operation.I hope I've been fairly accurate in my post, and that it was useful and/or informational to someone.