• Post Reply Bookmark Topic Watch Topic
  • New Topic

Help get started with Hash Tables  RSS feed

 
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello guys, I've started to learn with Closed and opened bucket hash tables.. We have an assingment in school, and we have to make a translator. First we input some words/translation in another language... then after that, we write some words and after writing END, the program should look if there is a translation for the typed words or not, this should be done with Opened Bucket Hash Tables.

I understand the whole idea on how they work, I just need some help to start writing the code, to see some examples on how that goes (I've tried tens of sites on google, but I don't know why Google is having some hard time showing me what I really want... I guess because of the word "Hash" or who knows ...
 
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So you have a list of words, and each word is tied to a translation? One solution to this would be to use a HashMap (a type that is part of the standard Java API).

I get the impression though that you are expected to write your own implementation of a hash-based container for this though. Is that correct?

What have you written so far?
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike. J. Thompson wrote:So you have a list of words, and each word is tied to a translation? One solution to this would be to use a HashMap (a type that is part of the standard Java API).

I get the impression though that you are expected to write your own implementation of a hash-based container for this though. Is that correct?

What have you written so far?


I believe your question means that I should think of a way to order the words, right? If that's the case, than yes, but I'd probably go with their first letter I guess...
 
Mike. J. Thompson
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My question is, are you expected to write your own hash-based container or can you use one that is already provided by java?
 
Kaspersky Ukshini
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike. J. Thompson wrote:My question is, are you expected to write your own hash-based container or can you use one that is already provided by java?


I believe I have to write my own..after they see we are comfortable using them, they'll allow us to use the one provided with Java.
 
Mike. J. Thompson
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Right, so what do you already understand about a hash-based container, and what operations do you think yours needs to have?
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kaspersky Ukshini wrote:I believe your question means that I should think of a way to order the words, right?

No. Hashed sets usually aren't ordered. They're main purpose is to be able to access items randomly in constant time, and that's why the hash itself is so important. In an ideal world, every hash would be unique and simply used to store an Item in a particular location in an array, so the process would be:
For an "add":
  • Calculate hash.
  • bucket[hash] = Item.
  • and for a "get" (or contains()):
  • Calculate hash.
  • return bucket[hash] (or 'return bucket[hash] != null').

  • And, as you can probably understand, that would be incredibly fast. However, the problem is that it's basically impossible to create a unique hash, so you need some way of resolving "collisions".

    I think (but I'm not sure, because the terminology is a bit confusing) that your "open bucket" set makes each bucket a List (or stack), whereas in a "closed" set, each bucket is a single Item. In the latter case, you'll need to have some consistent method of searching for an empty bucket if the one you initially try is full (and there are LOTS of variants, including ones that "displace" other values); and you'll also need some way to deal with the situation when ALL (or some proportion of) buckets are full - ie, some way to increase capacity.
    Actually, you'll probably want to do it in both cases, but in the "open" one it's less important - performance may degrade, but you'll never "run out of room".

    My advice: Deal with each case individually; and I think you may find the "open" style easier to start with.

    Winston
     
    Kaspersky Ukshini
    Ranch Hand
    Posts: 122
    C++ Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Mike. J. Thompson wrote:Right, so what do you already understand about a hash-based container, and what operations do you think yours needs to have?


    I need to see some examples, how to add a hash based on it's first letter, and how to later search for it...
     
    Winston Gutkowski
    Bartender
    Posts: 10575
    66
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Kaspersky Ukshini wrote:I need to see some examples, how to add a hash based on it's first letter, and how to later search for it...

    I don't understand. Why do you want to do that? For starters, it won't work for a "closed" set (at least not a single-tier one). For seconds: if these "words" are Strings, the class already provides a perfectly good hashCode() method for the entire word.

    My advice: Try not to get too bogged down in how you're going to code this too soon. You need to understand WHAT you need to do first; and the Wiki page is a pretty good place to start for that.

    Winston
     
    Marshal
    Posts: 56610
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Basing hashes on first letters is probably not a good idea.
    Start by creating a class with correctly overridden hashCode and equals methods. You can read about those methods in several places, notably Joshua Bloch's Effective Java™, Angelika Langer Odersky Spoon and Venners.
    Test objects of your class with different attacks at the hash code and equals methods.
    Then consider how you would use that class' instances as “K”s in a Map. Note all the problems about equals and hash code apply to the “K”s; none applies to a “V”.
     
    Consider Paul's rocket mass heater.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!