Open Addressing vs. Separate Chaining

Question

Which hashmap collision handling scheme is better when the load factor is close to 1 to ensure minimum memory wastage?

I personally think the answer is open addressing with linear probing, because it doesn't need any additional storage space in case of collisions. Is this correct?

Wellspoken

Depends on how many collisions you'll get when inserting your 162 items. Given the low count, though, I can't imagine there'll be a massive difference (but could be wrong if you've a lot of collisions). – Atrice

It also depends on the ratio of insert/lookup operations I would assume too? – Anglomania

possible duplicate of Chained Hash Tables vs. Open-Addressed Hash Tables – Chaparajos

Answer 1

Answering the question: Which hashmap collision handling scheme is better when the load factor is close to 1 to ensure minimum memory wastage?

Open addressing/probing that allows a high fill. Because as you said so yourself, there is no extra space required for collisions (just, well, possibly time -- of course this is also assuming the hash function isn't perfect).

If you did not specify "load factor close to 1" or included "cost" metrics in the question then it would be entirely different.

Happy coding.

Alkali

Answer 2

A hashmap that is that full will degrade into a linear search, so you will want to keep them under 90% full.

You are right about open addressing using less memory, chaining will need a pointer or offset field in each node.

I have created a hasharray data structure for when I need very lightweight hashtables that will not have alot of inserts. To keep memory usage low all data is embedded in the same block of memory, with the HashArray structure at the start, then two arrays for hashs & values. Hasharray can only be used with the lookup key is stored in the value.

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))

The macros hasharray_get_hashs & hasharray_get_values are used to get the 'hashs' & 'values' arrays.

I have used this for adding fast lookup of complex objects that are already stored in an array. The objects have a string 'name' field which is used for the lookup. The names are hashed and inserted into the hasharray with the objects index. The values stored in the hasharray can be indexes/pointers/whole objects (I only use small 16bit index values).

If you want to pack the hasharray till it is almost full, then you will want to use full 32bit Hashs instead of the 16bit ones defined above. Larger 32bit hashs will help keep searchs fast when the hasharray is more then 90% full.

The hasharray as defined above can only hold a maximum of 65535, which is fine since I never use it on anything that would have more the a few hundred values. Anything that needs more that that should just use an normal hashtable. But if memory is really an issue, the HashSize type could be changed to 32bits. Also I use power-of-2 lengths to keep the hash lookup fast. Some people prefer to use prime bucket lengths, but that is only needed if the hash function has bad distribution.

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

hash collisions will happen so the code that calls hasharray_search() needs to compare the search key with the one stored in the value object. If they don't match then hasharray_search() is called again. Also non-unique keys can exist, since searching can continue until 'NULL' is returned to find all values that match one key. The search function uses linear probing to be cache freindly.

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

The worst case searching will degrade to a linear search of the whole array if it is 99% full and the key doesn't exist. If the keys are integers, then a linear search shouldn't be to bad, also only keys with the same hash value will need to be compared. I try to keep the hasharrays sized so they are only about 70-80% full, the space wasted on empty slots isn't much if the values are only 16bit values. With this design you only waste 4bytes per empty slot when using 16bit hashs & 16bit index values. The array of objects (Field structs in the above example) has no empty spots.

Also most hashtable implementations that I have seen don't store the computed hashs and require full key compares to resolve bucket collisions. Comparing the hashs helps a lot since only a small part of the hash value is used to lookup the bucket.

Despotism

Please mention which collision handling scheme you are using. It is not very apparent from your answer. – Wellspoken

the hasharray is using open addressing with linear probing. The hasharray_search() function doesn't compare keys only hashs, so each time it finds a matching hash value it returns that value and the caller has to do the key compare. – Despotism

"A hashmap that is that full will degrade into a linear search" That is not true. A full hashmap doesnt mean that there are collisions. A full hashmap could mean that all buckets are claimed by a single entry. – Turino

How can all the buckets be claimed by a single entry? A key can only have one value. – Despotism

Answer 3

As the others said, in linear probing, when load factor near to 1, the time complexity near to linear search. (When it's full, its infinite.) There is a memory-efficiency trade off here. While segregate chaining always give us theoretically constant time.

Normally, under linear probing, it's recommended to keep the load factor between 1/8 and 1/2. when the array is 1/2 full, we resize it to double the size of original array. (Reference: Algorithms. by Robert Sedgewick. Kevin Wayne. ). When delete, we resize the array to 1/2 of original size as well. If you are really interested, it's good for you to begin with the book I mentioned above. In practical, it's said that 0.72 is an empirical value we usually use.

Asafoetida