Programming Forums > Application Development > C

Sane · Jan 8th, 2008, 6:04 PM

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.

Narue · Jan 8th, 2008, 8:51 PM

>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?

Sane · Jan 8th, 2008, 9:28 PM

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.

 C Syntax (Toggle Plain Text) 
#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;
}
#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;
}

mbd · Jan 8th, 2008, 10:35 PM

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.

Narue · Jan 9th, 2008, 8:24 AM

>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:

 c Syntax (Toggle Plain Text) 
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;
}
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;
}

Sane · Jan 9th, 2008, 11:05 AM

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.

Narue · Jan 9th, 2008, 11:16 AM

>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.

Sane · Jan 9th, 2008, 6:09 PM

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:

(Toggle Plain Text)

Example Output:

(Toggle Plain Text)

Example Input:

(Toggle Plain Text)

Example Output:

(Toggle Plain Text)

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.

 C Syntax (Toggle Plain Text) 
#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();
}
#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...

The Dark · Jan 9th, 2008, 6:51 PM

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

 c++ Syntax (Toggle Plain Text) 
#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;
}
#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;
}

Sane · Jan 9th, 2008, 7:01 PM

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.

 Cpp Syntax (Toggle Plain Text) 
#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;
}
#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;
}

Jan 8th, 2008, 6:04 PM	#1
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 2,032 Rep Power: 6	Hashing In C 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.

Jan 8th, 2008, 8:51 PM	#2
Narue Professional Programmer Join Date: Sep 2005 Posts: 419 Rep Power: 4	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? __________________ Even if the voices aren't real, they have some pretty good ideas.

Jan 8th, 2008, 9:28 PM	#3
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 2,032 Rep Power: 6	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. C Syntax (Toggle Plain Text) #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; } #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; } Last edited by Sane; Jan 8th, 2008 at 9:40 PM.*

Jan 8th, 2008, 10:35 PM	#4
mbd Programmer Join Date: Nov 2007 Posts: 86 Rep Power: 1	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.

Jan 9th, 2008, 8:24 AM	#5
Narue Professional Programmer Join Date: Sep 2005 Posts: 419 Rep Power: 4	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: c Syntax (Toggle Plain Text) 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; } 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; } __________________ Even if the voices aren't real, they have some pretty good ideas.

Jan 9th, 2008, 11:05 AM	#6
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 2,032 Rep Power: 6	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.

Jan 9th, 2008, 11:16 AM	#7
Narue Professional Programmer Join Date: Sep 2005 Posts: 419 Rep Power: 4	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. __________________ Even if the voices aren't real, they have some pretty good ideas.

Jan 9th, 2008, 6:51 PM	#9
The Dark Expert Programmer Join Date: Jun 2005 Posts: 881 Rep Power: 4	Re: Hashing In C Quickly done STL version (using your input loop) - untested - you probably would need to fix up the includes c++ Syntax (Toggle Plain Text) #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; } #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; }

Jan 9th, 2008, 7:01 PM	#10
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 2,032 Rep Power: 6	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. Cpp Syntax (Toggle Plain Text) #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; } #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; }

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Custom Hashing Algorithms	Sane	C	21	Oct 16th, 2006 10:05 PM
MD5 hashing...	Un4given	C++	3	May 31st, 2005 7:51 PM
Hashing Collashing	mtanti	Coder's Corner Lounge	0	Apr 10th, 2005 12:29 PM

Programming Forums > Application Development > C

Hashing In C