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.
Hashing and 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).
Hashing in Java
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
* <code>java.util.Hashtable</code>.
If you are going to write a custom hashCode(), then follow the following contract:
* The general contract of <code>hashCode</code> is:
* <ul>
* <li>Whenever it is invoked on the same object more than once during
* an execution of a Java application, the <tt>hashCode</tt> method
* must consistently return the same integer, provided no information
* used in <tt>equals</tt> comparisons on the object is modified.
The following is to improve performance of the Hashtable.
* <li>If two objects are equal according to the <tt>equals(Object)</tt>
* method, then calling the <code>hashCode</code> 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.
Collision in Hashtable
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.
Collision Resolution in java’s 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.
Hashtable performance
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.
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..!
See About : Hash Table VS HashMap :http://stackoverflow.com/questions/40471/java-hashmap-vs-hashtable
and implementation of hashCode for String is
h = 31*h + val[off++];in standard jdk 6 & 7
See this also ,,http://stackoverflow.com/questions/6493605/how-does-java-hashmap-work
Most use full information.
Good article after a long time…
Kindly start posting on JEE6 features.
Great. Clear & Simple. Thank you.
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
great post
Nice article
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.
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;
}
Very good explanation.Thanks alot :-)
Very Nice.. Keep it mate!!
awesome CSS !! i like it very much :D contents are lucid and to the point.. :)
Really nice post, comprehensive and upto the mark. I have also covered some important aspects of the Java Map interface on my blog . You would also find a detailed post on Map synchronization and concurrent HashMaps.
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
ok
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.
Nice Article joe !But if you go into still deeper with articles it will be really great !
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.
ok….thanks da …keep posting
this blog is great but if u posting the examples with real time that would be better…
nice keep it up
why null is not allowed in Hastable..??
i think it should be edit.have a look on this code .,,
java.util.HashtableVery 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.
http://javapapers.com/wp-content/themes/papers/images/pencil.png
awesum………
thanks for the details…….
nice article..
Very good article Joe!
very awesum…. article joe
wow nice jun jun
wow nice jun jun
well expland dude…….
first time i understood the hashcode and equalsmethod in java… good work it helps lot of people
Great post Joe :) Keep posting more..
gr8
its really very gud article…but it cover only 1 topic..should post more article.
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.
very very clear explanation on hash table..
Thanks a lot
wonderful～
i love you!
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 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
iam new to java can anyone explain why hash map is used for?
good explaination
Fantastic explanation,You are really Astute person.
Very Good Explanation
Pingback: Java String