memcached 源码阅读之字符串 hash 与搜集的一些字符串 hash-Mysql Tutorial-php.cn

Home

Database

Mysql Tutorial

memcached 源码阅读之字符串 hash 与搜集的一些字符串 hash

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 07, 2016 pm 04:41 PM

hashmemcachedstringSource coderead

前言在 memcached 源码阅读之 hash table文章的最后我说了，要研究一下 memcached 的字符串 hash 方法的。现在就开始记录下研究的结果。 Jenkins hash jenkins 的位置在 jenkins_hash.c . 大端小端 Little-Endian就是低位字节排放在内存的低地址端，高位

cover

前言

在 memcached 源码阅读之 hash table文章的最后我说了，要研究一下 memcached 的字符串 hash 方法的。
现在就开始记录下研究的结果。

Jenkins hash

jenkins 的位置在 jenkins_hash.c .

大端小端

Little-Endian就是低位字节排放在内存的低地址端，高位字节排放在内存的高地址端。
Big-Endian就是高位字节排放在内存的低地址端，低位字节排放在内存的高地址端。
举一个例子，比如数字0x12 34 56 78在内存中的表示形式为：

1)大端模式：  
低地址 -----------------> 高地址  
0x12  |  0x34  |  0x56  |  0x78  
2)小端模式：  
低地址 ------------------> 高地址  
0x78  |  0x56  |  0x34  |  0x12

#if ENDIAN_BIG == 1
# define HASH_LITTLE_ENDIAN 0
# define HASH_BIG_ENDIAN 1
#else
# if ENDIAN_LITTLE == 1
#  define HASH_LITTLE_ENDIAN 1
#  define HASH_BIG_ENDIAN 0
# else
#  define HASH_LITTLE_ENDIAN 0
#  define HASH_BIG_ENDIAN 0
# endif
#endif

rot 宏

看到的第一个是 rot 宏。
这个宏的作用是循环左移若干位。

#define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k))))

mix 宏

一个可逆的加密。
This is reversible, so any information in (a,b,c) before mix() is still in (a,b,c) after mix().

#define mix(a,b,c) \
{ \
  a -= c;  a ^= rot(c, 4);  c += b; \
  b -= a;  b ^= rot(a, 6);  a += c; \
  c -= b;  c ^= rot(b, 8);  b += a; \
  a -= c;  a ^= rot(c,16);  c += b; \
  b -= a;  b ^= rot(a,19);  a += c; \
  c -= b;  c ^= rot(b, 4);  b += a; \
}

final 宏

final mixing of 3 32-bit values (a,b,c) into c
将 a,b,c 合并到 c中。

#define final(a,b,c) \
{ \
  c ^= b; c -= rot(b,14); \
  a ^= c; a -= rot(c,11); \
  b ^= a; b -= rot(a,25); \
  c ^= b; c -= rot(b,16); \
  a ^= c; a -= rot(c,4);  \
  b ^= a; b -= rot(a,14); \
  c ^= b; c -= rot(b,24); \
}

hash 算法

源代码中大端小端，而且还分是 0x3 还是 0x1，这个目前就不知道干什么了。

uint32_t jenkins_hash( const void *key, size_t length) {
    uint32_t a,b,c;
    a = b = c = 0xdeadbeef + ((uint32_t)length) + 0;
    const char *k = (const char *)key;
    while (length > 12) {
        a += ((uint32_t)k[0])<<24;
        a += ((uint32_t)k[1])<<16;
        a += ((uint32_t)k[2])<<8;
        a += ((uint32_t)k[3]);
        b += ((uint32_t)k[4])<<24;
        b += ((uint32_t)k[5])<<16;
        b += ((uint32_t)k[6])<<8;
        b += ((uint32_t)k[7]);
        c += ((uint32_t)k[8])<<24;
        c += ((uint32_t)k[9])<<16;
        c += ((uint32_t)k[10])<<8;
        c += ((uint32_t)k[11]);
        mix(a,b,c);
        length -= 12;
        k += 12;
    }
    switch(length) {
    case 12:
        c+=k[11];
    case 11:
        c+=((uint32_t)k[10])<<8;
    case 10:
        c+=((uint32_t)k[9])<<16;
    case 9 :
        c+=((uint32_t)k[8])<<24;
    case 8 :
        b+=k[7];
    case 7 :
        b+=((uint32_t)k[6])<<8;
    case 6 :
        b+=((uint32_t)k[5])<<16;
    case 5 :
        b+=((uint32_t)k[4])<<24;
    case 4 :
        a+=k[3];
    case 3 :
        a+=((uint32_t)k[2])<<8;
    case 2 :
        a+=((uint32_t)k[1])<<16;
    case 1 :
        a+=((uint32_t)k[0])<<24;
        break;
    case 0 :
        return c;
    }
    final(a,b,c);
    return c;
}

看完这个代码，我们可以给他缩短一下。

uint32_t jenkins_hash( const void *key, size_t length) {
    uint32_t a,b,c;
    a = b = c = 0xdeadbeef + ((uint32_t)length) + 0;
    const char *k = (const char *)key;
    while (length >= 12) {
        a += *((uint32_t*)(k+0));
        b += *((uint32_t*)(k+4));
        c += *((uint32_t*)(k+8));
        mix(a,b,c);
        length -= 12;
        k += 12;
    }
    if(length == 0) {
        return c;
    }
    switch(length) {
        case 11:
            c+=((uint32_t)k[10])<<8;
        case 10:
            c+=((uint32_t)k[9])<<16;
        case 9 :
            c+=((uint32_t)k[8])<<24;
        case 8 :
            b += *((uint32_t*)(k+4));
            a += *((uint32_t*)(k+0));
            break;
        case 7 :
            b+=((uint32_t)k[6])<<8;
        case 6 :
            b+=((uint32_t)k[5])<<16;
        case 5 :
            b+=((uint32_t)k[4])<<24;
        case 4 :
            a += *((uint32_t*)(k+0));
            break;
        case 3 :
            a+=((uint32_t)k[2])<<8;
        case 2 :
            a+=((uint32_t)k[1])<<16;
        case 1 :
            a+=((uint32_t)k[0])<<24;
    }
    final(a,b,c);
    return c;
}

murmur3 hash

murmur3 hash 的位置在 murmur3_hash.c .

//不检查数据越界问题，主要用于得到一些随机数字
#define    FORCE_INLINE inline __attribute__((always_inline))
//循环左移
static inline uint32_t ROTL32 ( uint32_t x, int8_t r ) {
    return (x << r) | (x >> (32 - r));
}
//得到指针p位置的值，i可能为负数
static FORCE_INLINE uint32_t getblock32 ( const uint32_t * p, int i ) {
    return p[i];
}
static FORCE_INLINE uint32_t fmix32 ( uint32_t h ) {
    h ^= h >> 16;
    h *= 0x85ebca6b;
    h ^= h >> 13;
    h *= 0xc2b2ae35;
    h ^= h >> 16;
    return h;
}
uint32_t MurmurHash3_x86_32 ( const void * key, size_t length) {
    const uint8_t * data = (const uint8_t*)key;
    const int nblocks = length / 4;
    uint32_t h1 = 0;
    uint32_t c1 = 0xcc9e2d51;
    uint32_t c2 = 0x1b873593;
    const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
    for(int i = -nblocks; i; i++) {
        uint32_t k1 = getblock32(blocks,i);
        k1 *= c1;
        k1 = ROTL32(k1,15);
        k1 *= c2;
        h1 ^= k1;
        h1 = ROTL32(h1,13);
        h1 = h1*5+0xe6546b64;
    }
    const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
    uint32_t k1 = 0;
    switch(length & 3) {
        case 3:
            k1 ^= tail[2] << 16;
        case 2:
            k1 ^= tail[1] << 8;
        case 1:
            k1 ^= tail[0];
            k1 *= c1;
            k1 = ROTL32(k1,15);
            k1 *= c2;
            h1 ^= k1;
    };
    h1 ^= length;
    h1 = fmix32(h1);
    return h1;
}

Additive Hash

ub4 additive(char *key, ub4 len, ub4 prime){
    ub4 hash, i;
    for (hash=len, i=0; i<len; ++i) 
        hash += key[i];
    return (hash % prime);
}

Rotating Hash

ub4 rotating(char *key, ub4 len, ub4 prime){
    ub4 hash, i;
    for (hash=len, i=0; i<len; ++i)
        hash = (hash<<4)^(hash>>28)^key[i];
    return (hash % prime);
}

One-at-a-Time Hash

ub4 one_at_a_time(char *key, ub4 len){
    ub4   hash, i;
    for (hash=0, i=0; i<len; ++i){
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return (hash & mask);
}

Bernstein hash

ub4 bernstein(ub1 *key, ub4 len, ub4 level){
    ub4 hash = level;
    ub4 i;
    for (i=0; i<len; ++i) hash = 33*hash + key[i];
    return hash;
}

Goulburn Hash

u4 goulburn( const unsigned char *cp, size_t len, uint32_t last_value){
    register u4 h = last_value;
    int u;
    for( u=0; u<len; ++u ) {
        h += g_table0[ cp[u] ];
        h ^= (h << 3) ^ (h >> 29);
        h += g_table1[ h >> 25 ];
        h ^= (h << 14) ^ (h >> 18);
        h += 1783936964UL;
    }
    return h;
}

Murmur Hash

uint32_t MurmurHash1 ( const void * key, int len, uint32_t seed ){ const unsigned int m = 0xc6a4a793;

const int r = 16;
unsigned int h = seed ^ (len * m);
//----------
const unsigned char * data = (const unsigned char *)key;
while(len >= 4){
    unsigned int k = *(unsigned int *)data;
    h += k;
    h *= m;
    h ^= h >> 16;
    data += 4;
    len -= 4;
}
//----------
switch(len){
    case 3:
    h += data[2] << 16;
    case 2:
    h += data[1] << 8;
    case 1:
    h += data[0];
    h *= m;
    h ^= h >> r;
};
//----------
h *= m;
h ^= h >> 10;
h *= m;
h ^= h >> 17;
return h;

}

Pearson Hash

//This preinitializes tab[] to an arbitrary permutation of 0 .. 255.
char pearson(char *key, ub4 len, char tab[256]){
    char hash;
    ub4  i;
    for (hash=len, i=0; i<len; ++i) 
        hash=tab[hash^key[i]];
    return (hash);
}

CRC Hashing

ub4 crc(char *key, ub4 len, ub4 mask, ub4 tab[256]){
    ub4 hash, i;
    for (hash=len, i=0; i<len; ++i)
        hash = (hash >> 8) ^ tab[(hash & 0xff) ^ key[i]];
    return (hash & mask);
}

Generalized CRC Hashing

//The size of tab[] is the maximum number of input bits. 
//Values in tab[] are chosen at random. 
ub4 universal(char *key, ub4 len, ub4 mask, ub4 tab[MAXBITS]){
    ub4 hash, i;
    for (hash=len, i=0; i<(len<<3); i+=8){
        register char k = key[i>>3];
        if (k&0x01) hash ^= tab[i+0];
        if (k&0x02) hash ^= tab[i+1];
        if (k&0x04) hash ^= tab[i+2];
        if (k&0x08) hash ^= tab[i+3];
        if (k&0x10) hash ^= tab[i+4];
        if (k&0x20) hash ^= tab[i+5];
        if (k&0x40) hash ^= tab[i+6];
        if (k&0x80) hash ^= tab[i+7];
    }
    return (hash & mask);
}

Zobrist Hashing

ub4 zobrist( char *key, ub4 len, ub4 mask, ub4 tab[MAXBYTES][256]){
    ub4 hash, i;
    for (hash=len, i=0; i<len; ++i)
        hash ^= tab[i][key[i]];
    return (hash & mask);
}

本文出自：http://tiankonguse.github.io, 原文地址：http://github.tiankonguse.com//blog/2014/11/07/memcached-string-hash/, 感谢原作者分享。

Statement

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Memcached缓存技术对于PHP中的Session处理的优化May 16, 2023 am 08:41 AM

Memcached是一种常用的缓存技术，它可以使Web应用程序的性能得到很大的提升。在PHP中，常用的Session处理方式是将Session文件存放在服务器的硬盘上。但是，这种方式并不是最优的，因为服务器的硬盘会成为性能瓶颈之一。而使用Memcached缓存技术可以对PHP中的Session处理进行优化，提高Web应用程序的性能。PHP中的Session处

PHP8.0中的缓存库：MemcachedMay 14, 2023 am 08:16 AM

PHP8.0中的缓存库：Memcached随着互联网的快速发展，现代应用程序需要高效可靠的缓存技术来提高性能和处理大量数据。由于PHP的流行和开源特性，PHP缓存库已经成为了Web开发社区的一个必备工具。Memcached是一种广泛使用的开源高速内存缓存系统，它能处理数百万个同时连接的缓存请求，可以用于许多不同类型的应用程序，例如社交网络、在线

PHP与Memcached数据库备份与恢复May 15, 2023 pm 09:12 PM

随着互联网的快速发展，大规模MySQL数据库备份和恢复成为各大企业和网站必备的技能之一。而随着Memcached的广泛应用，如何备份和恢复Memcached也成为了一个重要的问题。PHP作为Web开发的主力语言之一，在处理备份和恢复MySQL和Memcached上拥有独特的优势和技巧。本文将详细介绍PHP处理MySQL和Memcached备份与恢复的实现方法

利用Memcached缓存技术对于PHP中的音视频播放进行优化May 17, 2023 pm 04:01 PM

随着互联网技术的不断发展，音视频资源已经成为了互联网上非常重要的一种内容形式，而PHP作为网络开发中使用最广泛的语言之一，也在不断地应用于视频和音频播放领域。然而，随着音视频网站的用户日益增加，许多网站已经发现了一个问题：在高并发的情况下，PHP对于音视频的处理速度明显变缓，会导致无法及时播放或者播放卡顿等问题。为了解决这个问题，Memcached缓存技术应

使用PHP和Memcached进行缓存管理May 23, 2023 pm 02:21 PM

随着网络应用的不断增加和数据量的不断膨胀，数据的读写效率成为影响应用性能的重要因素之一。而缓存技术的应用则可以很好地解决这个问题。在PHP应用中，Memcached是最常用的缓存服务器。Memcached是一个高性能的分布式内存对象缓存系统，可以将常用的数据存储在内存中，提高数据检索的效率。本文将介绍如何使用PHP和Memcached进行缓存管理，以及如何优

PHP与Memcached性能监控May 15, 2023 pm 09:51 PM

随着现代互联网应用的快速发展，用户体验对于一个应用的成功至关重要。如何保证应用的高性能和高可用性，成为了开发人员需要解决的重要问题之一。PHP作为一种广泛应用的编程语言之一，它的性能监控和优化也是非常重要的。Memcached是一个高性能、分布式的内存对象缓存系统，可以帮助应用提高性能和扩展性。本文将介绍如何使用PHP和Memcached实现性能监控的方法。

PHP实现Memcached数据库集群的方法May 15, 2023 pm 03:31 PM

随着互联网应用的快速发展，数据存储和处理变得越来越庞大和复杂。在这样的背景下，Memcached作为一款高性能、轻量级的分布式内存缓存系统，逐渐成为互联网应用领域中不可或缺的一部分。在PHP语言中，Memcached可以通过扩展内置的Memcached类实现与Memcached服务器的交互，而在实际生产环境中，我们需要通过搭建Memcached数据库集群来保

使用宝塔面板进行Redis、Memcached等缓存服务器的部署Jun 21, 2023 am 09:56 AM

随着互联网的发展，缓存技术在Web开发中扮演着越来越重要的角色。Redis和Memcached作为两种流行的缓存服务器，被广泛应用于各种Web应用开发中。然而，对于不熟悉Linux系统的开发人员来说，安装和配置这些缓存服务器可能会带来一些麻烦。但是，在宝塔面板的帮助下，这一过程将变得相当简单。一、什么是宝塔面板？宝塔面板是一款Linux服务器管理面板，它可以

See all articles