Redis 해시를 구현하는 방법

步履不停
풀어 주다: 2019-06-24 11:14:53
원래의
2928명이 탐색했습니다.

Redis 해시를 구현하는 방법

0. 서문

redis는 KV형 인메모리 데이터베이스입니다. 데이터베이스 저장소의 핵심은 Hash 테이블을 사용하여 저장된 db를 선택하는 것입니다. 다음은 redis의 해시 데이터 구조와 구현을 분석합니다.

1.hash 데이터 구조

/*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;
로그인 후 복사

2.hash 데이터 구조 다이어그램

Redis 해시를 구현하는 방법

3. 프로그레시브 해시 설명

ht[2]에는 두 개의 해시가 있습니다. dict 테이블에서 처음으로 데이터를 저장할 때 ht[0]은 최소 4개의 해시 테이블을 생성합니다. ht[0]에서 사용된 크기와 크기가 동일하면 ht[에 크기가 생성됩니다. 1] dict *2 크기 해시 테이블에서 이때 ht[0]의 데이터는 ht[0]에 직접 복사되지 않지만 후속 작업(find, set)에서 점진적인 재해시가 수행됩니다. , get 등) 천천히 복사하면 새로 추가된 요소가 앞으로 ht[0]에 추가됩니다. 따라서 ht[1]이 가득 차면 ht[0]에 있는 모든 데이터가 확실해집니다. ]는 ht[1]에 복사됩니다.

4. 해시 테이블 생성

해시 테이블 생성 과정은 매우 간단합니다. dictCreate 함수를 호출하고, 메모리를 할당하고, 중간 변수를 초기화하면 됩니다.

dict *dictCreate(dictType *type, void *privDataPtr)
{
     /*分配内存*/
    dict *d = zmalloc(sizeof(*d));
     /*初始化操作*/
    _dictInit(d,type,privDataPtr);
    return d;
}
로그인 후 복사

5. 요소 추가

해시 테이블에 요소를 추가하려면 먼저 공간이 충분한지 확인한 다음 키에 해당하는 해시 값을 계산한 다음 추가해야 할 키와 값을 테이블에 넣습니다.

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;
}
로그인 후 복사

6. 요소 찾기

요소를 찾는 과정은 먼저 해시 값을 계산한 다음 ht[0]과 ht 사이의 값을 계산합니다. [1]의 인덱스 위치에서 검색합니다.

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;
}
로그인 후 복사

7. elements

요소를 삭제하려면 먼저 해당 요소를 검색한 후 해시 테이블에서 요소를 제거하세요. dictDelete를 호출하여 요소를 삭제하면 해당 요소가 차지한 공간도 동시에 삭제됩니다

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 */
}
로그인 후 복사

hash 명령

hash 명령 작업은 비교적 간단합니다. 해시를 생성할 때 이는 dict가 아닌 ziplist 구조를 나타내는 기본 저장 구조를 나타냅니다. redis의 Ziplist 데이터 구조를 참조할 수 있습니다. , hash_max_ziplist_entries 및 hash_max_ziplist_value 값을 임계값으로, hash_max_ziplist_entries는 ziplist의 요소 수가 이 값을 초과하면 dict 구조로 변환해야 함을 의미합니다. hash_max_ziplist_value는 ziplist의 데이터 길이가 이 값보다 크다는 것을 의미합니다. , dict 구조로 변환해야 합니다.

더 많은 Redis 관련 기술 기사를 보려면 Redis Tutorial 칼럼을 방문하여 알아보세요!

위 내용은 Redis 해시를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿