java Hashtable help

Printing Hashtable in O(N) time

Page 1 of 1

6 Replies - 8893 Views - Last Post: 26 April 2006 - 01:27 AM Rate Topic: -----

#1 fitch1411  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 23-April 06

java Hashtable help

Posted 23 April 2006 - 10:21 AM

Here's my problem i need help solving...
**************************
A programmer wants to use a hashtable to store a set of Objects (with no duplicates). The programmer knows how to implement a hashtable so that the insert, lookup, and delete operations are all constant time using bucket hashing (i.e. fixed-size array of lists) and an appropriate size hashtable with a good hash function. However, the programmer doesn't know how to display all of the items in the hashtable in time proportional to the number of items in the hashtable. A straightforward implementation would iterate through the elements of the hashtable's array displaying every item in each element's list. This requires time proportional to the size of the array, which might be much larger than the number of items in the hashtable.

For this homework, you are to figure out how to implement display so that is runs in time proportional to the number of items in the hashtable. Supplement the hashtable using another data structure (in addition to the hashtable's array) or by adding extra information to what would be stored in the hashtable's array. For full credit, your solution should not make the insert, lookup, or delete operations take more than constant time. Note that the items in the hashtable can be printed in any order.

Describe how you would supplement the hashtable and how your solution would work. Describe what happens when a value is inserted into the hashtable, what happens when it is removed, and how the display operation would be implemented. Also illustrate your idea with some pictures.
*********************************

Is This A Good Question/Topic? 0
  • +

Replies To: java Hashtable help

#2 Amadeus  Icon User is offline

  • g+ + -o drink whiskey.cpp
  • member icon

Reputation: 248
  • View blog
  • Posts: 13,506
  • Joined: 12-July 02

Re: java Hashtable help

Posted 23 April 2006 - 11:29 AM

Hello,

The site has a policy by which we prefer to see some good faith effort on the part of the user before providing code or answers for academic assignments. If you could please post the code you have written in an attempt to solve the problem, we would be happy to guide you.
Was This Post Helpful? 0
  • +
  • -

#3 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 205
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: java Hashtable help

Posted 23 April 2006 - 11:07 PM

It's odd how you both posted hashtable questions in the same day... :)

when displaying the items in a list O(N) is the best you can do, as you are required to 'visit' every item. An iterator is exactly what you need, it will run in O(N) if written properly, i have written them for vectors, arrays, and linked lists and they are all quite similar, it's all about the data you keep track of.
Don't think about lists, but rather how an iterator works (they are as efficient as they can be)

This post has been edited by William_Wilson: 23 April 2006 - 11:08 PM

Was This Post Helpful? 0
  • +
  • -

#4 fitch1411  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 23-April 06

Re: java Hashtable help

Posted 25 April 2006 - 05:46 PM

Alright, this is what I have so far....
I believe that they way to display the hashtable is to keep track each time you insert an object, where you insert this, and then store this value somewhere, and then if this object were to be deleted, and there are no other object within the ArrayList, you would delete that hashFunction number from wherever it is stored. That way when you call lookup, you only call lookup on the stored values which would make it possible to print all the objects with O(n) within the hashtable, the problem I am having is where I can store these values, since you would need to access, insert, and delete these values with constant time since you still want to preserve the o(n) time complexity, and the only viable way of doing this would be to use another hashtable to store the integer values of which arrays actually hold values. I was wondering if you could steer me in the right direction or tell me if i'm on the correct path, and I was also wondering how exactly you would like me to illustrate this concept...Thanks for your help

I don't think an iterator would work, just because that would acess every array, which if some arrays are empty would create an order time of larger than order N, any directional help or poitners would be greatly appreciated, thanks....
Was This Post Helpful? 0
  • +
  • -

#5 1lacca  Icon User is offline

  • code.rascal
  • member icon

Reputation: 44
  • View blog
  • Posts: 3,822
  • Joined: 11-August 05

Re: java Hashtable help

Posted 25 April 2006 - 07:19 PM

Try to find a data structure that supports printing its elements in time proportional to the number of elements, but don't care about seeking (deleting and inserting) right now.
Once you have it, think about why can't it delete and insert in constant time. Probably because it's seeking takes too much time (before deleting and inserting its needed, too)- if not, find another one.
Since you are going to store your elements in both the hashtable and the other collection, you can suppose that inserting, seeking and deleting is done first in the hashtable. So if you could store the position of the element in the other collection inside the element, then you wouldn't have to seek in hte secondary structure.
Does knowing the element's position in the secondary structure provides constant accesstime (insert, delete)? If not, start over :P

Well, I hope I didn't give away too much information to be apprehended by the mods :o
Anyway, I left out some details and there are still plenty of problems to be solved, so have fun with it.
Was This Post Helpful? 0
  • +
  • -

#6 fitch1411  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 23-April 06

Re: java Hashtable help

Posted 25 April 2006 - 08:46 PM

Alright here is an idea, since my array of say arraylists holds objects, could i make the first array of my hashtable hold a hashtable object that then stores integers of which arrays are full, and then every time an object is inserted into the the array, that position number is stored in the hashtable in the first array, likewise with deleting it too, that way when going to display the objects, the look up of the positions would be constant time, thus acessing and printing the conents of the arrays that are stored withing the first array, does it soudns like i'm on the right track?
Thanks for all your help...
Was This Post Helpful? 0
  • +
  • -

#7 1lacca  Icon User is offline

  • code.rascal
  • member icon

Reputation: 44
  • View blog
  • Posts: 3,822
  • Joined: 11-August 05

Re: java Hashtable help

Posted 26 April 2006 - 01:27 AM

I am sorry, I don't fully understand what you are writing, but I think you are on the right track, as the main ideas seem to be correct. If you post your (pseudo)code, we could tell for sure if it works as required or it needs some more thinking.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1