Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 309
  • Last Modified:

Some useful thoughts are needed

Yesterday I came across one of my friend's assignments for a CS2 class. Basically he has to create a template Array of (template) Lists and use that as a (template) HashTable. The Lists are dynamic. HashTable uses multi-inheritance.

There are a few points in the teacher's design I do not really think are necessary. THIS IS NOT MY HOMEWORK, SO DON'T PROVIDE CODES, I'll only need reasonable thoughts on this. Here's the basic layouts (pseudo):

List<T> {...};

Array<T> {
protected:
   T*   dat_arr;
public:
   Array(int);
   ...
};

HashTable<T> : public Array< List<T>* >, public List<T> {
protected:
   int HashTableSiz;
public:
   HashTable(int);
   ...
};

I keep on thinking what on Earth that he wanted when he let HashTable have a HashTableSiz, where logically that should have been in Array. And to create an Array < List<T> > is Ok (makes sense), but why an Array of pointers to Lists, since the Lists are first and foremost dynamic?
0
n_fortynine
Asked:
n_fortynine
  • 4
  • 4
1 Solution
 
Kyle AbrahamsSenior .Net DeveloperCommented:
Depends on what kind of hashing you're using.

If you use open hashing then it's possible to have
(using a mod 10 function)

0 -> 10 -> 20 -> 30
1
2 -> 32 -> 562 -> 692
3
4
5 -> 15 -> 95
6
7
8
9

where the list would be 10 15 20 30 32 95 562 692.

It's developed using the % 10 function, then the node is added on to the last one. (hence why it's dynamic, when you get a new number add it on to the last.) Obviously this isn't the best way as you can have 0's table with 30 elements to search and 9 with nothing in it.  But it is one of the easiest one's to implement.


0
 
n_fortynineAuthor Commented:
Thanx ged325, but the hashing is not what I asked for. I was thinking what advantage (if any) Array< List<T>* > has over Array < List<T> >?
0
 
Kyle AbrahamsSenior .Net DeveloperCommented:
ah, pretty much, storage space:

if you have

array[0] = list;

Then you actually have 2 copies of it.  One in array, one where the list is actually stored.  By making it pointers, you only save the locations of the lists and can get to it by going to that location, instead of making the array hold it itself.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
n_fortynineAuthor Commented:
ged325, are you saying that by not having <List<T>* I'd have 2 copies of the lists? Would you be able to elaborate more on that, or perhaps provide some useful links? Thanx
0
 
Kyle AbrahamsSenior .Net DeveloperCommented:
if you have the list actually stored in the array it would look something like

array[x]   list
0        10 20 30 40 50 60
1        11 21 31 41 51
2        12 22 32 42 52
.
.
.

now, when you say array[0] = list0; //where list 0 is 10 20 30 40 50 60

you have:
The list0, the list itself which is stored at one address
and
array[0], which is a copy of list0 inputed into that row.

2  copies of the array.

Besides that, if you were to grow list 0, if the next memory cell wasn't free, it would have to move all of the array to a spot in free memory.  (The array must be in contiguous memory.)  

By storing the address of the list, (IE, pointing to it)
it has some advantages:

1) The lists have do not have to be in contiguous order, they can be sorted all throughout memory.  (IE: you can have the first node at 0200, and the next one at 6004, it doesn't matter because you point to that location through next) As long as there's a free cell, you can grow much easier.

2)  There's only one copy of the list in memory

That's all I can think of off the top of my head.  Any more questions?

0
 
n_fortynineAuthor Commented:
Alrite thanks. I'll not get too hooked up on this. It ain't my problem in the first place =)
0
 
Kyle AbrahamsSenior .Net DeveloperCommented:
do you understand what I'm saying though?
0
 
n_fortynineAuthor Commented:
yeah i think i understand it. just that i never thought the system would "back up" the list that way. =)
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

  • 4
  • 4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now