10 replies to this topic

[coolgirl]

Code a hash function, which computes the index number based on the MMU ID, which is
a 10-digit key. The hashing algorithm used to compute the hash index is given as follows:
• Partition the 10-digit key (yyyyyzzzzz) into two 5-digit numbers: yyyyy and
zzzzz.
• Add the two partitioned numbers, yyyyy and zzzzz.
• Truncate the addition result, and keep only the last three digits.
Use the function header given below. The function will accept an unsigned integer, ID
which stores the MMU ID, compute accordingly and return the computed hash index.
int hashfunc(unsigned int ID);
What is your MMU ID? ______________________
What is the hash index based on your MMU ID? ______________________

plz help me to solve this.....

[WingedPanther]

What do you have so far?

[coolgirl]

I have try to do it.Here is my code:

int hashfunc(unsigned int ID){

float x=ID/100000;
int a=strtok(x,".");
int b=strtok(x,"\n");

int c =a+b;
float d=c/1000;
int e=strtok(d,"\n");

return e;
}

Is this code correct????plz help me...

[MeTh0Dz]

I'm bored so I coded you a solution, but first a note. It appears that your assignment calls for the ID to be passed as an unsigned int, this however is a problem as the standard does not guarantee that an unsigned int will be able to represent all 10 digit numbers. Therefore I use the preprocessor to handle cases when an unsigned int is going to be too small.

Read through this code and hopefully you can learn something from it.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdbool.h>

#define TEN_MAX 9999999999
#define ID_LENGTH 10

#if (UINT_MAX >= TEN_MAX)
	int hash_algo(unsigned int id);
#else
	int hash_algo(unsigned long long id);
#endif
	size_t pad_number(char* in, char* out, int min);
	
	int main(int argc, char** argv)
	{
		unsigned long long tests[] = {9184567298, 8721756181, 9819809, 2837473718, 9878657654, 898, 8292000000, 0};
		for (unsigned long long* p = tests; *p; p++)
			printf("ID: %.10llu\t\t\tRESULT: %.3d\n", *p, hash_algo(*p));
		return 0;
	}
	
	/*
	**	Passing an ID of length greater than 10 will result in undefined behavior
	**	Returns a negative number in case of error
	*/
#if (UINT_MAX >= TEN_MAX)
	int hash_algo(unsigned int id)
#else
	int hash_algo(unsigned long long id)
#endif
	{
		char temp[11], new_temp[11], half_1[6], half_2[6];
		int total;
#if (UINT_MAX >= TEN_MAX)
		if (sprintf(temp, "%u", id) > 0) {
#else
		if (sprintf(temp, "%llu", id) > 0) {
#endif
			pad_number(temp, new_temp, ID_LENGTH);
			if (sprintf(half_1, "%.5s", new_temp) > 0) {
				if (sprintf(half_2, "%s", &(new_temp[5])) > 0) {
					total = atoi(half_1) + atoi(half_2);
					return total % 1000;
				}
			}
		}
		return -1;
	}
	
	/*
	** In order to safely use this function you must pass an 'out' variable of size atleast sizeof(char) * min
	** If variables 'in' and 'out' overlap results from this function are undefined
	** Returns the length of the 'out' variable
	*/
	size_t pad_number(char* in, char* out, int min)
	{
		size_t len = strlen(in);
		memset(out, 0, min);
		for (int i = 0; i < (min - len); i++) out[i] = '0';
		strcat(out, in);
		return strlen(out);
	}

[e] Keep in mind that this is an _extremely_ poor hashing algorithm and doing some quick math it looks like only ~1% of numbers are going to not be involved in collisions.

[draggard]

this program works in Dev..is this C code ? btw, why does it need the '#' infront of if,else and endif ? thanx..i m just a beginner in learning coding

[WingedPanther]

Those are compiler directives.

[draggard]

ohh..thanx..but can i consider that code as C code ? coz in C code, we nvr learn about da #if, #endif

[WingedPanther]

It is part of C. He is using a fairly advanced method, and is making sure it is cross-platform/cross-compiler safe.

[Firebird_38]

 
int hashfunc(unsigned int ID);
{
 return ( (ID / 100000) + (ID % 100000) ) % 1000;
}

I think that's all there's to it.

(ID / 100000) is integer division, leaving you with the high part
(ID % 100000) is modulus, or remainder from division, the low part

add it up, and return the remainder of a division by 1000, returning 0 - 999.

Ps, This is a lousy hash function, but that's not your fault. It has a bad "distribution".

[omega]

*****************

Edited by omega, 20 April 2010 - 12:38 PM.

[Firebird_38]

We do not want float anything, just int, int, int. So, uncorrect me please. Because you're wrong.

and % isn't the quotient, it's the modulus, the remainter-after-division, and when ID is 777000 then id % 100000 = 77000

So go learn what a remainder is.

Nice caps, by the way.

Anyway, I did explain how it works already, now, instead of telling me I'm wrong, give it a whirl yourself and see that I'm not actually wrong. Then you can save yourself the embaressment of saying the "computer doesn't know I want a FLOAT" division, because I don't.

Ps... The computer doesn't know anything.

Pps. x % y=x-x/y*y when thinking about this, please keep operator precedence in mind, and that x and y are ints.