• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Hashing ...

 
Ranch Hand
Posts: 55
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Does anybody know what is hashing and how hashing works and how it helps in faster lookup of object in its implementation (for instance : Hashtable) ?
 
Greenhorn
Posts: 28
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Salim,
See if this can help
http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?hashing
Mayuri
 
Ranch Hand
Posts: 2120
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The funtion hashCode relates the value to put in a hashTable with the position of that value in the data estructure. For searching, is quicker to use the hashCode funtion to yield the position instead of searching the whole estructure.
The problem is that the range of values to store is much greater than the capacity of the container. Thus it is not possible to have only one value in each position in the container. Solution: each position in the container (a bucket) is itself another container of a growable capacity, for instance an ArrayList. When the hashCode funtion yields the same bucket for several values, equals is used on the accessed value to compare it with the values placed in the same bucket.
Imagine we want to store Integers ranging from 1 to 20 in an array whose length is 15. We cannot have a hashCode that relates Integer 1 to position 1 etc. Some Integers are going to end up in the same bucket. If the array is of type ArrayList is possible to acomodate several Integers in each position. When an Integer is going to be put into the array, hashCode is invoked on it yielding a position of an ArrayList in which is stored. When the container is questioned for the presence of the Integer, applies the hashCode to get the ArrayList in which it was stored. Now the equals is invoked to compare the requested Integer with all the Integers residing in the ArrayList.
Between hashCode and equals the identity of an object must be determined. The former indexes into the array, and the latter causes a sequential search in a bucket (ArrayList in our example).
For this to be quick --the goal of this structure-- hashcode must spread out the possible values along the array, otherwise some buckets will contain many values; in this situation the sequential search in a bucket ruins the performance.
 
Author & Gold Digger
Posts: 7617
6
IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Also check out the following articles:
Equals And Hash Code by Manish Hatwalne
 
Salim Mohamed
Ranch Hand
Posts: 55
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you guys. Those are good links.
 
Valentin Crettaz
Author & Gold Digger
Posts: 7617
6
IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just found another good link to a sample chapter of Core Java 2 on the Collections Framework which explains well the details behind hashtables.
Core Java 2 : Chapter 2 : Collections
Also, check out this excellent article by Jack Shirazi on the O'Reilly network:
Optimizing Hash Functions For a Perfect Map
[ December 17, 2002: Message edited by: Valentin Crettaz ]
 
Whatever. Here's a tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic