Hashtable v.s. Dictionary
-
Here's link that explains more: http://en.wikipedia.org/wiki/Hash_table[^] Hashing transforms a key into the address of a slot to store the data in. There are a fixed number of slots. When multiple keys are mapped to the same slot, there are different ways of handling it, all of which take time. Type "hash table" into Google, and you'll get much more than I can explain here.
How about my question item 1? -------------------- I am confused what do you mean fixed size. I think from developer point of view, we can insert as much elements as possible into Hashtable, so no feel of limitation of fixed size. Any more descriptions or pseudo code please? -------------------- Fixed size means limited size? regards, George
-
How about my question item 1? -------------------- I am confused what do you mean fixed size. I think from developer point of view, we can insert as much elements as possible into Hashtable, so no feel of limitation of fixed size. Any more descriptions or pseudo code please? -------------------- Fixed size means limited size? regards, George
Look at the link I gave, type "hash table" into Google and look at some of those references, and see if they answer your questions. There's a lot of material on hash tables out there, with more complete explanations than I can give you here.
-
Look at the link I gave, type "hash table" into Google and look at some of those references, and see if they answer your questions. There's a lot of material on hash tables out there, with more complete explanations than I can give you here.
Thanks Alan, I read the link, clarified a lot of things. I often heard people talk about re-hash, does it mean the same thing of "Table resizing" in the link you mentioned? regards, George
-
Thanks Alan, I read the link, clarified a lot of things. I often heard people talk about re-hash, does it mean the same thing of "Table resizing" in the link you mentioned? regards, George
It might. I haven't heard that term in the context of hash tables.
-
It might. I haven't heard that term in the context of hash tables.
Thanks Alan, Your reply is clear. I want to check why do you think before Hashtable is fixed size? If the load factor is large enough (e.g. HashMap in Java is 75%), it will be resized to increase its size -- so not fixed. Could you clarify please? regards, George
-
Thanks Alan, Your reply is clear. I want to check why do you think before Hashtable is fixed size? If the load factor is large enough (e.g. HashMap in Java is 75%), it will be resized to increase its size -- so not fixed. Could you clarify please? regards, George
If you increase the size of the hash table, you also have to change the hashing function to produce keys for this larger size. When you do this, the elements you've already added to the hash table must go to different slots. So every element must be re-inserted in the new larger table. This process creates a new hash table and replaces the old one. The old one wasn't resized.
-
If you increase the size of the hash table, you also have to change the hashing function to produce keys for this larger size. When you do this, the elements you've already added to the hash table must go to different slots. So every element must be re-inserted in the new larger table. This process creates a new hash table and replaces the old one. The old one wasn't resized.
Thanks Alan, So, the root cause is hash function is dependent on table size? :-) regards, George
-
Thanks Alan, So, the root cause is hash function is dependent on table size? :-) regards, George
Yes.
-
Yes.
Thanks Alan! You mentioned before -- "When the hashtable has to grow regularly, it can increase the time for insertion to O(n) or higher, depending on how often it happens.". "It" means? :-) regards, George
-
Thanks Alan! You mentioned before -- "When the hashtable has to grow regularly, it can increase the time for insertion to O(n) or higher, depending on how often it happens.". "It" means? :-) regards, George
Growing regularly. Every time the hashtable "grows", all elements that have been inserted must be reinserted into the new hashtable. When a hashtable has n elements, it takes n operations to copy them, as opposed to a single operation to insert one element.
-
Growing regularly. Every time the hashtable "grows", all elements that have been inserted must be reinserted into the new hashtable. When a hashtable has n elements, it takes n operations to copy them, as opposed to a single operation to insert one element.
Thanks Alan! Question answered. You are so patience. :-) regards, George