Teen Programmers Unite  
 

 

Return to forum top

c++ project

Posted by Leydeya [send private reply] at April 23, 2002, 02:51:03 AM

have anybody know the codding of hashing using C++..please give me coz i really need it for my project.

Posted by vikram_1982 [send private reply] at April 23, 2002, 05:23:35 AM

What type of Hashing do u need? Collission,Bucket ... etc. or just the ordinary one.

Posted by taubz [send private reply] at April 23, 2002, 01:10:40 PM

Those are types of hash tables, which employ "hashing." Hashing is generating a single number from a set of bytes. There are many ways to hash, and a google search would probably give you the best methods. But anyone can figure out how to do a simple hash...

- taubz

Posted by unknown_lamer [send private reply] at April 23, 2002, 01:52:05 PM

I wrote a hash table (linked buckets) in C...it uses void*s and and a user-supplied
comparison function. It works. I can email it to you if you'd like,
just send a message to unknown_lamer at unknownlamer.org.
The hash table was written to be clear, not fast, because I am using it as
part of a presentation on Scheme / C (and why Scheme is better for
high school computer science classes). I have one written in Scheme as
well if anyone is interested (if ben would mail me the parts of my site that
I lost in my stupid fs barf, then they would all be up on unknownlamer.org)

Posted by Psion [send private reply] at April 23, 2002, 02:27:24 PM

I don't think it's appropriate for people to be offering to send code to others who ask for it for their school projects.

Posted by unknown_lamer [send private reply] at April 23, 2002, 02:57:56 PM

I didn't see the project part. Ooops. Never Mind about that then.
/me learns to read

Posted by vikram_1982 [send private reply] at April 24, 2002, 01:41:36 AM

Why dont you refer a good Data Structures book. It should be able to help u out. All the best.

Posted by Leydeya [send private reply] at April 27, 2002, 03:00:21 AM

actually my project title is searching student information using hashing table in C++..i already make the codding of student record and now i need just the codding of hashing namely collision,searching linear and chaining and the codding of timer because i want to show the differences of time when we search the student information.so anybody can help me because the due date is in the end of may and im really worry now...or mail me at leydeya@hotmail.com

Posted by taubz [send private reply] at April 27, 2002, 04:32:27 PM

Don't you have a textbook that has this information?

Posted by vikram_1982 [send private reply] at April 27, 2002, 09:42:30 PM

Ley,.... check ur mail.

Posted by vikram_1982 [send private reply] at April 27, 2002, 09:44:25 PM

Try, "The Complete Reference in Data Structures. 2 e/d" I believe it has the exact program that u need in it. :). In India it costs Rs.400, which works up to around US $6.

Posted by Leydeya [send private reply] at April 29, 2002, 02:40:08 AM

thanks for all your help especially vikram_1982 and unknown_lamer but it dont help much in my project.can you all give me the details codding of hashing(linear searching and chaining)

Posted by Leydeya [send private reply] at April 29, 2002, 02:59:50 AM

the information in the book dont help much..so i prefer asking to those who expert in C++..by the way anybody know the codding for timer.??

Posted by vikram_1982 [send private reply] at April 29, 2002, 05:50:14 AM

time.h has a library function in it called clock() that can return the clock time at a particular instant. So, call the clock function just before and after performing ur function. An UNRELATED example using the clock function is given below.

 #include <time.h>
#include <stdlib.h>
#include <stdio.h>

void
main (void)
{

  clock_t start, finish;
  int i;
  long int duration;

  for (i = 100; i <= 120; i++)
    {
      start = clock ();
      while (clock () < (start + i));
      finish = clock ();
      duration = finish - start;
      printf ("expected:%d  actual:%ld\n", i, duration);
    }
} 


This program will give the expected value for the "while" loop and the actual value that the clock() function displays. Run it and see. The expected and the actual values won't be the same.This will prove to you that the Clock() function , or any function for that matter in the time.h library isnt too specfic. So, ur plan of showing the difference in the access times between the two search mechanisms might not yeild the correct answer(given that the difference between the two mechanisms will be too small to percieve and since the clock() function can only give a millisecond precision).

Good Luck.

lol .

Vikram.


Posted by vikram_1982 [send private reply] at April 29, 2002, 05:54:21 AM

For more information on time functions , visit,

http://search.microsoft.com/default.asp?qu=time+functions&boolean=ALL&nq...

Posted by vikram_1982 [send private reply] at April 29, 2002, 05:55:24 AM

Oops, the whole thing is a single URL.

Posted by unknown_lamer [send private reply] at April 29, 2002, 08:22:16 AM

Maybe windows has horrible RTC support because I ran it on the OS X box here at school and got this result:

expected:100 actual:100
expected:101 actual:101
expected:102 actual:102
expected:103 actual:103
expected:104 actual:104
...
(repeat until the loop finishes at 120)

I'll try on my x86 machine at home, but it looks like Windows just sucks with timing. (I'm also running a somewhat heavy load on this machine, so you can't blame it on load).

Posted by vikram_1982 [send private reply] at April 30, 2002, 01:56:00 AM

Maybe Windows is to blame, I dont know. But, it didnt work 4 me.

Posted by Leydeya [send private reply] at April 30, 2002, 03:07:33 AM

i try it at home...i will reply soon if the timer is what i want..anyway thanks vikram_1982..i mail you back if i have problem..unknown_lamer did u receive my mail?

Posted by unknown_lamer [send private reply] at April 30, 2002, 04:54:35 PM

Yes leydeya, I did recieve your mail...I just haven't had time to reply to it yet...I'll try to get to it in a few days but I'm finishing up some final details for a bit of a large presentation that I am giving at the county-wide "learning conference" (OR the lazy kids in independent research get to show that they did _something_ during the year) (unknownlamer.org is back up, so you can see my presentation [draft...and I think it made it into M02] somewhere in the code section)...then I have to take the SAT saturday, followed up by a six hour long LUG meeting sunday (I'm getting an Apple //e there! Oregon Trail, here I come ;-).

Posted by unknown_lamer [send private reply] at April 30, 2002, 05:23:24 PM

I just tested the timing program on my Debian box...it returns 1000 every time. It looks like your timing example is extremely non portable. I watched the values of start and finish, and they both changed during run time, but were always 1000 between each other. Adding values of 100 to 120 to the clocks call does nothing when the return values are in the area of 1000000 or so, so you would need to choose a larger set of values like 10000 to 10200 to see any real impact...except that makes the while take longer and now I get 2000 between entries. So what you really have to do is scrap the whole program because obviously it is non-portable...sorry about the jumbled message, but I was running between two machines while writing this :)

Posted by vikram_1982 [send private reply] at May 01, 2002, 07:08:16 AM

OK. the program goes down the drain. Unfortunately, I only have Windows at home and I do not have the luxury of different OS s to test the portability issue. So sorry.

I'll try to bring out a comprehensive example soon.

lol

Posted by Leydeya [send private reply] at May 01, 2002, 08:46:32 AM

yeah...the codding u had gave vikram..not working properly..any codding?
unknown i know you are too bz so do take your time...good luck unknown_lamer!!its okey vikram_1982..buat if you all have any codding of timer do write to me ok..have you all receive my mail?

Posted by unknown_lamer [send private reply] at May 01, 2002, 02:39:21 PM

Please, use coding now codding! We aren't trying to hit people with cod here.

Posted by Leydeya [send private reply] at May 01, 2002, 09:28:32 PM

sorry unknown_lamer!

Posted by Leydeya [send private reply] at May 01, 2002, 09:31:17 PM

careless mistake...wrong spelling..

Posted by Leydeya [send private reply] at May 03, 2002, 01:06:51 AM

till now, i still confuse..what is the real meaning of hashing? i refer to the data structures book and it say hashing is the process of tranforming a key into an address.The tranformation involves some quickly computable operation on the key,together with a collision handler.BUt my problem is if we are using hashing what we must put in our project either the collision,probe sequences,rehash,chaining,open addressing,clustering..or all that? please help me..

Posted by Psion [send private reply] at May 03, 2002, 09:51:16 AM

Ask your teacher.

Posted by vikram_1982 [send private reply] at May 04, 2002, 08:02:08 AM

Let me try to make this easy for u.

1. We need to find a location in the Memory to place your data.

2. In Hashing techniques we try to find a location in memory to do so.

3. We use a simple algorithm like d = (ac+b) mod m. Here
a is the key,c and b are variables dependent on ur program; m is the memory size that u r working on. The mod is the modulus operator represented by % in high Level Languages.
d is the address that u end up with.

4. It is possible that two different records will give the same hash value ( the d value ) in the same program causing the record to be placed in the same location as another record.This is called colission.

5. We do not need that.

6.This is where collision resolution comes into picture.The various things that u have talked about are types of colission resolution. U can adopt any type of collision resolution as u like. The choice is yours.( I presume u understand the various techniques that u have mentioned )

7.I hope I have made myself clear.

All the best.

Posted by Leydeya [send private reply] at May 06, 2002, 02:06:04 AM

well, i understand now..thank you vikram_1982

Posted by Leydeya [send private reply] at May 09, 2002, 02:08:27 AM

i have new problem here...why the ElementType have error?

/*type declaration for open
addressing hash tables */

#ifndef _HashQuad_H

typedef unsigned int Index;

typedef Index Position;
struct HashTbl;
typedef struct HashTbl *HashTable;

HashTable InitializeTable( int TableSize );
void DestroyTable( HashTable H );
Position Find( ElementType Key, HashTable H );
void Insert( ElementType Key, HashTable H );
ElementType Retrieve( Position P );
HashTable Reshash( HashTable H );
//Routine such as Delete and Make Empty are omitted
#endif
enum KindOfEntry { Legitimate, Empty, Deleted};

struct HashEntry
{
ElementType Element;
enum KindOfEntry Info;
};
typedef struct HashEntry Cell;
//Cell *TheCells will be an array of
//HashEntry Cells, allocated later
struct HashTbl
{
int TableSize;
Cell *TheCells;
};

Posted by CViper [send private reply] at May 09, 2002, 03:45:33 AM

You need to declare / typedef ElementType somewhere... couldn't find it anywhere in your code.

Posted by Leydeya [send private reply] at May 09, 2002, 06:35:55 AM

can anybody show me how?
But the book said that we need to put strcmp and strcpy?
how?

Posted by unknown_lamer [send private reply] at May 09, 2002, 05:06:46 PM

If this is a C++ project, then you should use the basic_string class from the STL (most people just use string, which is a basic_string of char's). Replace all the occurences of ElementType with the name of your student type, or use templates instead (which is what I bet you were trying to do). I did recieve your code by email, but it uses so many Windows specific features there is no way I'll ever be able to compile it. Your code didn't look like it used any C++ only things either.

Posted by Leydeya [send private reply] at May 10, 2002, 01:51:02 AM

oic..that mean u cant help me unknown_lamer?

Posted by Psion [send private reply] at May 10, 2002, 09:01:11 AM

I think it is time for this thread to stop. Please continue correspondence via e-mail with anyone who has agreed to help. Personally, I still think you ought to be talking to your teacher, not trying to get us to basically walk you through your whole assignment.

Posted by unknown_lamer [send private reply] at May 10, 2002, 01:58:21 PM

Agreed. If you are this lost, I don't know if _anyone_ can help you.

Posted by Leydeya [send private reply] at May 11, 2002, 04:16:39 AM

thank you.most of u make a good job.

Posted by gian [send private reply] at May 13, 2002, 01:33:44 AM

Maybe it is time that we introduced per-thread locking.

You must be logged in to post messages and see which you have already read.

Log on
Username:
Password:
Save for later automatic logon

Register as a new user
 
Copyright TPU 2002. See the Credits and About TPU for more information.