首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

求HASH算法解决方法

2013-11-14 
求HASH算法key基本上是C++的常用关键字(不是全部),一共65个。比如:“if else break while for ”......hash表

求HASH算法
key基本上是C++的常用关键字(不是全部),一共65个。比如:“if else break while for ”......

hash表总容量为65×120%=70多个,取素数。我构建了n多的hash算法,发现对这些关键词进行分布时,不够散列。总有很多冲突,哪一位大侠有比较好的HASH算法,专门针对C++关键词的。

关键词如下:


        s_mapKeywords[ _T("if") ]        = HXTOKENTYPE_KEYWORD_IF;
        s_mapKeywords[ _T("else") ]      = HXTOKENTYPE_KEYWORD_ELSE;
        s_mapKeywords[ _T("for") ]       = HXTOKENTYPE_KEYWORD_FOR;
        s_mapKeywords[ _T("while") ]     = HXTOKENTYPE_KEYWORD_WHILE;
        s_mapKeywords[ _T("break") ]     = HXTOKENTYPE_KEYWORD_BREAK;
        s_mapKeywords[ _T("return") ]    = HXTOKENTYPE_KEYWORD_RETURN;
        s_mapKeywords[ _T("continue") ]  = HXTOKENTYPE_KEYWORD_CONTINUE;
        s_mapKeywords[ _T("switch") ]    = HXTOKENTYPE_KEYWORD_SWITCH;
        s_mapKeywords[ _T("case") ]      = HXTOKENTYPE_KEYWORD_CASE;
        s_mapKeywords[ _T("do") ]        = HXTOKENTYPE_KEYWORD_DO;
        s_mapKeywords[ _T("goto") ]      = HXTOKENTYPE_KEYWORD_GOTO;
        s_mapKeywords[ _T("typedef") ]   = HXTOKENTYPE_KEYWORD_TYPEDEF;
        s_mapKeywords[ _T("new") ]       = HXTOKENTYPE_KEYWORD_NEW;
        s_mapKeywords[ _T("delete") ]    = HXTOKENTYPE_KEYWORD_DELETE;
        s_mapKeywords[ _T("friend") ]    = HXTOKENTYPE_KEYWORD_FRIEND;
        s_mapKeywords[ _T("public") ]    = HXTOKENTYPE_KEYWORD_PUBLIC;
        s_mapKeywords[ _T("protected") ] = HXTOKENTYPE_KEYWORD_PROTECTED;
        s_mapKeywords[ _T("private") ]   = HXTOKENTYPE_KEYWORD_PRIVATE;
        s_mapKeywords[ _T("default") ]   = HXTOKENTYPE_KEYWORD_DEFAULT;
        s_mapKeywords[ _T("virtual") ]   = HXTOKENTYPE_KEYWORD_VRITUAL;
        s_mapKeywords[ _T("operator") ]  = HXTOKENTYPE_KEYWORD_OPERATOR;
        s_mapKeywords[ _T("try") ]       = HXTOKENTYPE_KEYWORD_TRY;
        s_mapKeywords[ _T("catch") ]     = HXTOKENTYPE_KEYWORD_CATCH;
        s_mapKeywords[ _T("finally") ]   = HXTOKENTYPE_KEYWORD_FINALLY;
        s_mapKeywords[ _T("throw") ]     = HXTOKENTYPE_KEYWORD_THROW;
        s_mapKeywords[ _T("leave") ]     = HXTOKENTYPE_KEYWORD_LEAVE;
        s_mapKeywords[ _T("#include") ]  = HXTOKENTYPE_KEYWORD_EXP_INCLUDE;
        s_mapKeywords[ _T("#define") ]   = HXTOKENTYPE_KEYWORD_EXP_DEFINE;
        s_mapKeywords[ _T("#ifdef") ]    = HXTOKENTYPE_KEYWORD_EXP_IFDEF;
        s_mapKeywords[ _T("#ifndef") ]   = HXTOKENTYPE_KEYWORD_EXP_IFNDEF;
        s_mapKeywords[ _T("#else") ]     = HXTOKENTYPE_KEYWORD_EXP_ELSE;
        s_mapKeywords[ _T("#endif") ]    = HXTOKENTYPE_KEYWORD_EXP_ENDIF;
        s_mapKeywords[ _T("#undef") ]    = HXTOKENTYPE_KEYWORD_EXP_UNDEF;
        s_mapKeywords[ _T("int") ]       = HXTOKENTYPE_DECLARE_INT;
        s_mapKeywords[ _T("float") ]     = HXTOKENTYPE_DECLARE_FLOAT;
        s_mapKeywords[ _T("double") ]    = HXTOKENTYPE_DECLARE_DOUBLE;
        s_mapKeywords[ _T("char") ]      = HXTOKENTYPE_DECLARE_CHAR;
        s_mapKeywords[ _T("BYTE") ]      = HXTOKENTYPE_DECLARE_BYTE;
        s_mapKeywords[ _T("WORD") ]      = HXTOKENTYPE_DECLARE_WORD;


        s_mapKeywords[ _T("DWORD") ]     = HXTOKENTYPE_DECLARE_DWORD;
        s_mapKeywords[ _T("long") ]      = HXTOKENTYPE_DECLARE_LONG;
        s_mapKeywords[ _T("unsigned") ]  = HXTOKENTYPE_DECLARE_UNSIGNED;
        s_mapKeywords[ _T("const") ]     = HXTOKENTYPE_DECLARE_CONST;
        s_mapKeywords[ _T("struct") ]    = HXTOKENTYPE_DECLARE_STRUCT;
        s_mapKeywords[ _T("union") ]     = HXTOKENTYPE_DECLARE_UNION;
        s_mapKeywords[ _T("enum") ]      = HXTOKENTYPE_DECLARE_ENUM;
        s_mapKeywords[ _T("class") ]     = HXTOKENTYPE_DECLARE_CLASS;
        s_mapKeywords[ _T("short") ]     = HXTOKENTYPE_DECLARE_SHORT;
        s_mapKeywords[ _T("void") ]      = HXTOKENTYPE_DECLARE_VOID;
        s_mapKeywords[ _T("static") ]    = HXTOKENTYPE_DECLARE_STATIC;
        s_mapKeywords[ _T("sizeof") ]    = HXTOKENTYPE_CONST_SIZEOF;
        s_mapKeywords[ _T("TRUE") ]      = HXTOKENTYPE_CONST_CONST_TRUE;
        s_mapKeywords[ _T("FALSE") ]     = HXTOKENTYPE_CONST_CONST_FALSE;
        s_mapKeywords[ _T("true") ]      = HXTOKENTYPE_CONST_CONST_TRUE;
        s_mapKeywords[ _T("false") ]     = HXTOKENTYPE_CONST_CONST_FALSE;
        s_mapKeywords[ _T("NULL") ]      = HXTOKENTYPE_CONST_CONST_NULL;
        s_mapKeywords[ _T("this") ]      = HXTOKENTYPE_CONST_CONST_THIS;

hash?关键词?map
[解决办法]
帮你顶一下,等大神粗线
[解决办法]
我一般需要hash string 的时候用 unordered_map VC自带 linux的话
#ifdef _MSC_VER
#  define COMPILER COMPILER_MICROSOFT
#elif defined( __GNUC__ )
#  define COMPILER COMPILER_GNU
#  define GCC_VERSION (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__)
#else
#  error "FATAL ERROR: Unknown compiler."
#endif

#if COMPILER_HAS_CPP11_SUPPORT
#    include <unordered_map>
#elif COMPILER == COMPILER_GNU && defined(__clang__) && defined(_LIBCPP_VERSION)
#    include <unordered_map>
#elif COMPILER == COMPILER_GNU && GCC_VERSION > 40200
#    include <tr1/unordered_map>
#elif COMPILER == COMPILER_GNU && GCC_VERSION >= 30000
#    include <ext/hash_map>
#endif


[解决办法]
65个还是循环逐个比较可能更快吧。
[解决办法]
1. 数据规模加个万再来倒腾性能
2. 对于关键字这种固定数据的情况,一般都是直接用完美hash,连检测冲突都用不着。
[解决办法]
直接遍历更好

热点排行