Hashing Problem

[fusi0n423]

I have a project where I have to analyze 3 different hashing functions. I cannot get the cyclic shift hash to work with a bitwise OR. Everything looks fine to me am I doing something wrong?

int Hash::hash(string key) {
	unsigned int h = 0;
	for(int i =0; i < key.length(); i++) {
		h = (h << 5) | (h >> 27);
		h += static_cast<unsigned int>(key[i]);
	}
	return (static_cast<int>(h) % NUM_BUCKETS);
}

I get

Unhandled exception at 0x7082212e (msvcp90d.dll) in CS400_HW3.exe: 0xC0000005: Access violation reading location 0xcccccce4.

at line 4. I'm using M$ Visual Studio 2008 pro.

[nucleon]

There does not seem to be anything wrong with your code. In particular, I see nothing that can cause an exception in what you've posted.

[fusi0n423]

Is it maybe my member? I steped through it instead of looking where the cursor was this time and its stopping at the if statement. It works fine with a sum of characters and ELF hash. This is code my prof gave us, maybe I copied it wrong.

bool Hash::member (string key) {
	cell *current;
	current = dictionary[hash(key)]; // hash(key) = bucket num
	while(current != NULL)
		if(current->lname == key)
			return(true);
		else
			current = current->next;
	return false;
}

[nucleon]

This code also looks okay, although it is definitely a place where an exception can occur. The error must be in how you've added members to "dictionary". Is it properly initialized to NULLs? When adding members, are you setting "next" to NULL. Etc, etc, ....

[fusi0n423]

Here's my insert function:

void Hash::insert(string key) {
	int bucket;
	cell *oldheader;
	if(!member(key)) {
		bucket = hash(key);
		oldheader = dictionary[bucket];
		dictionary[bucket] = new cell;
		dictionary[bucket]->lname = key;
		dictionary[bucket]->next= oldheader;
	}
}

Every member in the dictionary array is set to NULL when initializing the Hash. so the first insert will will make the last element in the bucket have a NULL pointer for next. Other than that It will get whatever was there already and be the new starting point.

[nucleon]

Everything still looks fine. You'll have to attach your entire code.

[nucleon]

Hold that code! I put together the pieces you've posted so far and was able to generate an error with this: Hash h; h.insert("KSADLOP 033983h"); The error does seem to be in the hash function. In fact, it seems to be with this line since commenting it out causes the program to work: h = (h << 5) | (h >> 27); Does commenting it out cause your program to work?
Strangely, changing it to this works: h = (h >> 5) | (h << 27); This is a strange one. I'll keep thinking.

[nucleon]

Solved it! (About two seconds after my last post.)
The problem is in this line: return (static_cast<int>(h) % NUM_BUCKETS); You must remove the cast to int, since that may give you a negative number and therefore the mod will return a negative number, giving you an array subscripting error.

[fusi0n423]

Solved it! (About two seconds after my last post.)
The problem is in this line: return (static_cast<int>(h) % NUM_BUCKETS); You must remove the cast to int, since that may give you a negative number and therefore the mod will return a negative number, giving you an array subscripting error.

Thanks I would never would have figured that one out. I changed it to return (static_cast<unsigned int>(h) % NUM_BUCKETS); and it works fine now.

[nucleon]

No problem. It's noteworthy that this bug involved casting. Remember to cast only when absolutely necessary since subverting the type system can be dangerous. In this situation, if you declare NUM_BUCKETS as an unsigned and return an unsigned, there's no need for a cast at all.