hash to array
Is my idea on hash tables correct?
The way I see them:
It’s basically an array. One place in the array holds the key, the next holds the data.
For example:
I’m trying to use a hash table with a data file. The key will be the line number, and the data will be the line.
So, I would add the first line, call it line 0 for obvious reasons, to the first spot in the array:
hashTable[0] = 0
Then, I would add the actual data, just call it “line1″, to the second spot:
hashTable[1]=line1
Then, second line to the third spot, line2 to the 4th spot
hashTable[2]=1
hashTable[3]=line2
Is this correct?
Pretty much. But you forgot the hash moment.
Lets create an array in size of 100 items.
Now we want to store thet data “Hello” with the key “foo”. Now we us a suting hash function converting the key to an integer (number) to use as the index in the array.
For simple example sake we just plus the ASCII number of the letters from “foo” together.
So the index i the hashtable will be 102+111+111 = 324.
So the position in the hashtable for the key “foo” is 324. But our hashtable was constructed with only 100 places. So we simply use the modules to limit the hashcode to max 100. 324 % 100 (size of hash table) = 24 so you put your data in the 24 place for the key “foo”.
But what happens if another keys hash becomes to a slot that is occupied? Whell, you rehash the key. Using a differens hash method OR just check if the place below is free and then as long as the hash table is not full eventually you will find a place. So you must the key aswell in the hash table struct.
When the hash table manages to get full you can make another one with the new desired size and one for one hash the old data into the new table.
|
|
Ruby Pocket Reference $7.99 Although Ruby is an easy language to learn, in the heat of action you may find that you can’t remember the correct syntax for a conditional or the name of a method. This handy pocket reference offers brief yet clear explanations of Ruby’s core components, from operators to reserved words to data structures to method syntax, highlighting those key features that you’ll likely use every day when codi… |