id for a hashtable
hey all. I'm going to add an object to a hash table in c++ but i prefer for this object to have an automated id, so i did this in the constructor of the class:id=(int)(this);
Will this be a good thing to do in order to get an automated id?
Will this be a good thing to do in order to get an automated id?
First of all, are you using MAP? Where do you want to store this object, as Key or Value?
Not sure if the standard guarantees that int has enough bits to store a pointer to an object. If not, then you are not guaranteed uniqueness.
Well surely you can't achieve uniqueness by using the memory address as a key... Reserving enough memory that can uniquely identify any cell in your memory will take exactly as much memory as your computer has! :))
1. Create an object, id = address.
2. Copy object and remove the original (like putting in a collection and returning from the function). It's possible that the next free address in the heap is the same one that was issued previously for your object.
3. Create another object, id = address. This object may have the same id as the previous one. Your IDs wouldn't be unique.
2. Copy object and remove the original (like putting in a collection and returning from the function). It's possible that the next free address in the heap is the same one that was issued previously for your object.
3. Create another object, id = address. This object may have the same id as the previous one. Your IDs wouldn't be unique.
This is a classic "hashclash" problem. Hash tables make inserting/retrieving very easy, but since there is no free lunch, it comes with the unique key generation problem. You WILL have to come up with key generation algorithm and then back it up with a rehashing algorithm.
It really depends on how busy the system is. If it is really busy then you will have frequent hash clashes and in that case, you will need rehashing, so preferably the hash algorithm itself needs to be an efficient one. If it is not that busy system (less than 10% of the table size is being used at any given time), then less primary hash clashes and even if the primary algorithm is not very efficient, rehashing can be done once or twice and you will be able to find next empty slot.
It really depends on how busy the system is. If it is really busy then you will have frequent hash clashes and in that case, you will need rehashing, so preferably the hash algorithm itself needs to be an efficient one. If it is not that busy system (less than 10% of the table size is being used at any given time), then less primary hash clashes and even if the primary algorithm is not very efficient, rehashing can be done once or twice and you will be able to find next empty slot.
Topic archived. No new replies allowed.