Velocity Reviews > hash table

# hash table

Peter Nilsson
Guest
Posts: n/a

 01-03-2004
"al" <(E-Mail Removed)> wrote in message
news:R1mJb.584231\$(E-Mail Removed)...
> Here's what I am trying to write a simple hash table:
>
> struct Employee
> {
> char name[30];
> int id;
> char department[10];
> float salary;
> };
>
> struct Employee *hash_array[MAX_SIZE];
> hash_array[n] = (struct Employee*)malloc(sizeof(Employee));
> strcpy(*hash_array[n].name, "John Smith");
> *hash_array[n].id = 1234;
> *hash_array[n].department = "Marketing";
> *hash_array[n].salary = 4000;
> ...
>
> hash_array will contain all the pointers pointing to each object of
> Employee type.
>
> My questions are:
>
> How to determine MAX_SIZE above?
> How to calculate index, n, to locate an appropriate array item? I read
> somewhere prime number can be used for such purpose(build a hash
> function).
> Could you show me how this work?

Google for hashing techniques. It's a non-trivial subject and largely
outside the domain of clc since it is not ISO C specific.

with is "How do get this to compile!"

The . operator has a higher precedence than unary *, so an expression
like...

*hash_array[n].id

....is parsed as...

*(hash_array[n].id)

But hash_array[n] is not a struct, it's a pointer to struct so the '.id'
part should cause your compiler to question your code. What you want is...

hash_array[n]->id

Also, you're code...

strcpy(*hash_array[n].name, "John Smith");

....even after adding the above correction, attempts to copy data through an
uninitialised pointer 'name'.

Note that C is not C++ (don't use a C++ compiler to compile C; at least, not
when you don't know what you're doing). Declaring a struct tag will not make
that tag a stand alone type name. You're sizeof(Employee) is invalid without
an
appropriate typedef (say)...

typedef struct Employee Employee;

That said, you would do better in general by writing your malloc in the
form...

hash_array[n] = malloc(sizeof *hash_array[n]);

So, search elsewhere for hashing methods then, if you have trouble coding a

--
Peter

Chris Torek
Guest
Posts: n/a

 01-03-2004
In article <(E-Mail Removed)>
Peter Pichler <(E-Mail Removed)> writes:
>I forgot to mention that in the newer version of the standard, C99, implicit
>int was made obsolete, so lack of prototypes requires diagnostics. Just FYI.

Slight correction: it is the lack of a declaration that requires
a diagnostic -- but you can still declare functions without giving
prototypes for them.

The following illustrates this by example:

int f1(); /* declares f1(), but does not provide a prototype */
int f2(void); /* declares f2() and provides a prototype */

void f3(x, y, z) double x, y, z; { /* defines f3(), no prototype */
...
}
void f4(double x, double y, double z) { /* defines f3, gives prototype */
...
}

If you study the Standard, you will find that every function
definition is a declaration, and every prototype is a declaration,
but not every declaration is a prototype. The "old-style", "K&R-1"
function declarations and definitions are the ones that fail to
provide prototypes.

Curiously, while a K&R-1 style function definition defines a
function whose prototype is trivial for any C compiler to calculate
at that point, the Standard does not require compilers to do this.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
Reading email is like searching for food in the garbage, thanks to spammers.

Ben Pfaff
Guest
Posts: n/a

 01-03-2004
"Peter Pichler" <(E-Mail Removed)> writes:

> I forgot to mention that in the newer version of the standard, C99, implicit
> int was made obsolete, so lack of prototypes requires diagnostics. Just FYI.

The C99 foreword contains a laundry list of differences from C89.
One of the items in the list simply says "remove implicit int".
I've now seen several misinterpretations of what this means.

Here's what it really means: in C99, every declaration must
include a type-specifier, such as `char', `short', `int', `long',
`signed', or `unsigned'. That means that each declaration on the
left below is no longer allowed, and must be replaced by the
corresponding declaration on the right:

valid in C89 only valid in C89, C99
----------------- -----------------
const w; const int w;
static x; static int x;
typedef y; typedef int y;
extern z[]; extern int z[];
foo () {} int foo () {}
static bar () {} static int bar () {}

This change is an intentional consequence of a pair of fairly
minor changes from C89 to C99:

1. C89 contained the following language in section 6.5.2
"Type specifiers":

Each list of type specifiers shall be one of the
following sets (delimited by commas, when there is
more than one set on a line); the type specifiers may
occur in any order, possibly intermixed with the other
declaration specifiers.

...
- int, signed, signed int, or no type specifiers
...

C99 added the following sentence at the top of the
paragraph, which is now in section 6.7.2:

At least one type specifier shall be given in the
declaration specifiers in each declaration...

C99 also removed the choice `no type specifiers' from the
list of aliases for int.

2. C89 sections 6.7.1 "Function definitions" makes
declaration-specifiers optional in function-definition.
In C99, now in section 6.9.1, declaration-specifiers are
mandatory.

Now for what removal of "implicit int" does not mean:

* All of the following are valid declarations in both C89 and
C99, because all of them include a type-specifier. This is
admittedly confusing because the keyword `int' is indeed
implied in these declarations. It would be more accurate
to say that C99 removes "implicit type-specifier", not
"implicit int", but for whatever reason, the committee
didn't choose that wording.

short w;
long x;
signed y;
unsigned z;

* The following have always been invalid declarations:

x;
foo ();

The problem is that neither one of these includes any
declaration-specifier, whereas at least one is mandatory.
Three classes of syntax can be declaration-specifiers: a
(`const', `volatile', and in C99 `restrict'), or a
storage-class-specifier (`typedef', `extern', `static',
`auto', `register'). Adding any of these to either of
these declarations will make it valid.

(If these constructions could be accepted as declarations,
then declarations would be ambiguous with statements at
block scope.)

Notwithstanding this, the following was valid in C89,
though it is no longer in C99:

foo () {}

The reason is that function definitions are subject to
syntax rules separate and somewhat different from other
declarations; see #2 above.

* In C89, undeclared functions could be called, with the
compiler assuming that the function returned `int'. In
C99, this is no longer true, but it is a separate change,
described in the foreword as "remove implicit function
declaration". So this is not, strictly speaking, removal
of "implicit int" either.
--
Go not to Usenet for counsel, for they will say both no and yes.

Peter Pichler
Guest
Posts: n/a

 01-03-2004
"Chris Torek" <(E-Mail Removed)> wrote:
> Peter Pichler <(E-Mail Removed)> writes:
> >I forgot to mention that in the newer version of the standard, C99,

implicit
> >int was made obsolete, so lack of prototypes requires diagnostics. Just

FYI.
>
> Slight correction: it is the lack of a declaration that requires
> a diagnostic -- but you can still declare functions without giving
> prototypes for them.

Doh! Thanks for pointing that out. The same to Ben, who gave a very
exhaustive explanation with a long list of examples. I blame the late night
hour

Barry Schwarz
Guest
Posts: n/a

 01-03-2004
On Fri, 02 Jan 2004 22:13:05 GMT, "al" <(E-Mail Removed)> wrote:

>Here's what I am trying to write a simple hash table:
>
>struct Employee
>{
> char name[30];
> int id;
> char department[10];
> float salary;
>};
>
>struct Employee *hash_array[MAX_SIZE];
>
>hash_array[n] = (struct Employee*)malloc(sizeof(Employee));
>strcpy(*hash_array[n].name, "John Smith");
>*hash_array[n].id = 1234;

The . operator has higher precedence than the * operator so this means
the same as *(hash_array[n].id) when what you want is (*hash[n]).id
which is accomplished with the -> operator as in
hash_array[n]->id = 1234;

>*hash_array[n].department = "Marketing";

department is an array. You cannot assign a string literal to an
array with =. You need to copy the data to the array as you did for
name.

>*hash_array[n].salary = 4000;
>...
>
>hash_array will contain all the pointers pointing to each object of Employee
>type.
>
>My questions are:
>
>How to determine MAX_SIZE above?
>How to calculate index, n, to locate an appropriate array item? I read
>somewhere prime number can be used for such purpose(build a hash function).
>Could you show me how this work?
>
>Thanks!
>
>

<<Remove the del for email>>