HashTable - Possiblity of Duplicate Hash Values

Yes you will get multiple hash values that re-occur for different strings.

If you are building your own hash table. you may will to look at howto implement skip lists. Or some similar method to overcome this issue. This efftivly lets you have duplicate keys. Which a small performance hit where duplicate keys occurs. If you get a lot of the same duplicate key you then either expend the number of bits in the key and alter how the keys are generated and rebuild the hash table.

This can work really well for a hash implementation that does not know how many keys it is likly to have in the system at design time.

But (and especially using something like barcodes), it may be to your advantage overall to be able to identify duplicates, because that lets you know that one of them is potentially wrong or has changed. The hashtable will throw a System.Argument exception if you try to add a duplicate key, which you can handle and investigate.

The methods used to solve the problem of collision is called collision resolution. The two most popular method of resolving collision are,
- Separate chaining
- Open addressing

Maybe you should try to implement one of these methods instead of trying to avoid collisions.

Let me clarify . . .

The bar codes that go into the HashTable will be unique.  There will be 1 million unique bar codes / unique keys inserted into the hash table.  Knowing this, can the hash value created for each bar code ever be duplicated?

Then you very little to worry about. This is pretty easy to test:

Dim ht As New Hashtable
For i = 1000000 To 2000000
ht.Add(i.GetHashCode, i)
Next
MsgBox(ht.Count)

'Generate a unique hash code for a million 7 digit integers. At 20 digits, you will get an even more diverse hash range

Busac --

you may or may not be correct. Some implementation will not handle duplicate keys. Some however will. Its impossible to tell unless you see the documentation for the hash table being used.

I had the .net base class library one in mind.

Calling Integer.GetHashCode() just returns the same integer so obviously you're never going to see a collision. I think that the OP will work with strings though.

But as I said, even if the collision occurs, the HashTable class will still correctly handle it. (I am assuming that OP is using the HasTable or Dictionary class from .net BCL.)

Ahh, yeah, forgot to .ToString. Makes no difference though, this also produces no duplicates:

Dim ht As New Hashtable
For i As Integer = 0 To 2000000
Dim s As String = i.ToString
ht.Add(s.GetHashCode, s)
Next

Hash insertion  consists of 2 parts

(1) Creation of a hash address for a record key

(2) Insertion of record into table using a collision resolution algorithm ie linear hash open addressing etc.

The very essence of hashing is the collision resolution, I suggest you read a good article on the subject
eg  http://www.pctechtalk.com/forums/community-news/12557-introduction-hashing.html
(the Wiki pages on this are not great imo btw). Hashing is fundamental and commonly used in many areas of computer science, reading up about it is worth it.

If your canned routines are not  implementing collision resolution of some then they are not hash routines.

typo  "...resolution of some kind then they.."

If your bar codes are 20 digits, there are 10^20 possible inputs. If your hash value is a simple 4 byte integer, there are only about 4*10^9 possible hash values.
Hence, if you'd really use up *all* possible input values, each hash value would be produced by about 2.5*10^10 (!) input values on average.
Of course, if you have only 1million random entries and a good hash function (with a really good hash function, the input need not even be random) there should be plenty of room for avoiding duplicates.
And yet beware - the so-called "Birthday paradox" may strike: if we have about sqrt(N) independant random values between 1 and N, inclusive, then the probability of no collision occuring is approximately 0.5.
With 4*10^9 possible hash values this would correspond to only 65,000 inputs.
Hecne with 1,000,000 inputs collisions are virtually unavoidable.

If the hash values are bigger, say 128 bit numbers as in MD5 hash, then the probability of collisions occuring is of course much lower: The birthday paradox would strike at about 1.8*10^44 inputs - with 1,000,000 inputs you can be relatively confident that no collisions occur. (In fact, 2^128 is much more than 2^20, so the re's no reason to use hashes at all).
However, if you want to use the hash (or part of it) as an address e.g. to a memory based array, then you'll necessarily squeeze the hash values into some useable size for addresses and we're back at the 32bit limit discussed above.

I have used hashtables for many very large sets of data and never had this problem.  As I understand it, the key value is hashed and this hash maps to a bucket, the bucket still contains the original keys and their corresponding object values, so if two or more keys map to the same bucket, it is not a problem, as the bucket is then searched sequentially until the correct entry is found.  Since the buckets should be guaranteed to be fairly small by a good hash function, the performance of the hashtable remains at virtually constant time.

Several of you have suggested problems with canned routines or implementing my own hash function.

I plan on using the Hashtable Class in the System.Collections Namespace in the Microsoft .Net Framework.

Will the Hastable Class in the .Net Framework handle collision resolution?

As I already said twice :D, yes it will. You don't have to worry about it.

Yes it will handle duplicate keys.

What some of the people here seem to fail to realize. Is that if you have a 128 bit value and implement a hash to reduce this size into smaller bits. You will always have collisions. there is no way around this. But there is a way to deal with it in a more efficent manner.

What some of the people here seem to fail to realize. Is that if you have a 128 bit value and implement a hash to reduce this size into smaller bits. You will always have collisions. there is no way around this. But there is a way to deal with it in a more efficent manner.

What you seem to fail to realize is that the author of this post asked a specific question regarding the .NET hastable object. He is not trying to research how to create a has-table scheme, skip list, collision resolution function, or anything of the sort. You are again using the term 'if you are going to implement a hash', which of course the author is not, he is using the stock object and the hash functions written by Microsoft for their base types.

If you are going to be critical of the answers given by other experts, at least address why it does not satisfy the problem that the author wishes to avoid.

Sorry if i assume it was an general hash table algorithms as it was post in Programming Algorithms. Therefore i was not being specific about certain framework implementations. I was also not making any assumtions that barcodes only containe numbers. Some support u to around 120 - 140 different characters.

ladarlin:

I did point out that it avioded the problem. You cut that bit from your trolling quote. I was only pointing out that you will always have collisions in a hash table. som others (including you) were pointing out that you dont. So if you could show me how to compact 7 * 20 bits into something smaller than a 32bit value without having duplicates I would really be intrested.

I have something like the problem here. We use bar code to process returned mail. We use different sections in the bar code to store different record id's eg job / batch / letter numbers. The barcode's produced are not sequentally generated. There is know way to test these at design time for all combinations.

So testing these things with a loop from 0 - 2m really doesnt actually test for anything usefull in a situation like this.
Testing with a loop from 0 - 1000m also doesnt even cover 1% of what may be required in the live enviroment.

We know that the C# hashtable implementation will deal with duplicate entires. But i think the real quesiton that should have been asked here. Is how well will it deal with many multiple duplicates keys returned from the data?
For anything at best guess up to approx 50k or so keys.

I did point out that it avioded the problem. You cut that bit from your trolling quote...

Trolling? I believe that I have been in this discussion from the start, and It appears that others as well as the author agreed that further consideration of the issues that you insist are relevant are not, in this case.

So if you could show me how to compact 7 * 20 bits into something smaller than a 32bit value without having duplicates I would really be intrested.

Again, not relevant, and, happily, we dont need to solve that particular problem, since Microsoft had the forethough to return a 32bit signed integer from their string.getHashCode function.

But i think the real quesiton that should have been asked here. Is how well will it deal with many multiple duplicates keys returned from the data?

Ahhh, I see, I didnt realize that the author failed to asked the correct question. What he really wanted to know, then, is how the hastable object's underlying collision resolution algorithm is written?

For anything at best guess up to approx 50k or so keys

Based on what? Whos best guess? So, with 4,294,967,295 possible unique values for the hash itself, are you asserting that 1 million unique strings (the authors number, mind you) hashed could result in 50,000 duplicates? That is 5%. Or, 1 in every 20 unique strings passed to that function will return a duplicate hashcode... I dont believe that.

You do know as the data that you are generating the key from gets longer you get more duplicates.

So for a 32bit int.

Assume a 7 bit char set (large barcode)

The longest barcode you can have which can fit its key into 32bit is 4 chars.
So for an 20 char barcode you require a hash key length of up to 140 bits for no duplicates ot occur. This is of course if your hash function is "perfect". So the difference between 32bit and 140bit number is somewhat easy to generate 50k duplicates ;)
In fact 50k is less that 0.0001% of the key size.

You are not working off 1 million unique strings. You are working off a 32bit key generated from a 140bit value. Which data so long for a key its possible to really hit the bad side of things and generate a lot of duplicate keys.

If you dont belive me you should go and try it :)

You do know as the data that you are generating the key from gets longer you get more duplicates.

Actually no, I dont know that. Since string.getHashCode works on both the characters value and its position within the string, performing a simple mathematical function on an initial value, it follows that a longer string will result in more iterations of modification to the value that a shorter string.

Given that it *is* a fixed seed and that the functions performed on the initial value are hard coded (and thus reliable) , you can positively say that string values whos characters 'add up' to identical values will exist, but that is all that you can 'guess' at.

----

See System.String.GetHashCode() below for further study. I think I'll move on to other Q's now. Thats for the discussion.

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
public override unsafe int GetHashCode()
{
    fixed (char* text = ((char*) this))
    {
        char* chPtr = text;
        int num = 0x15051505;
        int num2 = num;
        int* numPtr = (int*) chPtr;
        for (int i = this.Length; i > 0; i -= 4)
        {
            num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
            if (i <= 2)
            {
                break;
            }
            num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
            numPtr += 2;
        }
        return (num + (num2 * 0x5d588b65));
    }
}
                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

Thats for the discussion. << Thanks I mean. Have a great day.