0001 /****************************************************************************************** 0002 * Test of Hashtable 0003 ******************************************************************************************/ 0004 #include "Hashtable_test.h" 0005 0006 /****************************************************************************************** 0007 * 测试散列表 0008 ******************************************************************************************/ 0009 template <typename K, typename V> //key、value 0010 void testHashtable ( int n ) { 0011 Hashtable<K, V> ht ( n ); print ( ht ); 0012 while ( ht.size() < 4 * n ) { 0013 printf ( "\n" ); 0014 switch ( dice ( 3 ) ) { 0015 case 0: { //查找,成功率 <= 33.3% 0016 K key = dice ( ( K ) n * 12 ); //[0, 3n)范围内的key 0017 printf( "Searching " ); print ( key ); printf( "(%04d) :\n", hashCode( key ) ); 0018 V* pValue = ht.get ( key ); 0019 pValue ? printf( "Found with " ), print( *pValue ) : printf( "Not found" ); printf( "\n" ); 0020 break; 0021 } 0022 case 1: { //删除,成功率 <= 33.3% 0023 K key = dice ( ( K ) n * 12 ); //[0, 3n)范围内的key 0024 printf( "Removing " ); print ( key ); printf( "(%04d) :\n", hashCode( key ) ); 0025 ht.remove( key ) ? printf( "Done\n" ), print( ht ) : printf( "Entry not exists\n" ); 0026 break; 0027 } 0028 default: {//插入,成功率 == 100% 0029 K key = dice ( ( K ) n * 12 ); V v = ( V ) 'A' + dice ( 26 ); //在[0, 2n)*['A'~'Z']范围内的词条 0030 printf( "Inserting <" ); print( key ); printf( "(%04d)", hashCode( key ) ); printf( "," ); print ( v ); printf( ">\n" ); 0031 ht.put( key, v ) ? printf( "Done\n" ), print( ht ) : printf( "Dup key\n" ); 0032 break; 0033 } 0034 } //switch 0035 } //while 0036 while ( ht.size() > 0 ) { 0037 printf( "\n" ); 0038 K key = dice( ( K ) n * 12 ); //[0, 3n)范围内的key 0039 printf( "Removing " ); print( key ); printf( " :\n" ); 0040 ht.remove( key ) ? printf( "Done\n" ), print( ht ) : printf( "Entry not exists\n" ); 0041 } 0042 } 0043 0044 /****************************************************************************************** 0045 * 主程序 0046 ******************************************************************************************/ 0047 int main ( int argc, char* argv[] ) { 0048 if ( 2 > argc ) { printf ( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; } 0049 srand( ( unsigned int ) time( NULL ) ); //设置随机种子 0050 testHashtable<int, char>( atoi( argv[1] ) ); //元素类型可以在这里任意选择 0051 return 0; 0052 }