开放定址法解决hash冲突问题(C语言实现)

/*
 * hashquad.c 开放定址法解决hash冲突问题
 */

#include
#include

#include "hashquad.h"
#include "fatal.h"

#define MIN_TABLE_SIZE (10)
#define REHASH_FACTOR    (0.7)

enum kind_of_entry { legitimate, empty, deleted };

struct hash_entry
{
    element_type    element;
    enum kind_of_entry    info;
};

typedef struct hash_entry cell;

struct hash_tbl
{
    int table_size;        /* 表容量 */
    int entry_cnt;        /* 已填入的单元数量 */
    cell    *cells;
};

static int
need_rehash( hash_table h )
{
    return ( h->entry_cnt > h->table_size * REHASH_FACTOR );
}

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_table( int table_size )
{
    hash_table h;
    int i;

    if ( table_size < MIN_TABLE_SIZE )
        Error("Table size too small!");

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

    h->table_size = next_prime( table_size );

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

    for ( i = 0; i < h->table_size; i++){
        h->cells[ i ].info = empty;
    }
    h->entry_cnt = 0;

    return h;
}

static Pos
find( element_type key, hash_table h )
{
    Pos    cur_pos;
    int    collision_num;

    collision_num = 0;
    cur_pos = hash( key, h->table_size );

    /*
    当hash表大部分被占满，这个过程可能很慢。
    也有可能进入死循环! 需要在适当的时候进行rehash!
    */
    while ( h->cells[ cur_pos ].info != empty
        &&  h->cells[ cur_pos ].element != key ){
        cur_pos += 2 * ++collision_num - 1;
        if ( cur_pos >= h->table_size )
            cur_pos -= h->table_size;
    }

    return cur_pos;
}

static void
insert( element_type key, hash_table h )
{
    Pos    p;

    p = find( key, h );
    if ( h->cells[ p ].info != legitimate ){
        h->cells[ p ].info = legitimate;
        h->cells[ p ].element = key;
        h->entry_cnt++;
    }
}

static hash_table
rehash( hash_table h)
{
    int i, old_size;
    cell *old_cells;

    old_cells = h->cells;
    old_size = h->table_size;

    /* 创建一个新的double size的空表 */
    h = initialize_table( 2 * old_size );

    /* 拷贝旧表的数据到新表 */
    for ( i = 0; i < old_size; i++ ){
        if ( old_cells[ i ].info == legitimate )
            insert( old_cells[ i ].element, h );
    }

    free( old_cells );

    return h;
}

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


void
test_hashquad( void )
{
    int i;
    Pos    p;
    hash_table h;
    element_type datas[100];

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

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

    for ( i = 0; i < get_array_size( datas ); i++ ){
        insert( datas[i], h );
        /* 在每次插入操作后检查是否需要rehash */
        if ( need_rehash( h ) )
            h = rehash( h );
    }

    p = find( 67, h );
    if ( h->cells[p].info != legitimate ){
        printf("\n\t key value 67 not in hash table!\n");
    }else{
        printf("\n\t key value 67 in hash table!\n");    
    }

    p = find( datas[31], h );
    if ( h->cells[p].info != legitimate ){
        printf("\n\t key value %d not in hash table!\n",datas[31]);
    }else{
        printf("\n\t key value %d in hash table!\n",datas[31]);
    }

    i = i;
    return;
}

/*********************************************************************************************************/
/* hashquad.h */

#ifndef _HASHQUAD_H_
#define _HASHQUAD_H_

typedef int    element_type;
typedef unsigned int Index;
typedef Index    Pos;

struct hash_tbl;
typedef struct hash_tbl *hash_table;

#endif