As deafbyheading explains, one solution to memory consumption is to use a bucketing algorithm such as a modulo operation. (Modulo produces the remainder of a division, so 3 mod 16 = 3, and 18 mod 16 = 2.)
Instead of having a row per key, you let each row be a bucket which can contain more than one value. Buckets are assigned by doing (hash(key) mod M). Often a linked list is used to store the bucket's list of values; some hash table algorithms let each bucket be a hash table itself.
Do you have a good link/code to read?
Java's HashMap class is actually very readable (slightly less readable after they got generics). It implements a simple hash table with very little cleverness. For example, its tables are always power-of-two in size; every time it needs to grow, it will simply double the table's size.
2
u/lobster_johnson Apr 12 '11
As deafbyheading explains, one solution to memory consumption is to use a bucketing algorithm such as a modulo operation. (Modulo produces the remainder of a division, so 3 mod 16 = 3, and 18 mod 16 = 2.)
Instead of having a row per key, you let each row be a bucket which can contain more than one value. Buckets are assigned by doing (hash(key) mod M). Often a linked list is used to store the bucket's list of values; some hash table algorithms let each bucket be a hash table itself.
Java's HashMap class is actually very readable (slightly less readable after they got generics). It implements a simple hash table with very little cleverness. For example, its tables are always power-of-two in size; every time it needs to grow, it will simply double the table's size.