• Post Reply Bookmark Topic Watch Topic
  • New Topic

Would you confirm/refute understanding of a hash function?  RSS feed

 
Mohammed Azeem
Ranch Hand
Posts: 56
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good Evening,

I'm studying the Java Collections Framework.

To cross-check my reading I've also used Youtube.

So in this video I've watched, a hash table is used to turn a key (a person's name) into some sort of index which points to the storage location of that person's phone number. Why on earth they don't just store the person's phone number in a normal bog-standard 2-D table, I don't understand yet.

But my question is: Very basically... does a hash function tell you whereabouts to look for stored information in a table (the hash table) rather than having to trawl down columns and across rows to find it in a traditional table?

My first impression of this collections 'thing' is disappointment, unless I come across an example on the internet that compares say, using ordinary arrays and collections to do the same task. Well must plod on...I'm sure I'll realise its usefulness eventually.
 
Mohammed Azeem
Ranch Hand
Posts: 56
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sorry, there's another source that I ought to look at aswell.

And that is, the official Java tutorials for this subject.. hmmm.
 
Stefan Evans
Bartender
Posts: 1837
10
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your interpretation of the Hash is pretty good.

Using a name to look up an age is probably just a trivial example to demonstrate things. You are right, at that level it probably could be done quite efficiently in a simple 2d table.
But what assumptions are you making about this normal bog standard 2d table? Is the data in it sorted? Is it a database table? Or something else?

Lets say you have a million bits of paper with a person's name and age. All in one big pile. And the list isn't sorted in any way.
The only way to find a person in that list would be to look at the records one at a time until you found that persons name. Not the most efficient method.
Alternatively if you grouped all of the records into piles based on the first letter of their name (All names starting with 'A' in one pile, all those with 'B' in another...) you could find what you want a little more efficiently .
That is in essence what a Hash is used for. Split a large unsorted bunch of data into 'groups' that can be searched through more efficiently.
The 'hash function' in my example was 'the first letter of their name'. That makes sense to humans, not so much to computers.
 
Mohammed Azeem
Ranch Hand
Posts: 56
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you Stefan.

You made my day!
 
Mohammed Azeem
Ranch Hand
Posts: 56
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, the issue is resolved. No buttons here to indicate this though.

Guys, you probably already know this, but consulting several references is always helpful.

For example, when I grew out of that really nice book Java for Dummies by Barry Bird, I bought Herbert Schildt's Complete Java Reference.

That book is so good for post-beginners that I thought I would never need to consult anything else but guess what, Herbie's book failed miserably when it came to Java Collections (for me anyway - sorry Mr. Schildt) but the Java for Dummies was excellent (I'd skipped Java Collections on the first pass).
 
Guillermo Ishi
Ranch Hand
Posts: 789
C++ Linux Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Grouping names into piles based on the first letter wasn't meant to be an example of a good hash function though. You would have only 26 piles maximum and E would be a big pile and Q an empty one The ideal function would distribute the names more equally and would have a large number of piles and would be scalable in the number of piles.
 
Campbell Ritchie
Marshal
Posts: 56593
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not sure, but I don't think Schildt is correct about nextLine() in that book.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!