Why doesn't my HashTable allow key collisions?

I read that HashTable can map same key to multiple values. That's what collision is.

Now I run the program like this:

Dictionary<String,String> hTable = new Hashtable<String,String>();
hTable.put("a", "aa");
hTable.put("a", "ab");
System.out.println(""+hTable.get("a"));

My thinking says I should get aa and ab.

But actual output is a开发者_如何学Pythonb

Why is it so? Where is the collision then?

There is no collision. A HashTable entry maps a key to only one value.

The third line in your sample:

hTable.put("a", "ab");

replaces the mapping from a to aa with a mapping from a to ab.

After your four lines of code complete execution, hTable has only one mapping: a to ab.

A collision only happens internally. To the user, are resolved transparently.

That's why a hashtable can be a dictionary -- it maps each key to exactly 1 value. If it mapped to more than 1 value then it wouldn't be a dictionary.

Hashtable doesn't map the same key to multiple values. Collision is that multiple keys might be mapped to the same hash value. It is resolved by the data structure itself which is transparent to you.

If you want to get aa and ab by hTable.get("a"), you need to create Dictionary<String,List<String>> and append the list with the values of the same key.

In your code

hTable.put("a", "aa");
hTable.put("a", "ab");

The keys are the same. So the second operation used "ab" to override "aa". That's why you only get "ab".

HashTable is Key -> Value mapping. That means you can not have multiple values for more one key. You need to combine two data structures store multiple values with one key.

For Example, You can put a linkList inside you HashTable. For example

HashTable<String,LinkedList<String>> table = new HashTable();
LinkedList<String> list = new LinkedList();
list.add("aa");
list.add("ab");
table.add("a",list);

now you can do this get aa and ab value;

table.get("a").get(0); // returns aa
table.get("a").get(1); // returns ab

I strongly recommend you to go through the basics of data structure and algorithm.

You want to retrieve values by their keys. An array serves this purpose but is restricted to using integer keys and may use too much space (think about storing values at position 0 and 1000 only, you have to allocate the entire array for 2 elements).

HashTables solve both of these problems with:

• a dispersive non-injective function that converts an array of bytes of variable length in a fixed length array of bytes. This means that you have hash(bytes_1) == hash(bytes_2) but it doesn't happen too often and if bytes_1 ~ bytes_2 the hashes are different;
• an index of used hashes. If the function returns an array of 10 bytes you have 2^80 possibilities, so you need to keep a sorted list of the hashes that you already encountered;
• an array of linked lists. The index of hashes maps the hash with the position in the array.

The collision means that two keys have the same hash: map.put("key1", "value1"); map.put("key2", "value2") key1 and key2 might wind up in the same linked list.