K&R hash table question.

[b4283]

Hi,

I've encountered some confusing questions while reading k&r ed2.

Around page 128, in the book, has introduced an "hash-search
algorithm", while they uses hash(s) which is the hashed number of an
string, as the array index, this had raised my question: doesn't array
indexes have to start from 0 to (i-1), but random assigning index is
possible in the book?

and I also tried to practice this with a simple struct, but i always
get a segmentation fault running it.

the 2nd question is that it seems that the "next" pointer points to
itself in the array, this doesn't make any sense does it ?

 

[Giacomo Degli Esposti]

algorithm", while they uses hash(s) which is the hashed number of an
string, as the array index, this had raised my question: doesn't array
indexes have to start from 0 to (i-1), but random assigning index is
possible in the book?

Hello.

I haven't a copy of the book to check at the moment, but this seems
quite unlikely that k&r contains such an error.

I see two possibilities: maybe the hash function returns a value that
is
always in the interval 0..N-1 where N is the numebr of elements of
the array.
The other possibility is that a mod N is applied so that the
resulting number is between 0 and N-1

and I also tried to practice this with a simple struct, but i always
get a segmentation fault running it.

Show us the actual code you are using, if not too long of course!


ciao
Giacomo

 

[osmium]

I've encountered some confusing questions while reading k&r ed2.

Around page 128, in the book, has introduced an "hash-search
algorithm", while they uses hash(s) which is the hashed number of an
string, as the array index, this had raised my question: doesn't array
indexes have to start from 0 to (i-1), but random assigning index is
possible in the book?

and I also tried to practice this with a simple struct, but i always
get a segmentation fault running it.

How about page 144? Note the modulo operator in the returned value. That
reduces the value to the range of the array.

Segmentation faults result from running code, post the code.

 

[Ioannis Vranos]

Not having to do with the particular code in K&R2 (I didn't check the book),
but as an answer to the previous two replies, we can use negative indexing
for elements in an array.



An example:


int main(void)
{
int array[100]= {};


int *p= array+ 50;


/* Sets array[30] to 4. */
p[-20]= 4;


return 0;
}



--
Ioannis Vranos

C95 / C++03 Software Developer

http://www.cpp-software.net

 

[Chad]

Hi,

I've encountered some confusing questions while reading k&r ed2.

Around page 128, in the book, has introduced an "hash-search
algorithm", while they uses hash(s) which is the hashed number of an
string, as the array index, this had raised my question: doesn't array
indexes have to start from 0 to (i-1), but random assigning index is
possible in the book?

and I also tried to practice this with a simple struct, but i always
get a segmentation fault running it.

the 2nd question is that it seems that the "next" pointer points to
itself in the array, this doesn't make any sense does it ?

Do you mean the following lines code...

np->next = hashtab[hashval];
hashtab[hashval] = np;

If so, I believe the reason this is done because they are inserting a
node at the head of a linked list.

 

[b4283]

np->next = hashtab[hashval];
hashtab[hashval] = np;

If so, I believe the reason this is done because they are inserting a
node at the head of a linked list.

thanks for the interpretation !
now I understand, it's about when collision happens that two strings
have the same hash value.

 

[b4283]

How about page 144?  Note the modulo operator in the returned value.  That
reduces the value to the range of the array.

Segmentation faults result from running code, post the code.

My code was nothing, i used a rand() to assign random numbers for
array indexes to store an struct pointer.
After careful reading it again, I found that I missed the last line of
the hash() function, which

return hash % HASHVAL;

controls the hash to be a non-negative integer within the array range.

that's all for my question, thanks all for reply !