Algorithm of string:: hash?
Posted: 29 Jun 2018 17:08
What algorithm is used by function string::hash?
Visual Prolog Discussion forums
https://discuss.visual-prolog.com/
Code: Select all
implement string
open core, string_native
...
clauses
hash(String) = hash_native::hashValueString(String).
and in hash_native you can see
class hash_native
open core
predicates
hashValueString : (string String) -> unsigned HashValue
language apicall as runtimeLinkNamesRun::hashValueString.
% @short Obtain a #HashValue from a #String.
% @end
Code: Select all
//-----------------------------------------------------------------------------
// CMurmurHash2A, by Austin Appleby
// This is a sample implementation of MurmurHash2A designed to work
// incrementally.
// Usage -
// CMurmurHash2A hasher
// hasher.Begin(seed);
// hasher.Add(data1,size1);
// hasher.Add(data2,size2);
// ...
// hasher.Add(dataN,sizeN);
// hashValue_t hash = hasher.End()
#define mmix(h,k) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; }
typedef unsigned int uint32_t;
class CMurmurHash2A
{
public:
static void * operator new(size_t Size){
return Kernel::AllocAtomicHeap(Size);
}
public:
CMurmurHash2A(hashValue_t seed = 0)
{
m_hash = seed;
m_tail = 0;
m_count = 0;
m_size = 0;
}
void Add(const unsigned char * data, int len)
{
m_size += len;
MixTail(data, len);
while (len >= 4) {
uint32_t k = *(uint32_t*)data;
mmix(m_hash, k);
data += 4;
len -= 4;
}
MixTail(data, len);
}
uint32_t End(void)
{
mmix(m_hash, m_tail);
mmix(m_hash, m_size);
m_hash ^= m_hash >> 13;
m_hash *= m;
m_hash ^= m_hash >> 15;
return m_hash;
}
private:
static const uint32_t m = 0x5bd1e995;
static const int r = 24;
void MixTail(const unsigned char * & data, int & len)
{
while (len && ((len<4) || m_count)) {
m_tail |= (*data++) << (m_count * 8);
m_count++;
len--;
if (m_count == 4) {
mmix(m_hash, m_tail);
m_tail = 0;
m_count = 0;
}
}
}
uint32_t m_hash;
uint32_t m_tail;
uint32_t m_count;
uint32_t m_size;
};