title: Implementing a hash table
body: <p>I started reading about implementing various data structures a few days back, and got around to hash tables and got stuck on a specific point.</p>
  
  <p>My understanding of how a hash table is implemented:
  A key K is passed to a hash function H which returns a hashed version of K, HK. HK should probably be at least a uint32_t to account for collisions, we have an array of size X, the item is stored at the index HK of this array.. but, wouldn't this require a pre-allocated array of length uint32_t atleast (or whatever the return value of H is)? assuming that we don't store the data itself within that array, and instead store a ptr to the data, then we'd need an array of ptr_t of length uint32_t.. this seems quite wasteful, on 64bit that would mean memory usage of:
  2^32 * 8 = 34359738368 bytes or ~32GB just for the array of ptrs to the data, which is obviously not how its actually implemented in real life..</p>
  
  <p>So what am I missing?</p>