Programming Forums - Hashing In C

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C (http://www.programmingforums.org/forum60.html)

- - Hashing In C (http://www.programmingforums.org/showthread.php?t=14899)

I'm wondering what the best way to hash in C is, without using anyone else's code?

Is it acceptable to use the standard associative containers from C++, and then make the rest of the code C? Or can that end with bad results?

Or is it a better idea to write my own naive implementation in C?

Note: In most scenarios where I need the hash table, the hashing function is quite clear, and could be implemented without a hash table (IE, just a quick key -> array index conversion). However, there are sometimes occassional collisions due to unexpected input, that I need to handle. That's what brings me to this post.

Re: Hashing In C

>I'm wondering what the best way to hash in C is
It depends on the needs of your program. Like sorting there are tons of ways to hash, and they're all valid solutions.

>without using anyone else's code?
Could you be more specific about this requirement?

Re: Hashing In C

It's for a contest, so written code can be brought with us, but only if it's our own. And if it's too long, I can't spend 20+ minutes typing it all out from my notes, so it has to be something compact.

This is the current solution I have. I tried to keep it as compact as possible, but capable of insertion and retrieval.

This current example is meant to be specific to input where the key is "A-Z", but there could often be unexpected input such as "a", or "z", or "az". Therefore, the only reason a hash table is being used instead of an array of 26 elements, is to handle those exceptions. Performance of the buckets is not important, so building a linked list for collisions isn't tragic.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* Input Specifications Begin */
#define MAX_KEY 20
#define HT_WIDTH 26
#define VAL_TYPE int
 
int hash(char *key) {
    int i=0;
    do{i+=*key+13;}while(*++key);
    return i%HT_WIDTH;
}
/* Input Specifications End */
 
/* Hash Table Begin */
int ht_error;
typedef struct ht_me {struct ht_me *next; char key[MAX_KEY]; VAL_TYPE value;} ht_b; 
ht_b *ht_table[HT_WIDTH];
void ht_init() {
    int i;
    for(i=0;i<HT_WIDTH;i++)ht_table[i]=NULL;
}
void ht_insert(char *key, VAL_TYPE value) {
    int i=hash(key);
    ht_b *node;
    node = (ht_b *) malloc(sizeof( ht_b ));
    strcpy(node->key, key);
    node->value = value;
    node->next = ht_table[i];
    ht_table[i] = node;
}
int ht_lookup(char *key) {
    ht_error=0;
    int i=hash(key);
    ht_b *node;
    node = ht_table[i];
    while(node) {
        if(!strcmp(node->key,key))return node->value;
        node=node->next;
    }
    return ht_error=1;
}
void ht_clean_bucket(ht_b *node) {
    if(!node)return;
    ht_clean_bucket(node->next);
    free(node);
}
void ht_kill() {
    int i;
    for(i=0;i<HT_WIDTH;i++) {
        ht_clean_bucket(ht_table[i]);
        ht_table[i]=NULL;
    }
}
/* Hash Table End */
 
int main() {
    int value = 0;
    char key[3]; 
    key[2] = 0;
 
    ht_init();
 
    for(key[0]='A';key[0]<='Z';key[0]++)
        for(key[1]='A';key[1]<='Z';key[1]++)
            ht_insert(key, value++);
 
    value = ht_lookup("ZZ");
    if(!ht_error) printf("%d\n", value);
    else          printf("Key Does Not Exist\n");
 
    ht_kill();
 
    return 0;
}

Re: Hashing In C

if this is for the ccc which allows c or c++ and your problem requires a hashtable, you should just use c++ and take advantage of the stl.

Re: Hashing In C

>you should just use c++ and take advantage of the stl
C++0x hasn't been ratified yet, so any use of hash tables (unordered_list) or anything like it would be risking no support by the compiler.

>but only if it's our own
The problem with hashing is that if you make something up, it's highly likely to suck. That's why most wise programmers use existing algorithms. You can still use the algorithm without using someone else's code, but with the one I'm suggesting it's pretty hard to "personalize" something so simple.

>so it has to be something compact
A good, fast, and small algorithm is Bernstein's hash. It's so short that it's nearly impossible to forget, and it has surprisingly good properties:

unsigned djb_hash ( void *key, int len )
{
  unsigned char *p = key;
  unsigned h = 0;
  int i;
 
  for ( i = 0; i < len; i++ )
    h = 33 * h ^ p[i];
 
  return h;
}

Re: Hashing In C

Well it's almost always in the circumstance where the hash function is known. Such as there are only 26 keys between "A" and "Z" ... thus the hash function is key[0]-'A'.

The point of using the hash table is to handle any unexpected input, such as "a", "z", or "az". That's where the hash table, along with my solution, comes in.

I just need the best way to handle the scenario where the hash function is of small importance, and performance of the buckets is unimportant... whether it be something from the standard library, or a smaller version of the code I posted.

Are associative containers in C++ not usable like Hash Tables, and a part of the standard library?

P.S. I recall reading up on Bernstein's algorithm in an article you wrote, over a year ago. Good stuff. :)

Re: Hashing In C

>I just need the best way to handle the scenario where
>the hash function is of small importance, and
>performance of the buckets is unimportant...
Then any collision resolution strategy will work. All of the basic ones are painfully simple to remember and implement in a short time. Hell, hash tables are one of the few data structures that I can write and get working on the first try.

>Are associative containers in C++ not usable like Hash Tables
They're like hash tables, but may not be implemented as such. std::map, for example, is usually implemented as a red black tree. If one of those classes solves your problem, it'll be a lot easier than writing your own hash table.

Re: Hashing In C

Hmm.

So let's look at this objectively now. This isn't quite the same as the requirements I mentioned in the first post, but I'll go ahead anyways.

Here is an imaginary assignment:

Quote:

An input file, "mode.in", contains an integer on the first line, n, specifying how many lines will follow.

1 <= n <= 500000

Each line will contain an integer, x.

0 <= x <= 10000000

Write a program that will find the most commonly occuring number. Output the number of times it appeared. The program should not concern itself with tied amounts of repetitions.

Example Input:

Example Output:

1

Example Input:

Example Output:

5

Then would this be the "best" solution for C? Is this as short as it can get?

Would you recommend any changes? Could this be easier if I used the STL?

Thanks for all your help.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define HT_WIDTH 500000
unsigned hash(void *key) {
    unsigned i, len, h=0;
    unsigned char *p = key;
    for(i=0,len=sizeof(unsigned); i<len; i++) 
        h = 33 * h^p[i];
    return h%HT_WIDTH;
}
 
typedef struct ht_me {struct ht_me *next; unsigned key; unsigned value;} ht_b; 
ht_b *ht_table[HT_WIDTH]; ht_b *ht_node;
void ht_init() {
    unsigned i;
    for(i=0;i<HT_WIDTH;i++) ht_table[i]=NULL;
}
unsigned ht_increase(unsigned key, unsigned h, int amount) {
    /* Insert a new entry {key:amount}, but if the key already exists, increase it by amount */
    ht_node = ht_table[h];
    while(ht_node) {
        if(ht_node->key==key) return(ht_node->value+=amount);
        ht_node = ht_node->next;
    }
    ht_node = (ht_b *)malloc(sizeof(ht_b));
    ht_node->key = key;
    ht_node->value = amount;
    ht_node->next = ht_table[h];
    ht_table[h] = ht_node;
    return ht_node->value;
}
int ht_clean_bucket(ht_b *node) {
    if(!node)return 0;
    ht_clean_bucket(node->next);
    free(node);
    return 0;
}
int ht_kill() {
    int i;
    for(i=0;i<HT_WIDTH;i++) {
        if (ht_clean_bucket(ht_table[i])) return 1;
        ht_table[i]=NULL;
    }
    return 0;
}
 
int main() {
    unsigned n, x, size, mode=0;
 
    freopen("mode.in", "rt", stdin);
    scanf("%d\n", &n);
 
    ht_init();
    while (n--) {
        scanf("%d\n", &x);
        if (( size = ht_increase(x, hash(&x), 1) )> mode) mode = size;
    }
    printf("%d\n", mode);
 
    return ht_kill();
}

Edit: Uploaded a file of half a million randomly generated integers for performance testing. It's amazing how much a bad hashing function affects the performance. But I feel that an execution time of ~2s, as is, is perfect.

Post Edit: The file upload won't work...

Re: Hashing In C

Quickly done STL version (using your input loop) - untested - you probably would need to fix up the includes

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
 
int main() {
    unsigned n, x, size, mode=0;
 
    freopen("mode.in", "rt", stdin);
    scanf("%d\n", &n);
 
    std::map<int,int> counts;
    while (n--) {
        scanf("%d\n", &x);
        if (( size = ++counts[x]) )> mode) mode = size;
    }
    printf("%d\n", mode);
 
    return 0;
}

Re: Hashing In C

Interesting! That's much, much easier to implement. That could be written in 2 minutes, whereas mine took about 20. I now feel like I'll be wasting so much time on this contest by not using the STL. I'll have to ask the judges what they want to see...

It's interesting to note that mine is about 200% faster on the file with half a million integers. I guess that's because the stl map isn't a hash table. And your code worked, but you had a mismatched bracket before the greater than sign.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
 
int main() {
    unsigned n, x, size, mode=0;
 
    freopen("mode.in", "rt", stdin);
    scanf("%d\n", &n);
 
    std::map<int,int> counts;
    while (n--) {
        scanf("%d\n", &x);
        if (( size = ++counts[x]) > mode) mode = size;
    }
    printf("%d\n", mode);
 
    return 0;
}