Code for Game Developers - Hash Tables

We implement a hash function that we use to assign indexes into a hash table. This lets us look up our data very quickly.

I forgot to mention in the video but if we let n be the number of items in the hash table and m be the length of the string we are hashing, the algorithmic complexity of a hash table is O(m). It does not depend on n at all, and since m is generally very small, people usually say that hash tables are O(1). That makes hash tables are your best friend.

[MaximumRadical]

Heyy I like hash tables! I see the limitations that make them unsuitable for many cases, but I can already imagine a million different ways this method of data storage can improve run time performance in places where I would have naively used a regular array.

[AsbjornGrandt]

Hash the name and store it with the name, but only apply the hash % hash_table_length when accessing it. Then a rehashing of the table will become slightly cheaper.
In Java, instead of multiplying the char with a large value, the String hash is created by multiplying the previous iteration's hash with 31 before adding the char value.

IIRC in C it would be faster to do
for()
h = (h<<<5)-h+s[i];

simply because a bit shift might be faster than a multiplication

[NeilRoy]

I wonder if you could resize and then resort the table. Certainly in may be a more involved operation, but if you simple doubled the size of the table, than you wouldn't have to do it too often. Much like vector's operate. I made some stack functions for C that operate like vectors that resized when needed to double the current size. I wonder if resorting a hash table would be a terribly expensive operation?

[scshout]

Hashtables are very useful for GUI ids, but I been wondering... if we are doing some kind of gui lib, why not to use static uint which represents id and everytime we call a new widget or widgets' window we increment it. So there is no way to have a collision.

[starshkr]

Why would you use this over an array/vector, assuming you know the indexes of the objects you wanna use?

[derptivo]

Instead of adding an arbitrary large number, p, why not just add the number of spaces, k, to the function before doing mod k?