Открытая адресация и раздельная цепочка

Отвечая на вопрос: Какая схема обработки коллизий хэш-карты лучше, когда коэффициент загрузки близок к 1, чтобы обеспечить минимальную трату памяти?

Открытая адресация/проверка, допускающая большое заполнение. Потому что, как вы сами сказали, для коллизий не требуется дополнительное пространство (только, ну, возможно, время — конечно, это также предполагает, что хеш-функция не идеально).

Если бы вы не указали «коэффициент загрузки, близкий к 1» или не включили в вопрос показатели «стоимости», это было бы совершенно по-другому.

Удачного кодирования.

Полная хеш-карта превратится в линейный поиск, поэтому вам нужно, чтобы они были заполнены менее чем на 90%.

Вы правы в том, что открытая адресация использует меньше памяти, для цепочки потребуется поле указателя или смещения в каждом узле.

Я создал структуру данных hasharray, когда мне нужны очень легкие хеш-таблицы, в которых не будет много вставок. Чтобы уменьшить использование памяти, все данные встраиваются в один и тот же блок памяти со структурой HashArray в начале, а затем с двумя массивами для хэшей и значений. Hasharray можно использовать только с ключом поиска, сохраненным в значении.

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 ​​используются для получения массивов хэшей и значений.

Я использовал это для добавления быстрого поиска сложных объектов, которые уже хранятся в массиве. Объекты имеют строковое поле «имя», которое используется для поиска. Имена хэшируются и вставляются в хеш-файл с индексом объектов. Значения, хранящиеся в hasharray, могут быть индексами/указателями/целыми объектами (я использую только небольшие 16-битные значения индекса).

Если вы хотите упаковать hasharray почти до полного заполнения, вам следует использовать полные 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%, а ключ не существует. Если ключи являются целыми числами, то линейный поиск не должен быть плохим, также необходимо будет сравнивать только ключи с одинаковым значением хеш-функции. Я стараюсь поддерживать размер hasharray так, чтобы они были заполнены примерно на 70-80%, пространство, потраченное впустую на пустые слоты, невелико, если значения представляют собой только 16-битные значения. С этим дизайном вы тратите только 4 байта на пустой слот при использовании 16-битных хэшей и 16-битных значений индекса. Массив объектов (структуры Field в приведенном выше примере) не имеет пустых мест.

Кроме того, большинство реализаций хеш-таблиц, которые я видел, не хранят вычисленные хэши и требуют полного сравнения ключей для разрешения коллизий корзин. Сравнение хэшей очень помогает, так как только небольшая часть хеш-значения используется для поиска ведра.

Как говорили другие, при линейном поиске, когда коэффициент нагрузки близок к 1, временная сложность близка к линейному поиску. (Когда он заполнен, он бесконечен.) Здесь есть компромисс между эффективностью памяти. В то время как раздельная цепочка всегда дает нам теоретически постоянное время.

Обычно при линейных измерениях рекомендуется поддерживать коэффициент нагрузки от 1/8 до 1/2. когда массив заполнен на 1/2, мы изменяем его размер, чтобы удвоить размер исходного массива. (Ссылка: Алгоритмы. Роберта Седжвика. Кевина Уэйна.). При удалении мы также изменяем размер массива до 1/2 исходного размера. Если вы действительно заинтересованы, вам стоит начать с книги, о которой я упоминал выше. На практике говорят, что 0,72 — это эмпирическое значение, которое мы обычно используем.