0. Vorwort
Redis ist eine Speicherdatenbank vom Typ KV. Der Kern der Datenbankspeicherung ist die Hash-Tabelle , Alle Operationen basieren auf der Hash-Tabelle. Die Hash-Datenstruktur und die Implementierung von Redis werden unten analysiert.
1.Hash-Datenstruktur
/*Hash表一个节点包含Key,Value数据对 */
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; /* 指向下一个节点, 链接表的方式解决Hash冲突 */
} dictEntry;
/* 存储不同数据类型对应不同操作的回调函数 */
typedef struct dictType {
unsigned int (*hashFunction)(const void *key);
void *(*keyDup)(void *privdata, const void *key);
void *(*valDup)(void *privdata, const void *obj);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
void (*keyDestructor)(void *privdata, void *key);
void (*valDestructor)(void *privdata, void *obj);
} dictType;
typedef struct dictht {
dictEntry **table; /* dictEntry*数组,Hash表 */
unsigned long size; /* Hash表总大小 */
unsigned long sizemask; /* 计算在table中索引的掩码, 值是size-1 */
unsigned long used; /* Hash表已使用的大小 */
} dictht;
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2]; /* 两个hash表,rehash时使用*/
long rehashidx; /* rehash的索引, -1表示没有进行rehash */
int iterators; /* */
} dict;Nach dem Login kopieren
2.Hash-Datenstrukturdiagramm
3. Progressive Hash-Beschreibung
Es gibt zwei Hash-Tabellen in ht[2] in dict ] Eine Hash-Tabelle mit einer Mindestgröße von 4 wird erstellt. Sobald size und used in ht[0] gleich sind, wird in ht[1] eine Hash-Tabelle der Größe*2 erstellt. werden nicht direkt verwendet. Die Daten in 0] werden in ht[0] kopiert und ein progressiver Rehash durchgeführt, das heißt, sie werden langsam in nachfolgende Vorgänge (Suchen, Festlegen, Abrufen usw.) und neu hinzugefügte Elemente kopiert wird in Zukunft zu ht[0] hinzugefügt. Wenn also ht[1] voll ist, werden alle Daten in ht[0] nach ht[1] kopiert.
4 . Erstellen Sie eine Hash-Tabelle.
Der Vorgang zum Erstellen einer Hash-Tabelle ist sehr einfach. Rufen Sie einfach die Funktion dictCreate auf und initialisieren Sie Zwischenvariablen.
dict *dictCreate(dictType *type, void *privDataPtr)
{
/*分配内存*/
dict *d = zmalloc(sizeof(*d));
/*初始化操作*/
_dictInit(d,type,privDataPtr);
return d;
}Nach dem Login kopieren
5
Um Elemente zur Hash-Tabelle hinzuzufügen, bestimmen Sie zunächst, ob der Platz ausreicht, berechnen Sie dann den Hash-Wert, der dem Schlüssel entspricht, und geben Sie dann den Schlüssel und den Wert ein, die hinzugefügt werden müssen, in die Tabelle.
int dictAdd(dict *d, void *key, void *val)
{
/*添加入hash表中, 返回新添加元素的实体结构体*/
dictEntry *entry = dictAddRaw(d,key);
if (!entry) return DICT_ERR;
/*元素val值放入元素实体结构中*/
dictSetVal(d, entry, val);
return DICT_OK;
}
/*
*添加元素实体函数
*/
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d);
/*根据key值计算新元素在hash表中的索引, 返回-1则表示元素已存在, 直接返回NULL*/
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;
/*如果在进行rehash过程,则新元素添加到ht[1]中, 否则添加到ht[0]中 */
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
/*设置元素key*/
dictSetKey(d, entry, key);
return entry;
}
/*
*计算索引的函数
*/
static int _dictKeyIndex(dict *d, const void *key)
{
unsigned int h, idx, table;
dictEntry *he;
/* 判断hash表是否空间足够, 不足则需要扩展 */
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
/* 计算key对应的hash值 */
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
/*计算索引*/
idx = h & d->ht[table].sizemask;
/*遍历冲突列表, 判断需要查找的key是否已经在冲突列表中*/
he = d->ht[table].table[idx];
while(he) {
if (dictCompareKeys(d, key, he->key))
return -1;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return idx;
}
/*
*判断hash表是否需要扩展空间
*/
static int _dictExpandIfNeeded(dict *d)
{
/*redis的rehash采用的渐进式hash, rehash时分配了原来两倍的内存空间, 在rehash阶段空间必定够用*/
if (dictIsRehashing(d)) return DICT_OK;
/* hash表是空的需要初始化空间, 默认是4*/
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
/* 已使用空间满足不了设置的条件*/
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
/*扩展空间, 使用空间的两倍*/
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}
/*
*扩展空间或者初始化hash表空间
*/
int dictExpand(dict *d, unsigned long size)
{
dictht n;
/* 对需要分配大小圆整为2的倍数 */
unsigned long realsize = _dictNextPower(size);
/* 如果空间足够则表明调用错误 */
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;
/*hash表为空初始化hash表*/
if (d->ht[0].table == NULL) {
d->ht[0] = n;
return DICT_OK;
}
/*新分配的空间放入ht[1], 后面一步一步进行rehash*/
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;
}Nach dem Login kopieren
6. Finden Sie das Element
Der Prozess zum Suchen des Elements besteht darin, zuerst den Hash-Wert zu berechnen und dann die Indexposition in ht[0] und ht[1] zu berechnen und zu suchen.
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
unsigned int h, idx, table;
if (d->ht[0].size == 0) return NULL;
/*如果正在进行rehash, 执行一次rehash*/
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
/*由于可能正在rehash, 因此要从ht[0]和ht[1]中分别进行查找, 找不到返回NULL*/
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
/*遍历冲突列表查找元素*/
while(he) {
if (dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}Nach dem Login kopieren
7. Element löschen
Um ein Element zu löschen, suchen Sie zuerst nach dem Element und entfernen Sie dann das Element aus der Hash-Tabelle. Das war's. Durch den Aufruf von dictDelete zum Löschen eines Elements wird auch das Leerzeichen gelöscht Besetzt durch das Element
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0);
}
static int dictGenericDelete(dict *d, const void *key, int nofree)
{
unsigned int h, idx;
dictEntry *he, *prevHe;
int table;
if (d->ht[0].size == 0) return DICT_ERR;
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
prevHe = NULL;
/*查找元素到元素,进行删除操作, 并释放占用的内存*/
while(he) {
if (dictCompareKeys(d, key, he->key)) {
/* Unlink the element from the list */
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
if (!nofree) {
dictFreeKey(d, he);
dictFreeVal(d, he);
}
zfree(he);
d->ht[table].used--;
return DICT_OK;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return DICT_ERR; /* not found */
}Nach dem Login kopieren
Hash-Befehl
Hash-Befehlsoperation ist relativ einfach. Es sollte beachtet werden, dass es sich bei der Erstellung eines Hashs zur Darstellung der Standardspeicherstruktur nicht um ein Diktat handelt Eine Ziplist-Struktur. Sie können sich auf die Ziplist-Datenstruktur von redis beziehen. Die Werte hash_max_ziplist_value werden als Schwellenwerte verwendet, was bedeutet, dass die Anzahl der Elemente in der Ziplist konvertiert werden muss in eine Diktstruktur; hash_max_ziplist_value Gibt an, dass die Datenlänge in der Ziplist, sobald sie diesen Wert überschreitet, in eine Diktstruktur konvertiert werden muss.
Weitere technische Artikel zum Thema Redis finden Sie in der Spalte
Redis-Tutorial, um mehr zu erfahren!
Das obige ist der detaillierte Inhalt vonSo implementieren Sie Redis-Hash. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
