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 }