Эффективная реализация Hashtable, с локальным свойством кеша (Хеш-таблица, чувствительная к локальности)
Я пытаюсь поиграть со структурой данных C (хэш-таблица). Я не использую никакую предварительно созданную библиотеку хеш-таблиц (например, STL), потому что я хочу лучше понять, как она работает. Поэтому здесь я создаю хеш-таблицу, содержащую список элементов, где каждый элемент содержит ключ и данные строкового элемента (массив символов), а также длину данных строкового элемента.
Моя реализация работает, но после обсуждения ее с одним из моих коллег мне сказали, что моя реализация неэффективна, особенно в контексте того, что: моя реализация не поддерживает кэширование, в результате чего мой поиск по хеш-таблице неэффективен. Я не очень понял его объяснение.
Итак, я хотел бы знать, что на самом деле означает реализация локального кэша?
Как я могу сделать реализацию хэш-таблицы более эффективной, используя это свойство локальности кэша при поиске? Есть ли лучший способ построить структуру для этого и лучший способ организации элементов (поиск)?
Вот что я сделал до сих пор:
HASHTBL.h
struct hashelt {
struct hashelt* he_next; /* One way linked list pointer */
char* he_key; /* Pointer to element's key */
char* he_data; /* Pointer to element's data */
int he_data_len; /* Length of element's data */
};
typedef struct hashelt hashelt;
struct hashtbl {
hashelt** ht_links; /* Array of pointers to elemsnts */
int ht_prime; /* Length of hash table - it is a prime number */
};
typedef struct hashtbl hashtbl;
int prime_check( int num );
hashtbl* hashtbl_init( int tbl_size );
int hashtbl_key_convert( hashtbl* htable, char* hkey );
hashelt* hashtbl_lookup( hashtbl* htable, char* hkey, char* hdata );
int hashtbl_add( hashtbl* htable, char* hkey, char* hdata );
void hashtbl_print( hashtbl* htable );
HASHTBL.c
/*
* prime_check
* Check if num is a prime or not.
* num Number to use as an upper bound.
*
* The functions returns 0 for a prime and 1 otherwise.
*/
int prime_check( int num ) {
/* Local declarations */
int i; /* Loop counter */
/* Search through the first sqrt(num) integers */
for( i = 2; i*i < num; i++ )
if ( (num % i) == 0 )
return 1;
/* It is a prime */
return 0;
}
/*
* hashtbl_init
* Create and initialize a hash table.
* The input variable are
* tbl_size Suggested size of the table, which should be a prime or 0.
* The functions returns a pointer to a hashtbl or NULL for failure.
* The hash table is the size of the largest prime found for the suggested
* table size of the default size if 0 is given as a suggestion.
*/
hashtbl* hashtbl_init( int tbl_size ) {
/* Local declarations */
hashtbl* hp; /* Hash table pointer */
int i; /* Loop counter */
/* Initial values */
hp = NULL;
/* Determine the actual table size */
if ( tbl_size <= 0 )
tbl_size = DEFAULT_HASHTBL_LENGTH;
else if ( prime_check( tbl_size ) )
return NULL;
if ( tbl_size <= 0 )
return NULL;
/* Allocate the hash table */
if( ( hp = (hashtbl*)malloc( sizeof(hashtbl) ) ) == NULL )
return hp;
/* Allocate the linked list vector */
if( ( hp->ht_links = (hashelt**)malloc( tbl_size * sizeof(hashelt*) ) ) == NULL ) {
free( hp );
return NULL;
}
/* Fill in the hash table with no entries */
for( i = 0 ; i < tbl_size; i++ )
hp->ht_links[i] = NULL;
/* Fill in the hash table size */
hp->ht_prime = tbl_size;
/* All done */
return hp;
}
/*
* hashtbl_key_convert
* Make an index into the key chain in the hash table from a key:
* kindex = sum of the characters in hkey modulo ht_prime
* The input variable are
* htable A pointer to a hash table.
* hkey A pointer to a a key.
* The functions returns an index into the key chain.
*/
int hashtbl_key_convert( hashtbl* htable, char* hkey ) {
/* Local declarations */
int i; /* Loop counter */
int klen; /* Length of the key */
int kindex; /* Key index to return */
/* Compute the key index */
klen = strlen( hkey );
for( kindex = 0, i = 0 ; i < klen; i++ )
kindex += hkey[i];
kindex = kindex % htable->ht_prime;
/* All done */
return kindex;
}
/*
* hashtbl_lookup
* Lookup a (key,data) in a hash table.
* The input variable are
* htable A pointer to a hash table.
* hkey A key.
* hdata A pointer to the data.
* The functions returns 0 for found and 1 for not found.
*/
hashelt* hashtbl_lookup( hashtbl* htable, char* hkey, char* hdata ) {
/* Local declarations */
hashelt* hep; /* Hash element pointer */
int i; /* Loop counter */
int key; /* Hash table key index */
/* Get key index from hkey */
key = hashtbl_key_convert( htable, hkey );
/* Search through the hash table, including collicions */
for( hep = htable->ht_links[key] ; hep != NULL ; hep = hep->he_next )
if ( strcmp( hep->he_key, hkey ) == 0 )
return hep;
/* Not found */
return NULL;
}
/*
* hashtbl_add
* Add a (key,data) to a hash table.
* The input variable are
* htable A pointer to a hash table.
* hkey A key.
* hdata A pointer to the data.
* The functions returns 0 for success and 1-4 for failure.
*
*/
int hashtbl_add( hashtbl* htable, char* hkey, char* hdata ) {
/* Local declarations */
hashelt* hep; /* Element in linked list */
hashelt* newelt; /* New element in hash table */
int i; /* Loop counter */
int dlen; /* Length of data */
int key; /* Hash table key index */
/* Get key index from hkey */
key = hashtbl_key_convert( htable, hkey );
/* Check if the (key,data) is already in the hash table */
if ( ( hep = hashtbl_lookup( htable, hkey, hdata ) ) != NULL )
if ( strcmp( hep->he_data, hdata ) == 0 )
return 1;
/* Add the data */
dlen = strlen( hdata );
hep = htable->ht_links[key];
if ( ( newelt = (hashelt*)malloc( sizeof( hashelt ) ) ) == NULL ) {
fprintf( stderr, "hashtbl_add: Cannot allocate new hash element\n" );
return 3;
}
newelt->he_next = hep;
newelt->he_data_len = dlen;
newelt->he_key = (char*)malloc( (strlen(hkey)+1) * sizeof(char) );
newelt->he_data = (char*)malloc( (dlen+1) * sizeof(char) );
if ( newelt->he_key == NULL || newelt->he_data == NULL ) {
fprintf( stderr, "hashtbl_add: Cannot allocate new hash element contents\n" );
return 4;
}
strcpy( newelt->he_key, hkey );
strcpy( newelt->he_data, hdata );
htable->ht_links[key] = newelt;
/* All done */
return 0;
}
/*
* hashtbl_print
* Print an entire hash table.
* The input variable are
* htable A pointer to a hash table.
* The functions returns 0 for success and 1-4 for failure.
*/
void hashtbl_print( hashtbl* htable ) {
/* Local declarations */
hashelt* hep; /* Element in linked list */
int i; /* Loop counter */
int l; /* Link count */
/* Initial printing */
printf( "\nHash table contents\n" );
/* Print a has tbale out, one key bucket at a time */
for( i = 0 ; i < htable->ht_prime ; i++ ) {
printf( "\nkey index %i\n", i );
hep = htable->ht_links[i];
if ( hep == NULL )
printf( " No entries in the linked list\n" );
else {
l = 0;
while( hep != NULL ) {
printf( " Element %d\n", l );
printf( " key: %s\n", hep->he_key );
printf( " data: %s\n", hep->he_data );
printf( " data_len: %d\n", hep->he_data_len );
hep = hep->he_next;
}
}
}
/* All done */
}
ГЛАВНЫЙ ФАЙЛ
void make_string( char* buffer, int blen ) {
/* Local declarations */
char viable_chars[] = { "abcdefghijklmnopqrstuvwxyz-0123456789_ABCDEFGHIJKLMNOPQRSTUVWXYZ" };
char* bp; /* Pointer into buffer */
int i; /* Loop counter */
int c; /* Index into viable_chars */
static int vc_len = 0; /* Length of viable_chars */
/* Do once only */
if ( vc_len == 0 )
vc_len = strlen( viable_chars );
/* Do the fill operation on a subset of buffer */
blen = rand() % blen;
if ( blen == 0 ) blen++;
for( bp = buffer, i = 0; i < blen ; i++ ) {
c = rand() % vc_len;
*bp++ = viable_chars[c];
}
*bp++ = '\0';
}
int main( int argc, char** argv ) {
/* Local declarations */
hashtbl* htable; /* Hash table pointer */
char* kstrings; /* Pointer to key vector */
char* dstrings; /* Pointer to data vector */
int tblsize = 0; /* Hash table size */
int nkeys = 0; /* Number of keys */
int dlen = 0; /* Maximum data length for (keys,data) */
int i; /* Loop counter */
double t1; /* Time keeper */
double t2; /* Time keeper */
double mrun(); /* Get timing information */
#ifdef GOOD_SEED
/* Get a good random number seed */
struct timeval t1; /* holder for time of day (seconds, microseconds) */
gettimeofday( &t1, NULL );
srand( t1.tv_usec * t1.tv_sec );
#endif
/* Get hash table size */
printf( "Hash table size (pick a prime or bound for one): " );
scanf( "%d", &tblsize );
fflush( stdin );
/* Initialize hash table */
if( ( htable = hashtbl_init( tblsize ) ) == NULL ) {
fprintf( stderr, "Oops... hashtbl_init returned NULL\n" );
return 1;
}
printf( "Actual size of hash table is %d\n", htable->ht_prime );
/* Now fill it up */
while ( nkeys <= 0 ) {
printf( "How many keys do you want? " );
scanf( "%d", &nkeys );
fflush( stdin );
}
while ( dlen <= 0 ) {
printf( "What is the maximum character string length? " );
scanf( "%d", &dlen );
fflush( stdin );
}
/* Allocate vectors for (key,data) */
kstrings = (char*)malloc( (dlen+1) * sizeof( char ) );
dstrings = (char*)malloc( (dlen+1) * sizeof( char ) );
if ( kstrings == NULL || dstrings == NULL ) {
fprintf( stderr, "main: Could not allocate string vectors for (key,data)\n" );
return 2;
}
/* Now fill it up */
for( i = 0 ; i < nkeys ; i++ ) {
make_string( kstrings, dlen );
make_string( dstrings, dlen );
hashtbl_add( htable, kstrings, dstrings );
}
/* Print it out */
hashtbl_print( htable );
/* All done */
return 0;
}
1 ответ
Решение
Место было бы лучше, если бы вы изменили
struct hashtbl {
hashelt** ht_links; /* Array of pointers to elemsnts
...
быть:
struct hashtbl {
...
hashelt* elements; /* Array of elements (as last entry of struct)
Подумайте о том, как выглядит хеш-таблица: в вашей версии таблица состоит из указателей на элементы, в моей модификации таблица фактически содержит эти структуры, упакованные одна за другой! Есть, конечно, недостаток: пустой хэш-контейнер содержит не только нулевой указатель (как в вашей версии), но и целое sizeof(hashelt), Кроме того, вы должны убедиться, что hashtbl-struct выделена не с размером sizeof(hashtbl) потому что ваш хештбл содержит хешелт: вы должны выделить ht_prime*sizeof(hashelt)+sizeof(int) (первое слагаемое относится к хешелту ht_prime, который вы содержите, а второе слагаемое для хранения самого ht_prime).