Re: Hash table implementation.

From	"Scott Fluhrer" <sfluhrer@ix.netcom.com>
Newsgroups	comp.lang.c
References	<0c914904-6a93-4354-94a2-2bbeb6a53ddb@a17g2000yqk.googlegroups.com>
Subject	Re: Hash table implementation.
Message-ID	<1313100903.379884@rcdn-nntpcache-3> (permalink)
Organization	cisco.com
Date	2011-08-11 18:14 -0400

Show all headers | View raw

More comments...

<lolzy@live.nl> wrote in message 
news:0c914904-6a93-4354-94a2-2bbeb6a53ddb@a17g2000yqk.googlegroups.com...
> Hello comp.lang.c,
>
> This is a hash table implementation I wrote, please comment. Thanks in
> advance.
>
>
> # START CODE
>
>
> /*
> * Print error and quit.
> */
> void hash_table_fatal_error(int t, char *el)
> {
> switch (t)
> {
> case 0:
> printf("ERROR: Could not delete element '%s' from hash table.\n",
> el);

In case this is used in a utility which produces output which is used in a 
pipeline, you might want to make this:
fprintf( stderr, "Error message\n" );

> break;
> case 1:
> printf("ERROR: Could not find key '%s' in hash table.\n", el);
> break;
> }
>
>
> exit(0);
> }
>
>
>
> /*
> * Create a hash table with size 'size' and return a hash table array.
> */
> hash_table ** hash_table_create_table(int size)

What's the point in having the caller specify a hash table size, given that 
your hash function always returns values between 0 and 99?  If the caller 
specifies a value less that 100, you have a potential array overwrite when 
you add an element; if the caller specifies a value greater than 100, that's 
just wasted space.

> {
> register int i = 0;
> hash_table **x;
>
>
> x = (hash_table **) calloc(size, sizeof(hash_table *));
>
> for (; i <= size; ++i)

Array overflow!  You want:
   for (; i < size; ++i)

> {
> x[i] = (hash_table *) calloc(1, sizeof(hash_table));
> }

I see you have the convention that you represent an empty list with a dummy 
element.  While this is neither unethical nor immoral, it is a bit 
fattening, as it makes your search/insert/delete code more complex than it 
needs to be.  Why not represent an empty list with a NULL?

>
> return x;
> }
>
>
>
> /*
> * Returns a specified hash table element from table 't' with key 's',
> * or NULL on failure.
> */
> hash_table * hash_table_get_string_from_table(hash_table **t, char *s)
> {
> int id = hash_table_hash(s);
> hash_table *q;
>
> if (t[id]->data.uid != NULL && strcmp(t[id]->data.uid, s) != 0)
> {
> if (t[id]->x != NULL)
> {
> /* Move trough linked list */
> for (q = t[id]->x; ; q = q->x)
> {
> if (strcmp(q->data.uid, s) == 0)
> {
> /* Found */
> return q;
> }
>
>
> if (q->x == NULL)
> {
> break;
> }
> }
> }
>
> return NULL;
> }
>
> return (t[id]->data.uid == NULL ? NULL : t[id]);
> }

Sigh, this is rather more complex that it really needs to be:

    for (q = t[hash_table_hash(s)]; q; q = q->link) {
        if (q->data.uid && 0 == strcmp( q->data.uid, s ))
            return s;
    }
    return NULL;

The insert/remove functions can also be simplified a good bit.

>
>
>
> /*
> * Add 'data' to table 't' with key 'uid'.
> */
> void hash_table_add_element(hash_table **t, char *uid, char *data)
> {
> int hash = hash_table_hash(uid);
> hash_table *q = (hash_table *) calloc(1, sizeof(hash_table));
> hash_table *c;
>
> q->data.uid = strdup(uid);
> q->data.d = strdup(data);
> q->x = NULL;
>
>
> c = t[hash];
>
>
> if (c->data.uid != NULL)
> {
> while (c->x != NULL)
> {
> c = c->x;
> }
>
> c->x = q;
> }
> else
> {
> t[hash]->data.uid = strdup(uid);
> t[hash]->data.d = strdup(data);
Don't you leak the q element (and the strings it points to) here?

> }
> }
>
>
>
> /*
> * Delete element identified by 'uid' from hash table 't'.
> * Returns: 1 on success, 0 on failure.
> */
> int hash_table_delete_element(hash_table **t, char *uid)
> {
> int id = hash_table_hash(uid);
> hash_table *q;
>
>
> if (t[id]->data.uid == NULL)
> {
> return 0;
> }
>
>
> if (t[id]->data.uid != NULL && strcmp(t[id]->data.uid, uid) != 0)
> {
> /* Move trough linked list */
> for (q = t[id]; ; q = q->x)
> {
> if (strcmp(q->x->data.uid, uid) == 0)
> {
> if (q->x->x != NULL)
> {
> free(q->x);
> q->x = q->x->x;
> }
> else
> {
> free(q->x);
> q->x = NULL;
> }
>
> return 1;
> }
>
>
> if (q->x == NULL)
> {
> break;
> }
> }
>
> return 0;
> }
>
>
> if (t[id]->x == NULL)
> {
> t[id]->data.uid = NULL;
> }
> else
> {
> t[id]->data.uid = t[id]->x->data.uid;
> t[id]->data.d = t[id]->x->data.d;
> t[id]->x = t[id]->x->x;
> }
>
> return 1;
> }
>
>
>
>
> /***** NOT UNDER MY COPYRIGHT *****/
> /*
> * UNIX ELF hash.
> * Published hash algorithm used in the UNIX ELF format for object
> files.
> */
> int hash_table_hash(char *data)

This hash function has the property that the lower 2 bits of the result will 
always be the lower 2 bits of the last character of the string being hashed. 
Because the hash table is depending on the hashes to be well distributed 
(even if the strings might not be uniformly random), this is less than 
desirable.

Also, more generally, if this hash function were for general use as a 
utility, it's probably desirable for the user to be able to specify his own 
hash function.  The best that a generic hash function can do is act 
randomly; if the user knows about nonrandomness in his strings being hashed, 
he can often exploit that to create a hash function that actually works 
(generates a more uniform distribution) better than random (!).


> {
> int h = 0, g;
>
> while (*data)
> {
> h = (h << 4) + *data++;
>
> if (g = h & 0xF0000000)
> {
> h ^= g >> 24;
> }
>
> h &= ~g;
> }
>
> return h % HASH_TABLE_SIZE;
> }

>
> # END CODE

Thread

Hash table implementation. lolzy@live.nl - 2011-08-11 10:43 -0700
  Re: Hash table implementation. China Blue Tip Wrench <chine.bleu@yahoo.com> - 2011-08-11 11:25 -0700
  Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-11 11:49 -0700
    Re: Hash table implementation. Ralf Damaschke <rwspam@gmx.de> - 2011-08-11 20:02 +0000
  Re: Hash table implementation. Ike Naar <ike@sverige.freeshell.org> - 2011-08-11 22:02 +0000
  Re: Hash table implementation. "Scott Fluhrer" <sfluhrer@ix.netcom.com> - 2011-08-11 18:14 -0400
    Re: Hash table implementation. lolzy@live.nl - 2011-08-11 23:55 -0700
      Re: Hash table implementation. lolzy@live.nl - 2011-08-12 01:38 -0700
      Re: Hash table implementation. Nobody <nobody@nowhere.com> - 2011-08-12 09:47 +0100
        Re: Hash table implementation. tom st denis <tom@iahu.ca> - 2011-08-12 06:15 -0700
          Re: Hash table implementation. James Kuyper <jameskuyper@verizon.net> - 2011-08-12 11:34 -0400
            Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-12 08:50 -0700
              Re: Hash table implementation. James Kuyper <jameskuyper@verizon.net> - 2011-08-12 12:24 -0400
          Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-12 08:38 -0700
            Re: Hash table implementation. tom st denis <tom@iahu.ca> - 2011-08-12 10:17 -0700
              Re: Hash table implementation. James Kuyper <jameskuyper@verizon.net> - 2011-08-12 13:54 -0400
                Re: Hash table implementation. tom st denis <tom@iahu.ca> - 2011-08-12 11:30 -0700
                Re: Hash table implementation. Seebs <usenet-nospam@seebs.net> - 2011-08-12 20:39 +0000
                Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-12 14:08 -0700
            Re: Hash table implementation. gordonb.4sxmx@burditt.org (Gordon Burditt) - 2011-08-12 20:04 -0500
              Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-12 18:40 -0700
                Re: Hash table implementation. Harald van Dĳk <truedfx@gmail.com> - 2011-08-13 12:59 -0700
              Re: Hash table implementation. Seebs <usenet-nospam@seebs.net> - 2011-08-13 02:34 +0000
      Re: Hash table implementation. Ike Naar <ike@iceland.freeshell.org> - 2011-08-12 11:13 +0000
      Re: Hash table implementation. Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-08-12 07:24 -0400
      Re: Hash table implementation. Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-08-12 09:27 -0600
      Re: Hash table implementation. Seebs <usenet-nospam@seebs.net> - 2011-08-12 18:37 +0000
      Re: Hash table implementation. Jens Gustedt <Jens.Gustedt@loria.fr> - 2011-08-13 00:08 +0200
        Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-12 15:26 -0700
          Re: Hash table implementation. Jens Gustedt <Jens.Gustedt@loria.fr> - 2011-08-13 15:11 +0200
            Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-13 11:38 -0700
              Re: Hash table implementation. Jens Gustedt <Jens.Gustedt@loria.fr> - 2011-08-13 21:03 +0200
        Re: Hash table implementation. "Herbert Rosenau" <os2guy@pc-rosenau.de> - 2011-08-19 08:17 +0000
          Re: Hash table implementation. Jens Gustedt <jens.gustedt@loria.fr> - 2011-08-19 13:29 +0200
          Re: Hash table implementation. Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-08-19 14:35 +0300
  Re: Hash table implementation. Michael Angelo Ravera <maravera@prodigy.net> - 2011-08-12 02:54 -0700
  Re: Hash table implementation. Rui Maciel <rui.maciel@gmail.com> - 2011-08-13 23:11 +0100
    Re: Hash table implementation. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-08-14 00:56 +0100
      Re: Hash table implementation. lolzy@live.nl - 2011-08-14 00:11 -0700
        Re: Hash table implementation. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-08-14 11:57 +0100

csiph-web