Geek asks and answers

Hashing array indices

In my C program, I have four 8-bit (char) variables allocated in the structure. If I want to hash these numbers in order to create keys (representing whole structures) that will index the array, how can I do this? (There are many such structures in the program, since I often have to search in the symbol table to see if they exist, if I do not want to create others, I did not know which hash algorithm to use if I'd like to perform a keyword search) .

I thought of some kind of hashing that takes four numbers, turns them into hexadecimal numbers, puts them in sequence, and then converts a number that goes to a decimal number.

But I need something less "heavy" ... this method seems too vain, and I think it is not suitable for creating array indices.

It? Is there any other hash function that also takes up less memory than 32 bits if possible?

+3
source share
4 answers

You can see this list of hash functions .

To implement a hash table (which, in your opinion, I suppose) you need a hash function with an avalanche effect to avoid too many hash collisions for similar input values.

, , , , (, 256 4). 32- ? , hash%tablesize ?

- (, md5, sha-1). - (, Pearson/Jenkins hash).

/* jenkins hash, copied from http://en.wikipedia.org/wiki/Jenkins_hash_function */
uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
  uint32_t hash, i;
  for(hash = i = 0; i < len; ++i)
  {
    hash += key[i];
    hash += (hash << 10);
    hash ^= (hash >> 6);
  }
  hash += (hash << 3);
  hash ^= (hash >> 11);
  hash += (hash << 15);
  return hash;
}

: -, , - . , , ( ) 1, - .

+2

( , ) 4 char 32- , mod, - (, ):

unsigned int combined = (c1 << 24 ) | (c2 << 16 ) | (c3 << 8 ) | (c4);
unsigned int hashval = combined % hashtablesize;

, 4 , . - , , .

+2

?

#include <stdio.h>

typedef struct {
  char a,b,c,d;
} item;
item items[20];

int main(int argc, char *argv[])
{
  items[0].a = 4;
  items[0].b = 6;
  items[0].c = 1;
  items[0].d = 3;
  // ...
  items[4].a = 12;
  // ...
  printf("%d %d %d %d\n", items[0].a, items[0].b, items[0].c, items[0].d);
  return 0;
}

, , , , .

, , ++ .. .

, ( , ), ----XXX...

0

-, 32 , ?

This is an illusory problem. The key is the index of the array - it is not stored anywhere, it is calculated based on the search. Arrays in C are adjacent blocks, access to individual elements is based on the beginning of the array and the size of the type times the index.

For the key, simply enter the value in an unsigned 32-bit type (do not just use intor unsigned int, since the size does not have to be 32 bits):

#include <inttypes.h>
char x[4] = { 'A', 'B', 'C', 'D' };
uint32_t *key = (uint32_t*)&x;

Then create a module based on the size of the table.

0
source

More articles:


All Articles