Hash tables - open adressing for collision resolution

I have up to 10,000 such data:

Code:

typedef struct
{
	char authors[5][40]; // first and last names of the author
	char title[50]; // title of the publication
	unsigned int year; // year of the publication
	char isbn[15]; // publication code
} PubEntryT;

I have to use a hash table with open adressing for collision resolution to store this data and retrieve them effectively, on the basis of the isbn.

I'm having problems understanding how to store this data.
I can't figure out what is the key of the hash table here?
When does the collision happens?
Give me examples using this data please.

Originally Posted by Delia

I'm having problems understanding how to store this data.
I can't figure out what is the key of the hash table here?

I like it when people answer their own question:

Originally Posted by Delia

I have to use a hash table with open adressing for collision resolution to store this data and retrieve them effectively, on the basis of the isbn.

Collisions will happen when two ISBNs hash to the same thing. How often that happens depends on what you choose for the hash.

Originally Posted by tabstop

I like it when people answer their own question:


Collisions will happen when two ISBNs hash to the same thing. How often that happens depends on what you choose for the hash.

But the isbn is unique for one book, a data can't have two isbns. Or two data, the same isbn.

Or what "hash the same thing/choose for the hash" means?

Originally Posted by Delia

But the isbn is unique for one book, a data can't have two isbns. Or two data, the same isbn.

However, the hashing function may resolve two different isbns to the same location, hence the collision, and the reason for techniques like open addressing to resolve 'em.

Originally Posted by itCbitC

However, the hashing function may resolve two different isbns to the same location, hence the collision, and the reason for techniques like open addressing to resolve 'em.

What can I use as a hash function here?

No disrespect to the poster, but how come so many of the questions raised in these forums indicate that the "C" course being taught mixes algorithms / data structures and C-syntax issues leaving the student hopelessly confused as to which is which?

I mean, things like hashing or linked lists should be properly covered on a white board, or with nice animated illustrations, way before the student is sent out to code. Instead, the student is left to pull out their hair trying to resolve two different areas of knowledge at the same time.

Originally Posted by nonoob

No disrespect to the poster, but how come so many of the questions raised in these forums indicate that the "C" course being taught mixes algorithms / data structures and C-syntax issues leaving the student hopelessly confused as to which is which?

I mean, things like hashing or linked lists should be properly covered on a white board, or with nice animated illustrations, way before the student is sent out to code. Instead, the student is left to pull out their hair trying to resolve two different areas of knowledge at the same time.

You picked a weird thread to post this in, since I see no questions about C syntax here. (I think you're also making the assumption that "passed Programming I/II implies skill at programming", which is not always a valid assumption for various reasons.)

Originally Posted by nonoob

I mean, things like hashing or linked lists should be properly covered on a white board, or with nice animated illustrations, way before the student is sent out to code.

They typically are!
It's just that the students who come here asking about it are the ones who skipped class, didn't pay attention, aren't actually interested in programming, and didn't even want to be in the course to begin with.

Originally Posted by iMalc

They typically are!
It's just that the students who come here asking about it are the ones who skipped class, didn't pay attention, aren't actually interested in programming, and didn't even want to be in the course to begin with.

That's not true... The fact that I ask means that I'm interested. And no, they weren't properly explained at school. I bought 3 books written by my proffesor about Data structures and algorithms, so that I could understand his way of solving this. At the Hash tables area I have only theory, not even one example. I don''t want to complain. I don't need the solving of my program. I was just asking for some help to understand what can be a hash function in my case. It's Easter holiday and I'm in trying to solve this. And you say that i'm not interested?

Maybe this will clarify something for you:

Code:

#include <stdio.h>
#include <string.h>

#define  SIZE 12

int main() {
	char words[5][10] = { "word", "static", "delete", "goto", "continue" };
	int i, j, len, base, key;

	for (i=0;i<5;i++) {
		base = 0;
		len = strlen(words[i]);
// total the ascii value:
		for (j=0;j<len;j++) base += words[i][j];
// the hash:
		key = base%SIZE;
		printf("%s has a key of %d (base was %d)\n", words[i], key, base);
	}

	return 0;
}

Since an isbn number is all numbers, you could calculate "base" differently. But you might as well do it this way if the number is in a string. It doesn't matter; what matters is that the base for calculating the key needs to be a single integer value.

SIZE is the size of the array you will use for the table, so "key" will always be between 0 and SIZE-1. That's the slot in the array you use for that word (or isbn number).

The size of the array is pre-determined and set, but the number of items in the table is not. It could be (generally, will be) more than the number of slots, but that is not the only reason for collisions. The reason I chose 12 here is because it creates a collision between "word" and "static". That means they will be going into the same slot (aka bucket).

There are a few ways to deal with collisions, one of the most common is to make the array an array of pointers to a linked lists. These lists are initially empty. Collisions are not to be avoided, they are an integral aspect of how a hash table works.

It did clarify a lot. Thanks!

Originally Posted by Delia

That's not true...

Glad to hear you are an exception. I was speaking rather generally there.

MK27 has given an example of claculating some kind of hash. WHat is the next most useful thing we can show you?

To be fair, I recall thinking that most hash table "tutorials" I found seemed to have been written on the assumption that you already knew how they worked, which is kind of oxymoronic.

Being short on explanation and long on obfuscation is an unfortunate standard in much programming documentation. If you extended that policy all the way into the academy (not all profs are good profs!), then it doesn't surprise me that the OP needed a basic explanation.

http://en.wikipedia.org/wiki/Plain_Language_Movement
...a very sane concept.

The movement focuses attention on the information needs and the reading abilities of the reader and opposes writer-based prose, which is the tendency to use long sentences, jargon, and a formal style as a way to acquire authority, power, and credibility.