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

Question

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

Я лично считаю, что ответ - открытая адресация с линейным зондированием, потому что в случае столкновений не требуется дополнительное пространство для хранения. Это верно?

Answer 1

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

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

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

Счастливое кодирование.

Answer 2

Хешмап, который является полным, деградирует в линейный поиск, поэтому вы захотите сохранить их на 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 ​​используется, чтобы получить 'hashs' & массивов 'ценность'.

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

Если вы хотите упаковать хашармы до тех пор, пока он не будет полностью заполнен, вы захотите использовать полные 32-битные хеши вместо 16-битных, определенных выше. Большие 32-битные хэш-функции помогут ускорить поиск, когда хэш-карта будет заполнена на 90% больше.

Хэшхарэй, как определено выше, может содержать максимум 65535, что отлично, поскольку я никогда не использую его ни на чем, что будет иметь несколько сотен значений. Все, что требует больше, что должно просто использовать обычную хэш-таблицу. Но если память действительно проблема, тип HashSize может быть изменен на 32 бита. Кроме того, я использую power-of-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% полная и ключ не существует. Если ключи являются целыми числами, то линейный поиск не должен быть плохим, также нужно сравнивать только ключи с тем же значением хэш-функции. Я стараюсь, чтобы размеры hasharrays были такими, чтобы они составляли только 70-80%, пространство, потраченное на пустые слоты, не так много, если значения имеют только 16-битные значения. При таком дизайне вы используете только 4 байта на пустой слот при использовании 16-битных хешей & 16-разрядные значения индекса. Массив объектов (Структуры полей в приведенном выше примере) не имеет пустых мест.

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

Answer 3

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

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