Node* conflict_node = bucket->head_node_; while(conflict_node) { conflict_count++; if (CmpKey(conflict_node->key_, key_data)) {//冲突时释放之前的,重新保存新的 if(conflict_node->value_==value) {//先测试后再确认是否可以; exist_flag_ = 200; SetConflictCount(INSERT_TYPE, conflict_count); return conflict_node; } value_mem->ReleaseOneValue(conflict_node->value_->node_ptr_);//此处存在问题,conflict_node->value_==value时,会将value放至free列表,但是后面又调用value->use_count_++,会导致在free列表中但是又在hash使用中; Value* new_value = NULL; if (!value) { new_value = value_mem->ApplyOneValue(1); } else { /* *入口处提到的问题 *如果此时@param value与conflict_node->value_是同一个指针的话 *value_mem->ReleaseOneValue后,在HashValue中它已经被标记为 *未使用并归还至可用链表中,而下一行代码则会让hashmap通过key仍能 *访问@param value对应的内存。这与设计不符 */ new_value = value; new_value->use_count_++; } if (!new_value) { return NULL; } conflict_node->value_ = new_value; exist_flag_ = 200; SetConflictCount(INSERT_TYPE, conflict_count); return conflict_node; } conflict_node = conflict_node->next_node_; }什么意思
时间: 2024-02-10 14:23:02 浏览: 30
这段代码是在哈希表中处理冲突的情况。如果哈希桶中已经存在节点且键值与插入的键值相同,则需要更新节点的值。如果节点的值指针与插入的值指针相同,则不需要更新,直接返回该节点。否则,需要申请一个新的值,并将原来的值释放。如果申请新值失败,则返回空指针。最后,更新节点的值和标记,返回该节点。
如果存在冲突节点,但是键值与插入的键值不同,则需要继续查找下一个节点,直到找到键值相同的节点或者遍历完整个链表。
相关问题
//未发现冲突,直接保存 Value* new_value = NULL; Node* new_node = ApplyForOneNode(); Node* old_head = bucket->head_node_; if (new_node == NULL) { return NULL; } if (!value) { new_value = value_mem->ApplyOneValue(1); } else { new_value = value; new_value->use_count_++; } if (new_value == NULL) { return NULL; } bucket->head_node_ = new_node; bucket->head_node_->next_node_ = old_head; bucket->head_node_->value_ = new_value; DupKey(new_node->key_, key_data); SetConflictCount(INSERT_TYPE, conflict_count); return bucket->head_node_;什么意思
这段代码是一个哈希表中插入元素的函数实现。具体来说,它执行以下操作:
1. 申请一个新的节点new_node;
2. 暂存bucket的原始头节点old_head;
3. 如果value为空,就申请一个新的value并将其赋值给new_value,否则将value赋值给new_value并增加其引用计数;
4. 将new_node作为新的头节点赋值给bucket,并将其next_node指向原始头节点old_head;
5. 将new_value赋值给new_node的value_;
6. 复制key_data到new_node的key_;
7. 调用SetConflictCount函数来设置哈希表中的冲突计数;
8. 返回新的头节点bucket->head_node_。
其中,ApplyForOneNode和ApplyOneValue是分别用来申请节点和值的内存的函数。这个函数的主要目的是将一个新的键值对插入到哈希表中,并返回插入后的头节点。
Node* Select(Key& key_data, uint32_t key_hash, EditType type = SELECT_TYPE, HashValue<Value>* value_mem = NULL, Value* value = NULL) { Bucket* bucket = hash_bucket_ + key_hash; int conflict_count = 0; if (bucket->head_node_ == NULL) { SetConflictCount(SELECT_TYPE, conflict_count); return NULL; } Node* cur_node = bucket->head_node_; while (cur_node) { conflict_count++; if (CmpKey(cur_node->key_, key_data)) { SetConflictCount(SELECT_TYPE, conflict_count); return cur_node; } cur_node = cur_node->next_node_; } SetConflictCount(SELECT_TYPE, conflict_count); return NULL; }什么意思
这段代码是一个哈希表的查找函数,其中:
- `key_data` 是要查找的关键字;
- `key_hash` 是 `key_data` 的哈希值;
- `type` 参数表示查找类型,这里默认为 `SELECT_TYPE`,表示查找操作;
- `value_mem` 和 `value` 参数用于返回查找结果,其中 `value_mem` 是一个指向内存池中空闲位置的指针,`value` 则是一个指向要查找的值的指针。
函数的具体实现如下:
- 首先,从哈希桶中取出与 `key_hash` 对应的桶;
- 如果该桶中没有任何节点,则直接返回 `NULL`;
- 否则,遍历该桶中所有节点,查找与 `key_data` 相等的节点;
- 如果找到了,则返回该节点;
- 如果遍历完了所有节点,都没有找到,则返回 `NULL`。
在查找过程中,函数会统计冲突次数,最后将其记录下来。