Since
2008
Since
2008
Since
2008
Hashtable is an implementation of a key-value pair data structure in java. You can store and retrieve a ‘value’ using a ‘key’ and it is an identifier of the value stored. It is obvious that the ‘key’ should be unique.
java.util.Hashtable extends Dictionary and implements Map. Objects with non-null value can be used as a key or value. Key of the Hashtable must implement hashcode() and equals() methods. By the end of this article you will find out the reason behind this condition.
Generally a Hashtable in java is created using the empty constructor Hashtable(). Which is a poor decision and an often repeated mistake. Hashtable has two other constructors
Hashtable(int initialCapacity)
and
Hashtable(int initialCapacity, float loadFactor)
. Initial capacity is number of buckets created at the time of Hashtable instantiation. Bucket is a logical space of storage for Hashtable.
Before seeing java’s Hashtable in detail you should understand hashing in general. Assume that, v is a value to be stored and k is the key used for storage / retrieval, then h is a hash function where v is stored at h(k) of table. To retrieve a value compute h(k) so that you can directly get the position of v. So in a key-value pair table, you need not sequentially scan through the keys to identify a value.
h(k) is the hashing function and it is used to find the location to store the corresponding value v. h(k) cannot compute to a indefinite space. Storage allocated for a Hashtable is limited within a program. So, the hasing function h(k) should return a number within that allocated spectrum (logical address space).
Java’s hashing uses uses hashCode() method from the key and value objects to compute. Following is the core code from Hashtable where the hashCode ‘h’ is computed. You can see that both key’s and value’s hashCode() method is called.
h += e.key.hashCode() ^ e.value.hashCode();
It is better to have your hashCode() method in your custom objects. String has its own hashCode methode and it computes the hashcode value as below:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
If you don’t have a hashCode() method, then it is derived from Object class. Following is javadoc comment of hashCode() method from Object class:
Returns a hash code value for the object. This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable.
If you are going to write a custom hashCode(), then follow the following contract:
The general contract of hashCode is: Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified.
The following is to improve performance of the Hashtable.
If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
hashCode() guarantees distinct integers by using the internal address of the object.
When we try to restrict the hashing function’s output within the allocated address spectrue limit, there is a possibility of a collision. For two different keys k1 and k2, if we have h(k1) = h(k2), then this is called collision in hashtable. What does this mean, our hashing function directs us store two different values (keys are also different) in the same location.
When we have a collision, there are multiple methodologies available to resolve it. To name a few hashtable collision resolution technique, ‘separate chaining’, ‘open addressing’, ‘robin hood hashing’, ‘cuckoo hashing’, etc. Java’s hashtable uses ‘separate chaining’ for collision resolution in Hashtable.
Java uses separate chaining for collision resolution. Recall a point that Hashtable stores elements in buckets. In separate chaining, every bucket will store a reference to a linked list. Now assume that you have stored an element in bucket 1. That means, in bucket 1 you will have a reference to a linked list and in that linked list you will have two cells. In those two cells you will have key and its corresponding value.
Why do you want to store the key? Because when there is a collision i.e., when two keys results in same hashcode and directs to the same bucket (assume bucket 1) you want to store the second element also in the same bucket. You add this second element to the already created linked list as the adjacent element.
Now when you retrieve a value it will compute the hash code and direct you to a bucket which has two elements. You scan those two elements alone sequentially and compare the keys using their equals() method. When the key mathches you get the respective value. Hope you have got the reason behind the condition that your object must have hashCode() and equals() method.
Java has a private static class Entry inside Hashtable. It is an implementation of a list and you can see there, it stores both the key and value.
To get better performance from your java Hashtable, you need to
1) use the initialCapacity and loadFactor arguments
2) use them wisely
while instantiating a Hashtable.
initialCapacitiy is the number of buckets to be created at the time of Hashtable instantiation. The number of buckets and probability of collision is inversly proportional. If you have more number of buckets than needed then you have lesser possibility for a collision.
For example, if you are going to store 10 elements and if you are going to have initialCapacity as 100 then you will have 100 buckets. You are going to calculate hashCoe() only 10 times with a spectrum of 100 buckets. The possibility of a collision is very very less.
But if you are going to supply initialCapacity for the Hashtable as 10, then the possibility of collision is very large. loadFactor decides when to automatically increase the size of the Hashtable. The default size of initialCapacity is 11 and loadFactor is .75 That if the Hashtable is 3/4 th full then the size of the Hashtable is increased.
New capacity in java Hashtable is calculated as follows:
int newCapacity = oldCapacity * 2 + 1;
If you give a lesser capacity and loadfactor and often it does the rehash() which will cause you performance issues. Therefore for efficient performance for Hashtable in java, give initialCapacity as 25% extra than you need and loadFactor as 0.75 when you instantiate.
Comments are closed for "Java Hashtable".
if you’re really interested in performance you should stick to hashmap if multithreading is no issue. You really should add a section about Hastable vs. Hashmap in this article
yes Joshi you are right. Between Hashtable and Hashmap, Hashmap is preferred in non-threaded environment.
When you are forced to use Hashtable, consider these performance tips.
Sure I will come up with an article about Hashtable vs Hashmap.
good info. keep posting. can u write some info on the DAO patterns.
Nicely explained..!
and implementation of hashCode for String is
h = 31*h + val[off++];in standard jdk 6 & 7
Good article after a long time…
Kindly start posting on JEE6 features.
Great. Clear & Simple. Thank you.
Most use full information.
It is very nice and clear. Can you take some real time examples and explain (like yellow pages). That would be great!!
Thank you for this post!!
Cheers,
Jyothi
nice artical
this kind of explanation is clear
“Hashtable is preferred in non-threaded environment.” – you mixed it up? ;) – hashtable is the synchronized version, so use hashmap instead, if multi-threading is not needed. And besides – one should always consider the synchronizedXYZ Methods of the Collections class instead of using special synchronized Collection types. So use: Collections.synchronizedMap if you want a synchronized version of HashMap.
But – nevertheless – the theory the blog post is talking about is of course the same for the hashmap and considered as useful information ;)
Oops! Born, thats a typo (very costly one) :0 I have fixed it. Thanks for pointing out.
Nice article Joe. Well explained. Thanks
Such a nice article i have ever seen..
Worth Reading. Nice post. Looking forward for more :) keep posting
Instead of using HashTable, If we use HashMap and put those block in a synchronized block..what you say on performance?
@Partha, using HashMap enclosed in a synchronized block is costlier than using a Hashtable. Since, the synchronization in Hashtable is fine-grained than this approach.
The best possible approach would be analyze the need for synchronization and avoid using Hashtable.
Very good explanation.Thanks alot :-)
awesome CSS !! i like it very much :D contents are lucid and to the point.. :)
It is very simple language that you used in this blog which makes me very impressive to read a lot of stuff about java from this blog. I am fortunate to take look at this website. Hopefully you will be coming up with better and essential information regarding Java.
Thank you so much
from
Prabha
This is a lucid and nice Article. You can always keep adding the features and extra information. We are also java developers and provide various projects for free. Would you give us an opportunity for a Guest Posting to write about Image Processing in Java? We will wait for your positive response.
Nice post…….please try to elaborate it with some examples….
very nice site and helpful for beginners :)
Hey joe the explanation is really excellent you can also post on struts, spring, hibernate.
Joe, Could you explain the Collision resolution for below scenario
Map map = new HashMap();
I- two keys are same .But it does not throw any exception. How it finds collision resolution?
map.put(“abc”,12);
map.put(“abc”,13);
&
II- two keys are different .But hascode values are same for two keys. How it finds collision resolution?
map.put(“abc”,15);
map.put(“cba”,18);
Your point to this line when discussing the use of value.hashCode():
h += e.key.hashCode() ^ e.value.hashCode();
A line much like this exists (Hashtable.java:948 in jdk 6u23). However, this line is NOT used in the regular business of put() and get(). Rather, it is the hashCode Entry inner class, which must override hashCode() because it overrides equals().
In normal put() and get() operations, the value’s hashCode is never used. (This must be the case, because the value is not known in a get operation.) Look at the get() method on line 332 and note that it only calls key.hashCode().
Thanks for posting this article! Since it’s getting plenty of readership, I wanted to make sure that people don’t get the wrong idea and think that the value’s hashCode plays a role in the put operation.
To be honest, calculating hash using both key.hashCode() and value.hashCode() is done in Map.Entry.hashCode().
Hashtable uses _only_ the value of key.hashCode() to find value. It would be quite surprising to use value’s hash for lookups.
I assume Map.Entry.hashCode() is implemented only for purpose of using Map.Entry as a key:
Map<Map.Entry, Integer>
Which maps par (String, Integer) -> Integer.
Great post Buddy.
Keep posting :)
Very nice…..
nice explanation! i was struggling to understand about hash table and hash map.Now i am clear.Thanks a lot.looking for more stuff….
Hi Joe,
Its pretty good article for Hashtable. I have got more idea about on this. The Explanation is very nice..
Keep on posting more article, best of luck.
Thangavel L Nathan.
Good work dude………. very very easy to understand…………
Please give a same demo for HashMap also.
Really very happy to see this article……Thanks a lot…
Information is very clear and in simple terminology. Thanks a lot.
this blog is great but if u posting the examples with real time that would be better…
why null is not allowed in Hastable..??
Very nice discussion…it has almost full coverage of the topic,which is most feared one in java..if you please give some practical examples..then it will increase reader’s understanding
Hi Joe,
Worth going through this article – well done
Regards
Raajesh
This is great!
i want hashcode for long string without collision please.
excellent and super
You are awesome… Last thing I am gonna say (Actually the first thing too)..
Thanks Joe for making Hashtable simple for me.All my queries are resolved after reading this short and simple article.You rock :)
your explanation was good..
also pl try to put simple example to construct a hashtable program in java……..
by
Reader
Nice explanation, I’ve one question. Plz give two different Keys which produces a same hashcode?
Please Post article on HashMap vs Hashtable
Sir,
Please write an article on Thread and Comparable/comparator. I like the the way you are explaining every topic. This blog became as one of good references.
Interesting….please write Hashtable vs Hashmap also. it will really help us
Thank you for this post. Very useful article for me.
Thanks Joe,
can you please provide a full article on java collection framework with example.
awesum………
thanks for the details…….
nice article..
Very good article Joe!
very awesum…. article joe
yeah… site is very useful for beginner as well as for those who want to know about any specific topic. great! Thank you very much
Also put all Hashing Techniques like Bucket all that.
Quick and briefly useful. Thank you for that. We need easy examples to start with and increase our skills in hashing.
Thank you
Thank you very much.
very well explained !!!
Very wonder full article….
I like very much
Very good article..
I like that….Thank you very much
thank you.
Hi Joe,Can you please clarify my doubt about HashTable.
the locking will happen only for adding/removing the object or every operation (reading also )
Nice article Joe, helps understand the basics very well !
Hi Joe,
It was nice article
Thanks
Hi joe,
Please provide How will we handle the error code like 500 internal server error in application level ?
Hey Joe!
It is a very nice article, it helped me a lot.
But it would be very nice if you explain about how buckets are created and handled in hashtables.
It was nice article.
Thanks,
Subbu
Hi Good Morning Sir,
I am getting confusion in ovberriding equals and hasshcode methods will please provide in detail information
Dear Joe,
Please explain how this hashCode() returns hash number and why attributes i and j are converted into String
int i,j;
public int hashCode()
{
String s1 += Integer.toString(i);
String s2 += Integer.toString(j);
return hash;
}
Dear Joe,
Please explain how this hashCode() returns hash number and why attributes i and j are converted into String
int i,j;
public int hashCode()
{
String s1 += Integer.toString(i);
String s2 += Integer.toString(j);
return hash;
}
Dear Ashok i think u missing some codes how it will return hash whn u not defined
Really fantastic article, thanks, Joe
Beautiful article
hi joe,
can you tell me the formula to calculate “hash function”?
Hi Joe,
i have been following your Articles in your website
They are just awesome
Can u please come up with Struts explanation Saying what happens inside the ActionServlet and how RequestProcessor Handles
Fantastic explanation,You are really Astute person.
Here uses came twice: “Java’s hashing uses uses hashCode() ”
Thank you..
Jigar Bhai ,Nice link :)
Nice article but I dont think this is correct
hashcode is calculated using
h += e.key.hashCode() ^ e.value.hashCode();
Simple logic: How will this work when you are doing a search on a hash table. You are just aware of the key and there is no way you will be directed to the right bucket in retrieval.
The bucket creation is done using only the hashcode of the key
Nice article.. very usefull.thnx for sharing
Hi joe,
Provide some good Examples for Hashtable.I am able to attend easily.
Hi Joe,
This is pretty awesome.
I didn’t get this statement.
“If you have more number of buckets than needed then you have lesser possibility for a collision”
The collision is purely depends on the symetric objects(Same in hash codes) right? how it is depended on size of bucket?
Hi Joe,
I am fan of you, you are sharing the excellent knowledge from your experience. Thanks a lot for that.
I need some help from you that I just want a sample code (any class) which doesn’t override hashcode() method and shows different hashcode number in different context..
Gr8t 1… Thanx
Please me give real time ussage of collections..suppose in bank project where we use hash table or hashmap or ArrayList ect..
hi Joe,
i didn’t understand completely how the Collision Resolution. if h(B)=H(C)=310 if same hash code is returned, can you explain how the collision is resolved?
didn’t understand completely how the Collision Resolution. if h(B)=H(C)=310 if same hash code is returned, can you explain how the collision is resolved?
There are several differences between HashMap and Hashtable in Java:
1. Hashtable is synchronized, whereas HashMap is not. This makes HashMap better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.
2. Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.
3. One of HashMap’s subclasses is LinkedHashMap, so in the event that you’d want predictable iteration order (which is insertion order by default), you could easily swap out the HashMap for a LinkedHashMap. This wouldn’t be as easy if you were using Hashtable.
Hi can u provide some tutorial also on hsqldb.
Please do so
Will u please let us know abt ring buffer
good explanation on hashing…..
No need to covert into Integer here and can be done as below:-
public int hashCode()
{
int hash = 0, p = 31;
hash = hash * p + i;
hash = hash * p + j;
return hash;
}
Basic idea is to generate hashcode uniquely among the object and calculation logic should be simple enough.
very clear and easily understand………
Thank u very mush
Hi Joe, I have a question on HashMap below :
myMap.get(itr.next()) results output as “Four”
How is it possible that output is coming “Four” for the key provided as null.
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
public class HashMapTest {
public static void main(String[] args) {
HashMap myMap = new HashMap();
myMap.put(“1”, “One”);
myMap.put(“2”, “Two”);
myMap.put(“3”, “Three”);
myMap.put(null, “Four”);
Set mySet = myMap.keySet();
Iterator itr = mySet.iterator();
while (itr.hasNext()) {
System.out.println(myMap.get(itr.next()));
}
}
}
/*
Output :
Four
Three
Two
One
*/
yes..nice differentiation..
hi sir,
can we able to read and write excel(.xls) using hashtable ??
Hi Joe,
This is pretty awesome.
I didn’t get this statement.
“If you have more number of buckets than needed then you have lesser possibility for a collision”
The collision is purely depends on the symetric objects(Same in hash codes) right? how it is depended on size of bucket?
See the code below from HashMap
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
Basically it will return the hash code for null value as 0.So in your example the key is stored at 0 index and when you pass the key the value stored at index 0 will be returned which is “Four”
Thanks,
Ramesh M
In the first scenario, it overrides the value for the key “abc” from 12 to 13.
In the second scenario, it uses key’s equals() method for collision resolution.
Good article!!!! Keep sharing such valuable info…
Hi Joe,
In which scenario I should use HashTable. Can you please give scenarios for all Collection implementations. i.e., for ArrayList, LinkedList, HashMap, HashTable, HashSet, TreeSet etc.
Thanks in advance.
Excellent document …Trying to understand about the hashcode() and Equals() methods contract from long time. Finally got a nice and simple document which gives a clear explanation, thanku.
Why Hashtable class does not allow null key and null values? hash value for “null” is zero and HashMap is storing null key (and corresponding value) in the 0th location. why hashtable is not using this ? Is there any specific reason ?
Very Nice,Can any one explain the difference between hashtable and hashmap with realtime examples?
Thanks in Advance
Thanks for explaining in simple language..
My question is regarding size of HashMap/HashTable.
1.When will rehashing be done?.
suppose 16 is the initial size and i have added 12 ie. 16*0.75 element into hashmap. is it irrespective of element being added to same or different bucket?
2. cane we set default size? if yes than how?.
Please explain these lines written above “The general contract of hashCode is: Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified.”
note: please let me know where exactly(in real time) we are going to use hashtable(with example).. and advantages over It???