I understand there is a hashing technique is applied to a key to store its value in the memory address.
But I don't understand how the collision is happening here? Which hashing algorithm does Java use to create a memory space? Is it MD5?
In hashing, large keys are converted into small keys by using hash functions. The values are then stored in a data structure called hash table. The idea of hashing is to distribute entries (key/value pairs) uniformly across an array. Each element is assigned a key (converted key).
HashMaps use an inner class to store data: the Entry<K, V>. This entry is a simple key-value pair with two extra data: a reference to another Entry so that a HashMap can store entries like singly linked lists. a hash value that represents the hash value of the key.
It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.
Hashtable is a kind of Hash map but is synchronized. Hash map is non–synchronized, permits one null key & multiple null values, not-thread safe i.e. cannot share between many threads without proper synchronization, the key/values pairs are stored in Hashtable. The Hash table does not allow null value/key.
The basic idea of HashMap
is this:
HashMap
is really an array of special objects that hold both Key and Value.hashCode()
method that every object has. Therefore, when you are writing a new Class
, you should take care of proper hashCode()
and equals()
methods implementation. The default one (of the Object
class) takes the memory pointer as a number. But that's not good for most of the classes we would like to use. For example, the String
class uses an algorithm that makes the hash from all the characters in the string - think of it like this: hashCode = 1.char + 2.char + 3.char...
(simplified). Therefore, two equal Strings, even though they are on a different location in the memory, have the same hashCode()
.hashCode()
, say "132", is then the number of bucket where the object should be stored if we had an array that big. But we don't, ours is only 16 buckets long. So we use the obvious calculation 'hashcode % array.length = bucket'
or '132 mod 16 = 4'
and store the Key-Value pair in a bucket number 4.HashMap
, so you want to tell your Maps
how many buckets you'll use if you know it in before.An image, courtesy of Wikipedia:
In this case,
mod 256
, point to four different slots in the array.Now, if you tried to look up a telephone number of Sandra Dee, you would hash her name, mod it by 256, and look into the bucket 152. There you'd find John Smith. That's no Sandra, look further ... aha, there's Sandra chained after John.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With