当装载因子接近1时,哪种哈希冲突处理方案更好以确保最小的内存浪费?
我个人认为答案是线性探测的开放地址法,因为它在冲突时不需要任何额外的存储空间。这个想法正确吗?
当装载因子接近1时,哪种哈希冲突处理方案更好以确保最小的内存浪费?
我个人认为答案是线性探测的开放地址法,因为它在冲突时不需要任何额外的存储空间。这个想法正确吗?
哈希表如果填满了,就会退化成线性搜索,因此您需要保持它们不超过90%的填充率。
您关于开放地址法使用更少的内存是正确的,而链接法将需要在每个节点中使用指针或偏移字段。
我创建了一个哈希数组数据结构,用于当我需要非常轻量级的哈希表且不会有很多插入时。为了使内存使用低,所有数据都嵌入在同一块内存中,哈希数组结构位于开头,然后是两个数组,分别用于哈希和值。只有当查找键存储在值中时,才能使用哈希数组。
typedef uint16_t HashType; /* this can be 32bits if needed. */
typedef uint16_t HashSize; /* this can be made 32bits if large hasharrays are needed. */
struct HashArray {
HashSize length; /* hasharray length. */
HashSize count; /* number of hash/values pairs contained in the hasharray. */
uint16_t value_size; /* size of each value. (maximum size of value 64Kbytes) */
/* these last two fields are just for show, they are not defined in the HashArray struct. */
uint16_t hashs[length]; /* array of hashs for each value, this helps with resolving bucket collision */
uint8_t values[length * value_size]; /* array holding all values. */
};
#define hasharray_get_hashs(array) (HashType *)(((uint8_t *)(array)) + sizeof(HashArray))
#define hasharray_get_values(array) ((uint8_t *)(array)) + sizeof(HashArray) + \
((array)->length * sizeof(HashType))
#define hasharray_get_value(array, idx) (hasharray_get_values(array) + ((idx) * (array)->value_size))
#define hasharray_empty_hash 0xFFFF /* hash value to mark empty slots. */
void *hasharray_search(HashArray *array, HashType hash, uint32_t *next) {
HashType *hashs = hasharray_get_hashs(array);
uint32_t mask = array->length - 1;
uint32_t start_idx;
uint32_t idx;
hash = (hash == hasharray_empty_hash) ? 0 : hash; /* need one hash value to mark empty slots. */
start_hash_idx = (hash & mask);
if(*next == 0) {
idx = start_idx; /* new search. */
} else {
idx = *next & mask; /* continuing search to next slot. */
}
/* find hash in hash array. */
do {
/* check for hash match. */
if(hashs[idx] == hash) goto found_hash;
/* check for end of chain. */
if(hashs[idx] == hasharray_empty_hash) break;
idx++;
idx &= mask;
} while(idx != start_idx);
/* maximum tries reached (i.e. did a linear search of whole array) or end of chain. */
return NULL;
found_hash:
*next = idx + 1; /* where to continue search at, if this is not the right value. */
return hasharray_get_values(array) + (idx * array->value_size);
}
哈希冲突是不可避免的,因此调用hasharray_search()函数的代码需要将搜索键与存储在值对象中的键进行比较。如果它们不匹配,则再次调用hasharray_search()函数。此外,非唯一键也可以存在,因为搜索可以继续进行,直到返回“NULL”以查找与一个键匹配的所有值。搜索函数使用线性探测来提高缓存友好性。
typedef struct {
char *name; /* this is the lookup key. */
char *type;
/* other field info... */
} Field;
typedef struct {
Field *list; /* array of Field objects. */
HashArray *lookup; /* hasharray for fast lookup of Field objects by name. The values stored in this hasharray are 16bit indices. */
uint32_t field_count; /* number of Field objects in 'list'. */
} Fields;
extern Fields *fields_new(uint16_t count) {
Fields *fields;
fields = calloc(1, sizeof(Fields));
fields->list = calloc(count, sizeof(Field));
/* allocate hasharray to hold at most 'count' uint16_t values.
* The hasharray will round 'count' up to the next power-of-2.
* That power-of-2 length must be atleast (count+1), so that there will always be one empty slot.
*/
fields->lookup = hasharray_new(count, sizeof(uint16_t));
fields->field_count = count;
}
extern Field *fields_lookup_by_name(Fields *fields, const char *name) {
HashType hash = str_to_hash(name);
Field *field;
uint32_t next = 0;
uint16_t *rc;
uint16_t idx;
do {
rc = hasharray_search(fields->lookup, hash, &next);
if(rc == NULL) break; /* field not found. */
/* found a possible match. */
idx = *rc;
assert(idx < fields->field_count);
field = &(fields->list[idx]);
/* compare lookup name with field's name. */
if(strcmp(name, field->name) == 0) {
/* found match. */
return field;
}
/* field didn't match continue search to next field. */
} while(1);
return NULL;
}
开放地址/探测允许高填充率。因为正如您自己所说,对于冲突不需要额外的空间(只是可能需要时间 - 当然这也假设哈希函数不完美)。
如果您没有指定“负载因子接近1”或在问题中包含“成本”指标,则情况将完全不同。
祝编码愉快。
正如其他人所说,在线性探测中,当负载因子接近1时,时间复杂度接近于线性搜索。(当它满了时,它是无限的。)这里存在内存效率的权衡。而隔离链接始终为我们提供理论上的恒定时间。
通常,在线性探测下,建议将负载因子保持在1/8到1/2之间。当数组填充到一半时,我们将其调整为原始数组大小的两倍。(参考:《算法》Robert Sedgewick. Kevin Wayne.)。删除时,我们也将数组调整为原始大小的1/2。如果您真的感兴趣,最好从我上面提到的书开始学习。
实际上,据说0.72是我们通常使用的经验值。