Can Anybody explain Internal code of HashMap?

HashMap works on the principle of Hashing . To understand Hashing , we should understand the three terms first i.e Hash Function , Hash Value and Bucket . What is Hash Function , Hash Value and Bucket ? hashCode() function which returns an integer value is the Hash function. The important point to note that , this method is present in Object class (... more» read less

To understand Hashing , you should understand the three terms first i.e Hash Function , Hash Value and Bucket . hashCode- hashCode() function which returns an integer value is the Hash function. The important point to note that , this method is present in Object class. This is the code for the hash function(also known as hashCode method) in Object Class : public int hashCode(); The most important point to note from the above line : hashCode method return int value . So the Hash value is the int value returned by the hash function . So summarize the terms in the diagram below : public int hashCode() { //some function code return intValue; } bucket - A bucket is used to store key value pairs . A bucket can have multiple key-value pairs . In hash map, bucket used simple linked list to store objects . HashMap in Java works on hashing principle. It is a data structure which allows us to store object and retrieve it in constant time O(1) provided we know the key. In hashing, hash functions are used to link key and value in HashMap. Objects are stored by calling put(key, value) method of HashMap and retrieved by calling get(key) method. When we call put method, hashcode() method of key object is called so that hash function of map can find a bucket location to store value object, which is actually index of internal array, known as table. HashMap internally store mapping in form of Map.Entry object which contains both key and value object. When you want to retrieve the object, you call get() method and again pass key object. This time again key object generate same hash code (it's mandatory for it to do so to retrieve object and that's why HashMap keys are immutable e.g. String) and we end up at same bucket location. If there is only one object then it is returned and that's your value object which you have stored earlier. Things get little tricky when collisions occurs. Since internal array of HashMap is of fixed size, and if you keep storing objects, at some point of time hash function will return same bucket location for two different keys, this is called collision in HashMap. In this case, a linked list is formed at that bucket location and new entry is stored as next node. If we try to retrieve object from this linked list, we need an extra check to search correct value, this is done by equals() method. Since each node contains an entry, HashMap keep comparing entry's key object with passed key using equals() and when it return true, Map returns corresponding value. read less

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time. This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important. An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets. read less

Note : HashMap and LinkedHashMap stores the elements according to Hashtable algorithm only. In Map interface, elements will be stored using keys. Keys are always unique(duplicates not allowed). Keys are also objects. Duplicate elements are allowed with unique keys. "null" key is allowed in HashMap and LinkedHashMap. "null" object is also allowed. It is allowed to store the elements with heterogenous keys(but unique). Duplicates will be replaced but not rejected. HashMap : 1) available in util package 2) since from jdk 1.2 3) not ordered 4) duplicates allowed with unique keys 5) default capacity is 16 6) default load factor is 0.75 7) HashMap is not synchronized by default. but can be synchronized explicitly as follows. Collections.synchronizedMap(new HashMap(...)); read less

TreeMap : 1) TreeMap maintains ascending order of keys. 2) TreeMap does it through Balanced binary trees. 3) null key is not allowed 4) only unique data type keys(homogenous) are allowed. 5) Using what type of key, we are storing the first element into map Object, remaining elements also must be inserted with the same type of Key. read less

Hashmap will work based on hashing technique,HashMap in Java works on hashing principle. It is a data structure which allows us to store object and retrieve it in constant time O(1) provided we know the key. In hashing, hash functions are used to link key and value in HashMap. Objects are stored by calling put(key, value) method of HashMap and retrieved by calling get(key) method. When we call put method, hashcode() method of key object is called so that hash function of map can find a bucket location to store value object, which is actually index of internal array, known as table. HashMap internally store mapping in form of Map. read less