知新_RL

这个屌丝很懒，什么也没留下！

热门标签

C++现成的hash函数_c++ 有自带的哈希函数吗

作者：知新_RL | 2024-07-11 01:43:54

踩

c++ 有自带的哈希函数吗

一、简介

Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

二、__gnu_cxx中的hash函数

这个hash函数包含在__gnu_cxx这个命名空间里，实现在backward/hash_fun.h这个头文件里。

 
 inline  
 size_t

 
    
 __stl_hash_string( 
 const  
 char 
 * __s) 

{

 
      
 unsigned  
 long  
 __h = 0; 

 
 for  
 ( ; *__s; ++__s)

 
        
 __h = 5 * __h + *__s; 

 
      
 return  
 size_t 
 (__h); 

}

然后基于这个hash算法特化了下面几个版本的hash函数

 
 template 
 <> hash< 
 char 
 *>( 
 const  
 char 
 * __s) 

 
 template 
 <> hash< 
 const  
 char 
 *>( 
 const  
 char 
 * __s) 

 
 template 
 <> hash< 
 char 
 >( 
 char  
 __x) 

 
 template 
 <> hash<unsigned  
 char 
 >(unsigned  
 char  
 __x) 

 
 template 
 <> hash< 
 signed  
 char 
 >(unsigned  
 char  
 __x) 

 
 template 
 <> hash< 
 short 
 >( 
 short  
 __x) 

 
 template 
 <> hash<unsigned  
 short 
 >(unsigned  
 short  
 __x) 

 
 template 
 <> hash< 
 int 
 >( 
 int  
 __x) 

 
 template 
 <> hash<unsigned  
 int 
 >(unsigned  
 int  
 __x) 

 
 template 
 <> hash< 
 long 
 >( 
 long  
 __x) 

 
 template 
 <> hash<unsigned  
 long 
 >(unsigned  
 long  
 __x) 

我也基于这个hash算法实现了一个hash<string>的版本

 
 namespace  
 __gnu_cxx 

{

 
 template  
 <>

 
 struct  
 hash<string>

{

 
                  
 size_t  
 operator()( 
 const  
 string &s)  
 const 

 
                  
 {  
 return  
 __stl_hash_string(s.c_str()); } 

};

}

三、tr1中hash函数(Fnv_hash)

特点和用途：FNV能快速hash大量数据并保持较小的冲突率，它的高度分散使它适用于hash一些非常相近的字符串，比如URL，hostname，文件名，text，IP地址等。

这个hash函数包含在std::tr1这个命名空间里，包含tr1/functional头文件即可，实现在tr1_impl/functional_hash.h文件中。下面是它的实现

 
 //Dummy generic implementation (for sizeof(size_t) != 4, 8) 

 
 template 
 <std:: 
 size_t  
 =  
 sizeof 
 (std:: 
 size_t 
 )> 

 
 struct  
 Fnv_hash 

{

 
    
 static  
 std:: 
 size_t 

 
    
 hash( 
 const  
 char 
 * first, std:: 
 size_t  
 length) 

{

 
 std:: 
 size_t  
 result = 0; 

 
 for  
 (; length > 0; --length) 

 
    
 result = (result * 131) + *first++; 

 
 return  
 result; 

}

};

 
 template 
 <> 

 
 struct  
 Fnv_hash<4> 

{

 
    
 static  
 std:: 
 size_t 

 
    
 hash( 
 const  
 char 
 * first, std:: 
 size_t  
 length) 

{

 
 std:: 
 size_t  
 result =  
 static_cast 
 <std:: 
 size_t 
 >(2166136261UL); 

 
 for  
 (; length > 0; --length) 

{

 
      
 result ^= (std:: 
 size_t 
 )*first++; 

 
      
 result *= 16777619UL; 

}

 
 return  
 result; 

}

};

 
 template 
 <> 

 
 struct  
 Fnv_hash<8> 

{

 
    
 static  
 std:: 
 size_t 

 
    
 hash( 
 const  
 char 
 * first, std:: 
 size_t  
 length) 

{

 
 std:: 
 size_t  
 result =  
 static_cast 
 <std:: 
 size_t 
 >(14695981039346656037ULL); 

 
 for  
 (; length > 0; --length) 

{

 
      
 result ^= (std:: 
 size_t 
 )*first++; 

 
      
 result *= 1099511628211ULL; 

}

 
 return  
 result; 

}

};

然后基于这个Fnv_hash算法实现了各种版本的hash函数，其中包括string和wstring版本的。

四、测试

#include <iostream>

#include <string>

#include <tr1/functional>

int main()

{

std::string name = "jim jim jim";

//直接调用Fnv_hash

std::cout << std::tr1::_Fnv_hash<1>::hash(name.c_str(), name.size()) << std::endl;

std::cout << std::tr1::_Fnv_hash<4>::hash(name.c_str(), name.size()) << std::endl;

std::cout << std::tr1::_Fnv_hash<8>::hash(name.c_str(), name.size()) << std::endl;

//string

std::cout << std::tr1::hash<std::string>()(name) << std::endl;

//wstring

std::wstring age = L"22222";;

std::cout << std::tr1::hash<std::wstring>()(age) << std::endl;

//bool

std::cout << std::tr1::hash<bool>()(true) << std::endl;

//float

std::cout << std::tr1::hash<float>()(24.0f) << std::endl;

//double

std::cout << std::tr1::hash<double>()(24.0) << std::endl;

//short

std::cout << std::tr1::hash<short>()(static_cast<short>(24)) << std::endl;

//int

std::cout << std::tr1::hash<int>()(24) << std::endl;

//long

std::cout << std::tr1::hash<long>()(24L) << std::endl;

return 0;

}

说明：

gcc 4.8以上的版本支持c++11,我用的是4.7的版本。tr1/functional在gcc 4.7的版本里gcc的搜寻路径下直接就有functional这个头文件，可以直接#include <functional>，这样就不需要std::tr1这个明明空间了，直接在std的命名空间下，编译的时候需要加个参数即可。

[jim@localhost ~]$g++ -std=c++0x myHash.cpp

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/808360