are deleted entries counted in the load factor of a hash table using open addressing

Posted by Dr. Monkey on Stack Overflow See other posts from Stack Overflow or by Dr. Monkey
Published on 2010-06-08T09:13:33Z Indexed on 2010/06/08 19:22 UTC
Read the original article Hit count: 329

Filed under:

hashtable

|

load-factor

When calculating the load factor of a hashtable with an open-addressing array implementation I am using:

numberOfKeysInArray/sizeOfArray

however it occurred to me that since deleted entries must be marked as such (to distinguish them from empty spaces), it might make sense to include these in the number of keys.

My thinking is that as far as estimating the average number of probes to find an entry, deleted entries should count towards the load factor, but as far as inserting a new key they should not.

Which is the proper calculation: including deleted keys or not?

© 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 load-factor

are deleted entries counted in the load factor of a hash table using open addressing

as seen on Stack Overflow - Search for 'Stack Overflow'
When calculating the load factor of a hashtable with an open-addressing array implementation I am using: numberOfKeysInArray/sizeOfArray however it occurred to me that since deleted entries must be marked as such (to distinguish them from empty spaces), it might make sense to include these in… >>> More
Testing the load factor in my lab

as seen on Server Fault - Search for 'Server Fault'
I am a system admin in a lab, I have ~90 computers in the lab and I want to check the load factor on them.. meaning, to check how many people are working on the computers hourly.. To see if I need to buy more computers or not. I am looking for a way to build a script to check if a computer is logged… >>> More
Testing the load factor in my lab [closed]

as seen on Stack Overflow - Search for 'Stack Overflow'
I am a system admin in a lab, I have ~90 computers in the lab and I want to check the load factor on them.. meaning, to check how many people are working on the computers hourly.. To see if I need to buy more computers or not. I am looking for a way to build a script to check if a computer is logged… >>> More
Does it make sense to resize an Hash Table down? And When?

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, My Hash Table implementation has a function to resize the table when the load reaches about 70%. My Hash Table is implemented with separate chaining for collisions. Does it make sense that I should resize the hash table down at any point or should I just leave it like it is? Otherwise, if I… >>> More
Hash Table: Should I increase the element count on collisions?

as seen on Stack Overflow - Search for 'Stack Overflow'
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… >>> More