c++中有現成的string hash函數么？

01-05

我想實現一個功能，輸入一個字元串，然後返回一個int的key。（c++實現）

C++11有，gcc 是 murmur hash。

有條件的話可以考慮用 https://code.google.com/p/cityhash/。

#include & #include & #include &

int main(int argc, char *argv[]) { std::hash& h; size_t n = h("Just fucking google it"); std::cout &<&< n &<&< std::endl; return 0; }

&> g++ -std=c++0x main.cpp

C++有現成的hash函數，在C++標準中已經規定，這個hash函數是std::hash。

在具體實現方面，GCC(確切說是libc.so)中用的是murmur2 hash (閉源的VC看不到。。。)

經本人測試調研，它存在以下問題：

1) 32bit和64bit操作系統下，生成的hash函數不兼容(這好象是廢話，一個結果是32bit，一個是64bit)

2) 64bit版本的實現貌似有點搓(衝突率有點高)

3) 完全沒有考慮endian的問題

4) 很容易人工造出conclusion。(所以不適合用來防DDos之類的應用)

所以如果自己真的需要一個固定的hash函數，還是不建議用GCC自帶的版本。

個人推薦直接去murmur2官網複製粘貼(官網上的，license是public domain，也更加友好)

BTW：

1) CityHash我試過，起碼在我們當時項目所需的數據集上，比Murmur2慢好多

2) Boost的hash string的函數，我記得是直接調用操作系統提供的Hash函數，所以樓主應該在庫里找不到。

3) 還是不建議把Perl或者GCC的hash的代碼直接考出來，因為他們是GPL的。。。況且他們默認用的就是Murmur2。。。

也可以用這些經典演算法呀

各種字元串Hash函數比較

#define HASH_STRING_PIECE(string_piece) size_t result = 0; for (auto it = string_piece.cbegin(); it != string_piece.cend(); ++it) { result = (result * 131) + *it; } return resu<

from chromiumsrcasestringsstring_piece.h

我能想到的有若干個選擇：

用Boost的unordered_map或者unordered_set，或者把它的字元串hash的代碼拷出來。

用Glib的字元串hash，或者把相應代碼拷出來。

把Perl的字元串hash代碼拷出來。

/*********************************StringHash.h*********************************/

#pragma once

#define MAXTABLELEN 1024 // 默認哈希索引表大小

//////////////////////////////////////////////////////////////////////////

// 哈希索引表定義

typedef struct _HASHTABLE

{

　　long nHashA;

　　long nHashB;

　　bool bExists;

}HASHTABLE, *PHASHTABLE ;

class StringHash

{

public:

　　StringHash(const long nTableLength = MAXTABLELEN);

　　~StringHash(void);

private:

　　unsigned long cryptTable[0x500];

　　unsigned long m_tablelength; // 哈希索引表長度

　 HASHTABLE *m_HashIndexTable;

private:

　　void InitCryptTable(); // 對哈希索引表預處理

　　unsigned long HashString(const string lpszString, unsigned long dwHashType); // 求取哈希值

public:

　　bool Hash(string url);

　　unsigned long Hashed(string url); // 檢測url是否被hash過

};

/*********************************StringHash.cpp*********************************/

#include "StdAfx.h"

#include "StringHash.h"

StringHash::StringHash(const long nTableLength /*= MAXTABLELEN*/)

{

　　InitCryptTable();

　　m_tablelength = nTableLength;

　　//初始化hash表

　　m_HashIndexTable = new HASHTABLE[nTableLength];

　　for ( int i = 0; i &< nTableLength; i++ )

　　{

　　　　m_HashIndexTable[i].nHashA = -1;

　　　　m_HashIndexTable[i].nHashB = -1;

　　　　m_HashIndexTable[i].bExists = false;

　　}

StringHash::~StringHash(void)

{

　　//清理內存

　　if ( NULL != m_HashIndexTable )

　　{

　　　　delete []m_HashIndexTable;

　　　　m_HashIndexTable = NULL;

　　　　m_tablelength = 0;

　　}

/************************************************************************/

/*函數名：InitCryptTable

/*功能：對哈希索引表預處理

/*返回值：無

/************************************************************************/

void StringHash::InitCryptTable()

{

　 unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;

　　for( index1 = 0; index1 &< 0x100; index1++ )

　　{

　　　　for( index2 = index1, i = 0; i &< 5; i++, index2 += 0x100 )

　　　　{

　　　　　　unsigned long temp1, temp2;

　　　　　　seed = (seed * 125 + 3) % 0x2AAAAB;

　　　　　　temp1 = (seed 0xFFFF) &<&< 0x10;

　　　　　　seed = (seed * 125 + 3) % 0x2AAAAB;

　　　　　　temp2 = (seed 0xFFFF);

　　　　　　cryptTable[index2] = ( temp1 | temp2 );

　　　　}

/************************************************************************/

/*函數名：HashString

/*功能：求取哈希值

/*返回值：返回hash值

/************************************************************************/

unsigned long StringHash::HashString(const string lpszString, unsigned long dwHashType)

{

　　unsigned char *key = (unsigned char *)(const_cast&(lpszString.c_str()));

　　unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;

　　int ch;

　　while(*key != 0)

　　{

　　　　ch = toupper(*key++);

　　　　seed1 = cryptTable[(dwHashType &<&< 8) + ch] ^ (seed1 + seed2);

　　　　seed2 = ch + seed1 + seed2 + (seed2 &<&< 5) + 3;

　　}

　　return seed1;

}

/************************************************************************/

/*函數名：Hashed

/*功能：檢測一個字元串是否被hash過

/*返回值：如果存在，返回位置；否則，返回-1

/************************************************************************/

unsigned long StringHash::Hashed(string lpszString)

{

　　const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;

　 //不同的字元串三次hash還會碰撞的幾率無限接近於不可能

　　unsigned long nHash = HashString(lpszString, HASH_OFFSET);

　 unsigned long nHashA = HashString(lpszString, HASH_A);

　　unsigned long nHashB = HashString(lpszString, HASH_B);

　 unsigned long nHashStart = nHash % m_tablelength,

　　nHashPos = nHashStart;

　　while ( m_HashIndexTable[nHashPos].bExists)

　　{

　　if (m_HashIndexTable[nHashPos].nHashA == nHashA m_HashIndexTable[nHashPos].nHashB == nHashB)

　　　　return nHashPos;

　　else

　　nHashPos = (nHashPos + 1) % m_tablelength;

　　if (nHashPos == nHashStart)

　　break;

　　}

　　return -1; //沒有找到

}

/************************************************************************/

/*函數名：Hash

/*功能：hash一個字元串

/*返回值：成功，返回true；失敗，返回false

/************************************************************************/

bool StringHash::Hash(string lpszString)

{

　　const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;

　　unsigned long nHash = HashString(lpszString, HASH_OFFSET);

　　unsigned long nHashA = HashString(lpszString, HASH_A);

　　unsigned long nHashB = HashString(lpszString, HASH_B);

　　unsigned long nHashStart = nHash % m_tablelength,

　　nHashPos = nHashStart;

　　while ( m_HashIndexTable[nHashPos].bExists)

　　{

　　　　nHashPos = (nHashPos + 1) % m_tablelength;

　　　　if (nHashPos == nHashStart) //一個輪迴

　　　　{

　　　　　　//hash表中沒有空餘的位置了,無法完成hash

　　　　　　return false;

　　　　}

　　m_HashIndexTable[nHashPos].bExists = true;

　　m_HashIndexTable[nHashPos].nHashA = nHashA;

　　m_HashIndexTable[nHashPos].nHashB = nHashB;

　　return true;

}