学步园

/*<br /> * hashquad.c 开放定址法解决hash冲突问题<br /> */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include "hashquad.h"<br /> #include "fatal.h"<br /> #define MIN_TABLE_SIZE (10)<br /> #define REHASH_FACTOR (0.7)<br /> enum kind_of_entry { legitimate, empty, deleted };<br /> struct hash_entry<br /> {<br /> element_type element;<br /> enum kind_of_entry info;<br /> };<br /> typedef struct hash_entry cell;<br /> struct hash_tbl<br /> {<br /> int table_size; /* 表容量 */<br /> int entry_cnt; /* 已填入的单元数量 */<br /> cell *cells;<br /> };<br /> static int<br /> need_rehash( hash_table h )<br /> {<br /> return ( h->entry_cnt > h->table_size * REHASH_FACTOR );<br /> }<br /> static int<br /> next_prime( int N )<br /> {<br /> int i;<br /> if ( N % 2 == 0 )<br /> N++;<br /> for ( ; ; N += 2 ){<br /> for ( i = 3; i * i <= N; i += 2 ){<br /> if ( N % i == 0 )<br /> goto cont_outer;<br /> }<br /> return N;<br /> cont_outer: ;<br /> }<br /> }<br /> static Index<br /> hash( element_type key, int table_size )<br /> {<br /> return key % table_size;<br /> }<br /> static hash_table<br /> initialize_table( int table_size )<br /> {<br /> hash_table h;<br /> int i;<br /> if ( table_size < MIN_TABLE_SIZE )<br /> Error("Table size too small!");<br /> h = malloc( sizeof( struct hash_tbl ) );<br /> if ( h == NULL )<br /> Error("Out of space!");<br /> h->table_size = next_prime( table_size );<br /> h->cells = malloc( sizeof( cell ) * h->table_size );<br /> if ( h->cells == NULL ){<br /> free( h );<br /> Error("Out of space!");<br /> }<br /> for ( i = 0; i < h->table_size; i++){<br /> h->cells[ i ].info = empty;<br /> }<br /> h->entry_cnt = 0;<br /> return h;<br /> }<br /> static Pos<br /> find( element_type key, hash_table h )<br /> {<br /> Pos cur_pos;<br /> int collision_num;<br /> collision_num = 0;<br /> cur_pos = hash( key, h->table_size );<br /> /*<br /> 当hash表大部分被占满，这个过程可能很慢。<br /> 也有可能进入死循环! 需要在适当的时候进行rehash!<br /> */<br /> while ( h->cells[ cur_pos ].info != empty<br /> && h->cells[ cur_pos ].element != key ){<br /> cur_pos += 2 * ++collision_num - 1;<br /> if ( cur_pos >= h->table_size )<br /> cur_pos -= h->table_size;<br /> }<br /> return cur_pos;<br /> }<br /> static void<br /> insert( element_type key, hash_table h )<br /> {<br /> Pos p;<br /> p = find( key, h );<br /> if ( h->cells[ p ].info != legitimate ){<br /> h->cells[ p ].info = legitimate;<br /> h->cells[ p ].element = key;<br /> h->entry_cnt++;<br /> }<br /> }<br /> static hash_table<br /> rehash( hash_table h)<br /> {<br /> int i, old_size;<br /> cell *old_cells;<br /> old_cells = h->cells;<br /> old_size = h->table_size;<br /> /* 创建一个新的double size的空表 */<br /> h = initialize_table( 2 * old_size );<br /> /* 拷贝旧表的数据到新表 */<br /> for ( i = 0; i < old_size; i++ ){<br /> if ( old_cells[ i ].info == legitimate )<br /> insert( old_cells[ i ].element, h );<br /> }<br /> free( old_cells );<br /> return h;<br /> }<br /> /************ The next is test functions ***************/<br /> #define get_array_size(array) ( sizeof(array) / sizeof(array[0]) )</p> <p>void<br /> test_hashquad( void )<br /> {<br /> int i;<br /> Pos p;<br /> hash_table h;<br /> element_type datas[100];<br /> for ( i = 0; i < get_array_size( datas ); i++ ){<br /> datas[i] = rand() % 1000;<br /> }<br /> h = initialize_table( 13 );<br /> if ( h == NULL )<br /> Error("Initialize error!");<br /> for ( i = 0; i < get_array_size( datas ); i++ ){<br /> insert( datas[i], h );<br /> /* 在每次插入操作后检查是否需要rehash */<br /> if ( need_rehash( h ) )<br /> h = rehash( h );<br /> }<br /> p = find( 67, h );<br /> if ( h->cells[p].info != legitimate ){<br /> printf("/n/t key value 67 not in hash table!/n");<br /> }else{<br /> printf("/n/t key value 67 in hash table!/n");<br /> }<br /> p = find( datas[31], h );<br /> if ( h->cells[p].info != legitimate ){<br /> printf("/n/t key value %d not in hash table!/n",datas[31]);<br /> }else{<br /> printf("/n/t key value %d in hash table!/n",datas[31]);<br /> }<br /> i = i;<br /> return;<br /> }<br /> /*********************************************************************************************************/<br /> /* hashquad.h */<br /> #ifndef _HASHQUAD_H_<br /> #define _HASHQUAD_H_<br /> typedef int element_type;<br /> typedef unsigned int Index;<br /> typedef Index Pos;<br /> struct hash_tbl;<br /> typedef struct hash_tbl *hash_table;<br /> #endif