Hash Table: Should I increase the element count on collisions?

Posted by Nazgulled on Stack Overflow See other posts from Stack Overflow or by Nazgulled
Published on 2010-04-18T14:31:48Z Indexed on 2010/04/18 14:33 UTC
Read the original article Hit count: 315

Filed under:

hashtable

|

hash-collision

|

load-factor

Hi,

Right now my hash tables count the number of every element inserted into the hash table. I use this count, with the total hash table size, to calculate the load factor and when it reaches like 70%, I rehash it.

I was thinking that maybe I should only count the inserted elements with fills an empty slot instead of all of them. Cause the collision method I'm using is separate chaining. The factor load keeps increasing but if there can be a few collisions leaving lots of empty slots on the hash table.

You are probably thinking that if I have that many collisions, maybe I'm not using the best hashing method. But that's not the point, I'm using one of the know hashing algorithms out there, I tested 3 of them on my sample data and selected the one who produced less collisions.

My question still remains. Should I keep counting every element inserted, or just the ones that fill an empty slot in the Hash Table?

© Stack Overflow or respective owner

Related posts about hashtable

Copy hashtable to another hashtable using c++

as seen on Stack Overflow - Search for 'Stack Overflow'
I am starting with c++ and need to know, what should be the approach to copy one hashtable to another hashtable in C++? We can easily do this in java using: HashMap copyOfOriginal=new HashMap(original); But what about C++? How should I go about it? UPDATE Well, I am doing it at a very basic level… >>> More
Search Complexity of a Hashtable within a Hashtable?

as seen on Stack Overflow - Search for 'Stack Overflow'
Say we have a hashtable of size m, and at each bucket we store a hashtable of size p. What would the worst case/average case search complexity be? I am inclined to say that since computing a hash function is still atomic, the only worst case scenario is if the value is at the end of the linked list… >>> More
How to fix the size of the Hashtable and find the whether it has fix size or not?

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi All, I am trying to fix the size of the Hashtable with following code. Hashtable hashtable = new Hashtable(2); //Add elements in the Hashtable hashtable.Add("A", "Vijendra"); hashtable.Add("B", "Singh"); hashtable.Add("C", "Shakya"); hashtable.Add("D"… >>> More
Hi, I have a C hashing routine which is behaving strangely?

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, In this hashing routine: 1.) I am able to add strings. 2.) I am able to view my added strings. 3.) When i try to add a duplicate string, it throws me an error saying already present. 4.) But, when i try to delete the same string which is already present in hash table, then the lookup_routine… >>> More
Hashtable comparator problem

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi guys i've never written a comparator b4 and im having a real problem. I've created a hashtable. Hashtable <String, Objects> ht; Could someone show how you'd write a comparator for a Hashtable? the examples i've seen overide equals and everything but i simply dont have a clue. The code… >>> More

Related posts about hash-collision

Find a Hash Collision, Win $100

as seen on SQL Blog - Search for 'SQL Blog'
Margarity Kerns recently published a very nice article at SQL Server Central on using hash functions to detect changes in rows during the data warehouse load ETL process. On the discussion page for the article I noticed a lot of the same old arguments against using hash functions to detect change… >>> More
Are hash collisions with different file sizes just as likely as same file size?

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm hashing a large number of files, and to avoid hash collisions, I'm also storing a file's original size - that way, even if there's a hash collision, it's extremely unlikely that the file sizes will also be identical. Is this sound (a hash collision is equally likely to be of any size), or do I… >>> More
Are has collisions with different file sizes just as likely as same file size?

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm hashing a large number of files, and to avoid hash collisions, I'm also storing a file's original size - that way, even if there's a hash collision, it's extrememly unlikely that the file sizes will also be identical. Is this sound (a hash collision is equally likely to be of any size), or do… >>> More
Collision Attacks, Message Digests and a Possible solution

as seen on Stack Overflow - Search for 'Stack Overflow'
I've been doing some preliminary research in the area of message digests. Specifically collision attacks of cryptographic hash functions such as MD5 and SHA-1, such as the Postscript example and X.509 certificate duplicate. From what I can tell in the case of the postscript attack, specific data… >>> More
Moving from Linear Probing to Quadratic Probing (hash collisons)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, My current implementation of an Hash Table is using Linear Probing and now I want to move to Quadratic Probing (and later to chaining and maybe double hashing too). I've read a few articles, tutorials, wikipedia, etc... But I still don't know exactly what I should do. Linear Probing, basically… >>> More