开放寻址与分离链接

Question

开放寻址与分离链接

hashtablehashmaphash-collision

7

当装载因子接近1时，哪种哈希冲突处理方案更好以确保最小的内存浪费？

我个人认为答案是线性探测的开放地址法，因为它在冲突时不需要任何额外的存储空间。这个想法正确吗？

- user191776

取决于插入162个项目时会发生多少碰撞。虽然数量较少，但我想不出会有很大的差异（如果有很多碰撞可能会错）。 - Will A

这也取决于插入/查找操作的比率，我想是吧？ - Flexo

可能是链式哈希表与开放定址哈希表的区别的重复问题。 - finnw

3个回答

1

回答问题：当负载因子接近1时，哪种哈希映射冲突处理方案更好以确保最小的内存浪费？

开放地址/探测允许高填充率。因为正如您自己所说，对于冲突不需要额外的空间（只是可能需要时间 - 当然这也假设哈希函数不完美）。

如果您没有指定“负载因子接近1”或在问题中包含“成本”指标，则情况将完全不同。

祝编码愉快。

- user166390

0

正如其他人所说，在线性探测中，当负载因子接近1时，时间复杂度接近于线性搜索。（当它满了时，它是无限的。）这里存在内存效率的权衡。而隔离链接始终为我们提供理论上的恒定时间。

通常，在线性探测下，建议将负载因子保持在1/8到1/2之间。当数组填充到一半时，我们将其调整为原始数组大小的两倍。（参考：《算法》Robert Sedgewick. Kevin Wayne.）。删除时，我们也将数组调整为原始大小的1/2。如果您真的感兴趣，最好从我上面提到的书开始学习。

实际上，据说0.72是我们通常使用的经验值。

- Lowson Pan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Neopallium · Accepted Answer

哈希表如果填满了，就会退化成线性搜索，因此您需要保持它们不超过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))

宏 'hasharray_get_hashs' 和 'hasharray_get_values' 用于获取 'hashs' 和 'values' 数组。

我已经使用它来快速查找已存储在数组中的复杂对象。这些对象有一个字符串“name”字段，用于查找。名称被哈希并插入到哈希数组中，其中包括对象索引。存储在哈希数组中的值可以是索引/指针/整个对象（我只使用小的16位索引值）。

如果要将哈希数组打包到接近满的程度，则需要使用完整的32位哈希值而不是上面定义的16位哈希值。较大的32位哈希值将有助于在哈希数组超过90％满时保持搜索速度。

如上定义的哈希数组最多只能容纳65535个，这很好，因为我从未在任何具有超过几百个值的东西上使用它。需要更多的内容应该使用普通散列表。但是，如果内存确实是问题，HashSize类型可以更改为32位。此外，我使用2的幂长度来保持哈希查找速度。有些人喜欢使用素数桶长度，但只有当哈希函数分布不良时才需要这样做。

#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;
}

如果数组填充了99%，并且关键字不存在，最坏情况下的搜索将退化为整个数组的线性搜索。如果关键字是整数，则线性搜索不应该太糟糕，而且只需要比较具有相同哈希值的关键字。我尝试保持哈希数组的大小，使其只填充约70-80%，如果值只是16位值，则浪费在空插槽上的空间不多。使用16位哈希和16位索引值时，每个空插槽只浪费4个字节。在上面的示例中，对象数组（Field结构体）没有空插槽。

此外，我见过的大多数哈希表实现都不存储计算出的哈希值，并且需要完全的关键字比较来解决桶碰撞。比较哈希值可以帮助很多，因为只有哈希值的一小部分用于查找桶。