memcached 源码阅读之 字符串 hash 与 搜集的一些 字符串 hash
前言 在 memcached 源码阅读之 hash table文章的最后我说了,要研究一下 memcached 的 字符串 hash 方法的。 现在就开始记录下研究的结果。 Jenkins hash jenkins 的位置在 jenkins_hash.c . 大端小端 Little-Endian就是低位字节排放在内存的低地址端,高位
前言
在 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/, 感谢原作者分享。

Heiße KI -Werkzeuge

Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool
Ausziehbilder kostenlos

Clothoff.io
KI-Kleiderentferner

AI Hentai Generator
Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

Heiße Werkzeuge

Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6
Visuelle Webentwicklungstools

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen

Ausführliche Erläuterung der Methode zum Konvertieren des Typs int in einen String in PHP. Bei der PHP-Entwicklung stoßen wir häufig auf die Notwendigkeit, den Typ int in einen String-Typ zu konvertieren. Diese Konvertierung kann auf verschiedene Weise erreicht werden. In diesem Artikel werden verschiedene gängige Methoden im Detail vorgestellt, mit spezifischen Codebeispielen, um den Lesern das Verständnis zu erleichtern. 1. Verwenden Sie die integrierte Funktion strval() von PHP. PHP bietet eine integrierte Funktion strval(), die Variablen verschiedener Typen in String-Typen konvertieren kann. Wenn wir den Typ int in den Typ string konvertieren müssen,

In diesem Artikel zeigen wir Ihnen, wie Sie Microsoft Reading Coach im Immersive Reader auf einem Windows-PC verwenden. Lesehilfefunktionen helfen Schülern oder Einzelpersonen dabei, das Lesen zu üben und ihre Lese- und Schreibfähigkeiten zu entwickeln. Sie beginnen mit dem Lesen einer Passage oder eines Dokuments in einer unterstützten Anwendung. Auf dieser Grundlage wird Ihr Lesebericht vom Reading Coach-Tool erstellt. Der Lesebericht zeigt Ihre Lesegenauigkeit, die Zeit, die Sie zum Lesen benötigt haben, die Anzahl der richtigen Wörter pro Minute und die Wörter, die Sie beim Lesen am schwierigsten fanden. Sie können auch die Wörter üben, was Ihnen dabei hilft, Ihre Lesefähigkeiten im Allgemeinen zu verbessern. Derzeit nur Office oder Microsoft365 (einschließlich OneNote for Web und Word for We

Wie kann man in Golang überprüfen, ob eine Zeichenfolge mit einem bestimmten Zeichen beginnt? Beim Programmieren in Golang kommt es häufig vor, dass Sie prüfen müssen, ob eine Zeichenfolge mit einem bestimmten Zeichen beginnt. Um diese Anforderung zu erfüllen, können wir die vom Strings-Paket in Golang bereitgestellten Funktionen verwenden, um dies zu erreichen. Als Nächstes stellen wir anhand spezifischer Codebeispiele ausführlich vor, wie Sie mit Golang überprüfen können, ob eine Zeichenfolge mit einem bestimmten Zeichen beginnt. In Golang können wir HasPrefix aus dem Strings-Paket verwenden

Titel: So ermitteln Sie, ob eine Zeichenfolge in Golang mit einem bestimmten Zeichen endet. In der Go-Sprache müssen wir manchmal feststellen, ob eine Zeichenfolge mit einem bestimmten Zeichen endet. In diesem Artikel wird erläutert, wie Sie diese Funktion mithilfe der Go-Sprache implementieren, und es werden Codebeispiele als Referenz bereitgestellt. Schauen wir uns zunächst an, wie Sie in Golang feststellen können, ob eine Zeichenfolge mit einem bestimmten Zeichen endet. Die Zeichen in einer Zeichenfolge in Golang können durch Indizierung ermittelt werden, und die Länge der Zeichenfolge kann ermittelt werden

1. Öffnen Sie zuerst Pycharm und rufen Sie die Pycharm-Homepage auf. 2. Erstellen Sie dann ein neues Python-Skript, klicken Sie mit der rechten Maustaste – klicken Sie auf „Neu“ – klicken Sie auf „Pythondatei“. 3. Geben Sie eine Zeichenfolge ein, Code: s="-". 4. Dann müssen Sie die Symbole in der Zeichenfolge 20 Mal wiederholen, Code: s1=s*20 5. Geben Sie den Druckausgabecode ein, Code: print(s1). 6. Führen Sie abschließend das Skript aus und Sie sehen unten unseren Rückgabewert: - 20 Mal wiederholt.

Methoden zur Lösung des Problems verstümmelter chinesischer Zeichen beim Konvertieren von Hexadezimalzeichenfolgen in PHP. Bei der PHP-Programmierung stoßen wir manchmal auf Situationen, in denen wir Hexadezimalzeichenfolgen in normale chinesische Zeichen konvertieren müssen. Bei dieser Konvertierung treten jedoch manchmal Probleme mit verstümmelten chinesischen Zeichen auf. In diesem Artikel finden Sie eine Methode zur Lösung des Problems verstümmelter chinesischer Zeichen bei der Konvertierung von Hexadezimalzahlen in Zeichenfolgen in PHP sowie spezifische Codebeispiele. Verwenden Sie die Funktion hex2bin() für die Hexadezimalkonvertierung. Die in PHP integrierte Funktion hex2bin() kann 1 konvertieren

Tipps zum PHP-String-Matching: Vermeiden Sie mehrdeutige eingeschlossene Ausdrücke. In der PHP-Entwicklung ist der String-Matching eine häufige Aufgabe, die normalerweise verwendet wird, um bestimmte Textinhalte zu finden oder das Eingabeformat zu überprüfen. Manchmal müssen wir jedoch die Verwendung mehrdeutiger Einschlussausdrücke vermeiden, um die Übereinstimmungsgenauigkeit sicherzustellen. In diesem Artikel werden einige Techniken zur Vermeidung mehrdeutiger Einschlussausdrücke beim String-Matching in PHP vorgestellt und spezifische Codebeispiele bereitgestellt. Verwenden Sie die Funktion preg_match() für den exakten Abgleich. In PHP können Sie preg_mat verwenden

PHP-String-Operation: Eine praktische Methode zum effektiven Entfernen von Leerzeichen Bei der PHP-Entwicklung kommt es häufig vor, dass Sie Leerzeichen aus einem String entfernen müssen. Das Entfernen von Leerzeichen kann die Zeichenfolge sauberer machen und die nachfolgende Datenverarbeitung und -anzeige erleichtern. In diesem Artikel werden mehrere effektive und praktische Methoden zum Entfernen von Leerzeichen vorgestellt und spezifische Codebeispiele angehängt. Methode 1: Verwenden Sie die in PHP integrierte Funktion trim(). Die in PHP integrierte Funktion trim() kann Leerzeichen an beiden Enden der Zeichenfolge entfernen (einschließlich Leerzeichen, Tabulatoren, Zeilenumbrüche usw.), was sehr praktisch und einfach ist benutzen.
