当前位置：首页 > news >正文

静态网站是什么样网络营销的方式

news 2025/7/29 6:33:42

静态网站是什么样,网络营销的方式,源代码代做网站,晋江网站建设公司字典也叫哈希表。看一下redis中的实现。下面是数据结构关系图。 redis中，哈希表的设计思想是，申请一个指针数组，然后每个元素指向一个链表用来存储数据（即链地址法）。 1 创建一个字典 // 申请一个表示字典的数据结构…

字典也叫哈希表。看一下redis中的实现。下面是数据结构关系图。

redis中，哈希表的设计思想是，申请一个指针数组，然后每个元素指向一个链表用来存储数据（即链地址法）。

1 创建一个字典

// 申请一个表示字典的数据结构
dict *dictCreate(dictType *type,void *privDataPtr)
{dict *ht = _dictAlloc(sizeof(*ht));_dictInit(ht,type,privDataPtr);return ht;
} // 初始化字典数据结构
int _dictInit(dict *ht, dictType *type,void *privDataPtr)
{_dictReset(ht);ht->type = type;ht->privdata = privDataPtr;return DICT_OK;
}// 扩容
int dictResize(dict *ht)
{int minimal = ht->used;if (minimal < DICT_HT_INITIAL_SIZE)minimal = DICT_HT_INITIAL_SIZE;return dictExpand(ht, minimal);
}

首先调用申请一个dict结构体用来表示一个字典。然后初始化他的相关字段，最后调用dictExpand开辟保存数据的内存。

int dictExpand(dict *ht, unsigned long size)
{dict n; // size是数组元素的个数，需要是2的倍数unsigned long realsize = _dictNextPower(size), i;_dictInit(&n, ht->type, ht->privdata);// 哈希表数组的长度n.size = realsize;// 索引掩码，用于计算索引n.sizemask = realsize-1;// 用作哈希表的指针数组n.table = _dictAlloc(realsize*sizeof(dictEntry*));// 初始化内存为0memset(n.table, 0, realsize*sizeof(dictEntry*));// 之前字典已经使用的项数，复制过来，used是字典里节点个数n.used = ht->used;for (i = 0; i < ht->size && ht->used > 0; i++) {dictEntry *he, *nextHe;// 空项，不需要复制if (ht->table[i] == NULL) continue;he = ht->table[i];while(he) {unsigned int h;// 保存下一个节点的地址，table的每一个项都是一个链表nextHe = he->next;  /* Get the new element index */// 重新计算he的索引h = dictHashKey(ht, he->key) & n.sizemask;// 插入索引为h的字典项中，头插法he->next = n.table[h];n.table[h] = he;// 使用数减一ht->used--;he = nextHe;}}assert(ht->used == 0);// 释放旧的内存_dictFree(ht->table);// 覆盖之前的信息*ht = n;return DICT_OK;
}

这样就形成了一个和文章开始那个图一样的结构。

2 往字典加入一个元素

int dictAdd(dict *ht, void *key, void *val)
{int index;dictEntry *entry;// 计算key是否已经存在，不存在则返回key对应的索引if ((index = _dictKeyIndex(ht, key)) == -1)return DICT_ERR;// 申请一个字典项entry = _dictAlloc(sizeof(*entry));// 头插法插入第index项对应的链表中entry->next = ht->table[index];ht->table[index] = entry;// 设置键值dictSetHashKey(ht, entry, key);dictSetHashVal(ht, entry, val);// 节点数加一ht->used++;return DICT_OK;
}

1 首先判断key是否已经存在，存在的话就无法添加。
2 根据key和哈希函数，计算对应的索引。
3 头插法插入对应索引的链表。

3 修改某个key对应的值

int dictReplace(dict *ht, void *key, void *val)
{dictEntry *entry;// 尝试新增，成功说明之前还没有这个key，否则说明存在，下面再替换if (dictAdd(ht, key, val) == DICT_OK)return DICT_OK;// 找到key对应的索引entry = dictFind(ht, key);// 释放当前的valuedictFreeEntryVal(ht, entry);// 重新设置新值dictSetHashVal(ht, entry, val);return DICT_OK;
}

4 删除一个元素

static int dictGenericDelete(dict *ht, const void *key, int nofree)
{unsigned int h;dictEntry *he, *prevHe;// 空字典if (ht->size == 0)return DICT_ERR;// 算出索引h = dictHashKey(ht, key) & ht->sizemask;// 拿到索引对应的链表he = ht->table[h];prevHe = NULL;while(he) {// 比较key，找到返回trueif (dictCompareHashKeys(ht, key, he->key)) {/* Unlink the element from the list */// 上一个不匹配节点的next指针指向待删除节点的下一个节点if (prevHe)prevHe->next = he->next;else// prevHe为空，说明待删除的节点是链表的第一个节点，则更新头指针指向待删除节点的下一个ht->table[h] = he->next;// if (!nofree) {dictFreeEntryKey(ht, he);dictFreeEntryVal(ht, he);}// 删除这个节点_dictFree(he);// 已使用个数减一ht->used--;return DICT_OK;}// 保存上一个不匹配的prevHe = he;he = he->next;}return DICT_ERR; /* not found */
}

首先根据key找到索引的对应的链表，然后遍历链表找到key一样的节点，最后就是从链表中删除一个节点。
新增和删除等操作都涉及到查找元素，我们看看怎么查找。

5 查找

dictEntry *dictFind(dict *ht, const void *key)
{dictEntry *he;unsigned int h;if (ht->size == 0) return NULL;// 自定义的哈希函数钩子h = dictHashKey(ht, key) & ht->sizemask;he = ht->table[h];while(he) {// 自定义的比较函数钩子if (dictCompareHashKeys(ht, key, he->key))return he;he = he->next;}return NULL;
}

我们可以看一下某个钩子的实现。

// 哈希函数
unsigned int dictGenHashFunction(const unsigned char *buf, int len) {unsigned int hash = 5381;while (len--)hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */return hash;
}
// 比较函数
static int _dictStringCopyHTKeyCompare(void *privdata, const void *key1,const void *key2)
{return strcmp(key1, key2) == 0;
}

总来的流程就是根据key产生一个索引，然后根据索引到哈希表中取得对应的一个链表，然后操作这个链表（新增，查找，删除）。

6 销毁字典

// 销毁整个字典
int _dictClear(dict *ht)
{unsigned long i;/* Free all the elements */for (i = 0; i < ht->size && ht->used > 0; i++) {dictEntry *he, *nextHe;// 空闲项，跳过if ((he = ht->table[i]) == NULL) continue;// while(he) {// 先保存下一个节点地址，不然下面内存被释放就找不到了nextHe = he->next;// 释放键内存dictFreeEntryKey(ht, he);// 释放值内存dictFreeEntryVal(ht, he);// 释放节点内存_dictFree(he);// 使用数减一ht->used--;he = nextHe;}}/* Free the table and the allocated cache structure */// 释放字典结构体_dictFree(ht->table);/* Re-initialize the table */// 重置字段_dictReset(ht);return DICT_OK; /* never fails */
}

该函数只是释放字典里存储数据的内存，但是没有释放字典本身。下面函数可以释放字典本身的内存。

// 释放字典里的数据和字典本身
void dictRelease(dict *ht)
{_dictClear(ht);_dictFree(ht);
}

7 迭代字典
redis中实现了各种迭代器对某种数据结构进行迭代，比如字典。

// 申请字典迭代器
dictIterator *dictGetIterator(dict *ht)
{dictIterator *iter = _dictAlloc(sizeof(*iter));iter->ht = ht;iter->index = -1;iter->entry = NULL;iter->nextEntry = NULL;return iter;
}
// 迭代字典的元素，每次调用返回一个节点
dictEntry *dictNext(dictIterator *iter)
{while (1) {// 初始化时entry为NULLif (iter->entry == NULL) {iter->index++;// 到底了才break，而不是entry为空if (iter->index >=(signed)iter->ht->size) break;// 返回索引为0对应的链表iter->entry = iter->ht->table[iter->index];} else {iter->entry = iter->nextEntry;}// 还有节点，则同时记录下一个节，返回entry节点if (iter->entry) {iter->nextEntry = iter->entry->next;return iter->entry;}}return NULL;
}