分离链接法解决hash冲突问题(C语言实现)

/* hashsep.c */

#include
#include

#include "hashsep.h"
#include "fatal.h"

#define MIN_TABLE_SIZE (10)

struct list_node
{
 element_type element;
 pos  next;
};

typedef pos list;

/* 为了简单起见使用了带头节点的链表 */
struct hash_tbl
{
 int  table_size;
 list *lists;
};

static int
next_prime( int N )
{
 int i;

 if ( N % 2 ==  0 )
  N++;

 for ( ; ; N += 2 ){
  for ( i = 3; i * i <= N; i += 2 ){
   if ( N % i == 0 )
    goto cont_outer;
  }
  return N;
cont_outer: ;
 }
}
/* 采用简单的取模方法 */

static Index
hash ( element_type key, int table_size )
{
 return key % table_size;
}

static hash_table
initialize_talbe( int table_size )
{
 hash_table h;
 int i;

 if ( table_size < MIN_TABLE_SIZE ){
  Error("Table size too small!");
  return NULL;
 }

 h = malloc( sizeof( struct hash_tbl ) );
 if ( h == NULL )
  Error("Out of space!");

 h->table_size = next_prime(table_size);
 h->lists = malloc( sizeof( list ) * h->table_size );
 if ( h->lists == NULL ){
  free(h);
  Error("Out of space!");
 }

 /* 预先分配全部头节点 */
 for ( i = 0; i < h->table_size; i++){
  h->lists[i] = malloc( sizeof( struct list_node ) );
  if ( h->lists[i] == NULL ){
   Error("Out of space!");
   goto init_fail;
  }else{
   h->lists[i]->next = NULL;
  }
 }

 return h;

init_fail:
 for ( i = 0; i < h->table_size || h->lists[i] == NULL; i++){
  free( h->lists[i] );
  h->lists[i] = NULL;
 }
 free( h->lists );
 free( h );

 return NULL;
}

static pos
find( element_type key, hash_table h )
{
 pos p;
 list l;

 l = h->lists[ hash( key, h->table_size ) ];
 p = l->next;
 while ( p != NULL && p->element != key )
   p = p->next;

 return p;
}

static void
insert( element_type key, hash_table h )
{
 pos p, new_cell;
 list l;

 p = find( key, h );
 if ( p == NULL ){
  new_cell = malloc( sizeof( struct list_node ) );
  if ( new_cell == NULL )
   Error("Out of space!");
  else{
   l = h->lists[ hash( key, h->table_size ) ];
   new_cell->next = l->next;
   new_cell->element = key;
   l->next = new_cell;
  }
 }
}

static element_type
retrieve( pos p)
{
 return p->element;
}

static void
destroy_table( hash_table h )
{
 int i;
 pos p, tmp;

 for ( i = 0; i < h->table_size; i++ ){
  p = h->lists[i];

  while ( p != NULL ){
   tmp = p->next;
   free( p );
   p = tmp;
  }
 }

 free( h->lists );
 free( h );
}

/************ The next is test functions ***************/
#define get_array_size(array) ( sizeof(array) / sizeof(array[0]) )

void
test_hashsep( void )
{
 int i;
 pos p;
 hash_table h;
 element_type datas[100];

 for ( i = 0; i < get_array_size( datas ); i++ ){
  datas[i] = i;
 }

 h = initialize_talbe( 13 );
 if ( h == NULL )
  Error("Initialize error!");

 for ( i = 0; i < get_array_size( datas ); i++ ){
  insert( datas[i], h );
 }

 p = find( 31, h );

 p = find( 65, h );

 return;
}

/***************************************************************************/

/* hashsep.h */

#ifndef _HASHSEP_H_
#define _HASHSEP_H_

typedef  int  element_type;
typedef  int  Index;

struct list_node;
typedef struct list_node *pos;

struct hash_tbl;
typedef struct hash_tbl *hash_table;

#endif