diff --git a/src/dict.c b/src/dict.c
index 7f89cc0..e1426ca 100644
--- a/src/dict.c
+++ b/src/dict.c
@@ -70,25 +70,23 @@
 {
     struct ly_dict_rec *dict_rec = NULL;
     struct ly_ht_rec *rec = NULL;
+    uint32_t hlist_idx;
+    uint32_t rec_idx;
 
     LY_CHECK_ARG_RET(NULL, dict, );
 
-    for (uint32_t i = 0; i < dict->hash_tab->size; i++) {
-        /* get ith record */
-        rec = (struct ly_ht_rec *)&dict->hash_tab->recs[i * dict->hash_tab->rec_size];
-        if (rec->hits == 1) {
-            /*
-             * this should not happen, all records inserted into
-             * dictionary are supposed to be removed using lydict_remove()
-             * before calling lydict_clean()
-             */
-            dict_rec = (struct ly_dict_rec *)rec->val;
-            LOGWRN(NULL, "String \"%s\" not freed from the dictionary, refcount %d", dict_rec->value, dict_rec->refcount);
-            /* if record wasn't removed before free string allocated for that record */
+    LYHT_ITER_ALL_RECS(dict->hash_tab, hlist_idx, rec_idx, rec) {
+        /*
+         * this should not happen, all records inserted into
+         * dictionary are supposed to be removed using lydict_remove()
+         * before calling lydict_clean()
+         */
+        dict_rec = (struct ly_dict_rec *)rec->val;
+        LOGWRN(NULL, "String \"%s\" not freed from the dictionary, refcount %d", dict_rec->value, dict_rec->refcount);
+        /* if record wasn't removed before free string allocated for that record */
 #ifdef NDEBUG
-            free(dict_rec->value);
+        free(dict_rec->value);
 #endif
-        }
     }
 
     /* free table and destroy mutex */
diff --git a/src/hash_table.c b/src/hash_table.c
index 246fb34..cdd2163 100644
--- a/src/hash_table.c
+++ b/src/hash_table.c
@@ -55,10 +55,29 @@
     return lyht_hash_multi(hash, NULL, len);
 }
 
-struct ly_ht_rec *
-lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx)
+static LY_ERR
+lyht_init_hlists_and_records(struct ly_ht *ht)
 {
-    return (struct ly_ht_rec *)&recs[idx * rec_size];
+    struct ly_ht_rec *rec;
+    uint32_t i;
+
+    ht->recs = calloc(ht->size, ht->rec_size);
+    LY_CHECK_ERR_RET(!ht->recs, LOGMEM(NULL), LY_EMEM);
+    for (i = 0; i < ht->size; i++) {
+        rec = lyht_get_rec(ht->recs, ht->rec_size, i);
+        if (i != ht->size)
+            rec->next = i + 1;
+        else
+            rec->next = LYHT_NO_RECORD;
+    }
+
+    ht->hlists = malloc(sizeof(ht->hlists[0]) * ht->size);
+    LY_CHECK_ERR_RET(!ht->hlists, free(ht->recs); LOGMEM(NULL), LY_EMEM);
+    for (i = 0; i < ht->size; i++)
+        ht->hlists[i] = LYHT_NO_RECORD;
+    ht->first_free_rec = 0;
+
+    return LY_SUCCESS;
 }
 
 LIBYANG_API_DEF struct ly_ht *
@@ -80,15 +99,15 @@
 
     ht->used = 0;
     ht->size = size;
-    ht->invalid = 0;
     ht->val_equal = val_equal;
     ht->cb_data = cb_data;
     ht->resize = resize;
 
-    ht->rec_size = (sizeof(struct ly_ht_rec) - 1) + val_size;
-    /* allocate the records correctly */
-    ht->recs = calloc(size, ht->rec_size);
-    LY_CHECK_ERR_RET(!ht->recs, free(ht); LOGMEM(NULL), NULL);
+    ht->rec_size = SIZEOF_LY_HT_REC + val_size;
+    if (lyht_init_hlists_and_records(ht) != LY_SUCCESS) {
+        free(ht);
+        return NULL;
+    }
 
     return ht;
 }
@@ -120,14 +139,14 @@
 
     LY_CHECK_ARG_RET(NULL, orig, NULL);
 
-    ht = lyht_new(orig->size, orig->rec_size - (sizeof(struct ly_ht_rec) - 1), orig->val_equal, orig->cb_data, orig->resize ? 1 : 0);
+    ht = lyht_new(orig->size, orig->rec_size - SIZEOF_LY_HT_REC, orig->val_equal, orig->cb_data, orig->resize ? 1 : 0);
     if (!ht) {
         return NULL;
     }
 
-    memcpy(ht->recs, orig->recs, (size_t)orig->used * (size_t)orig->rec_size);
+    memcpy(ht->hlists, orig->hlists, sizeof(ht->hlists[0]) * orig->size);
+    memcpy(ht->recs, orig->recs, (size_t)orig->size * orig->rec_size);
     ht->used = orig->used;
-    ht->invalid = orig->invalid;
     return ht;
 }
 
@@ -135,20 +154,18 @@
 lyht_free(struct ly_ht *ht, void (*val_free)(void *val_p))
 {
     struct ly_ht_rec *rec;
-    uint32_t i;
+    uint32_t hlist_idx;
+    uint32_t rec_idx;
 
     if (!ht) {
         return;
     }
 
     if (val_free) {
-        for (i = 0; i < ht->size; ++i) {
-            rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-            if (rec->hits > 0) {
-                val_free(&rec->val);
-            }
-        }
+        LYHT_ITER_ALL_RECS(ht, hlist_idx, rec_idx, rec)
+            val_free(&rec->val);
     }
+    free(ht->hlists);
     free(ht->recs);
     free(ht);
 }
@@ -164,11 +181,16 @@
 lyht_resize(struct ly_ht *ht, int operation)
 {
     struct ly_ht_rec *rec;
+    uint32_t *old_hlists;
     unsigned char *old_recs;
+    uint32_t old_first_free_rec;
     uint32_t i, old_size;
+    uint32_t rec_idx;
 
+    old_hlists = ht->hlists;
     old_recs = ht->recs;
     old_size = ht->size;
+    old_first_free_rec = ht->first_free_rec;
 
     if (operation > 0) {
         /* double the size */
@@ -178,18 +200,25 @@
         ht->size >>= 1;
     }
 
-    ht->recs = calloc(ht->size, ht->rec_size);
-    LY_CHECK_ERR_RET(!ht->recs, LOGMEM(NULL); ht->recs = old_recs; ht->size = old_size, LY_EMEM);
+    if (lyht_init_hlists_and_records(ht) != LY_SUCCESS) {
+        ht->hlists = old_hlists;
+        ht->recs = old_recs;
+        ht->size = old_size;
+        ht->first_free_rec = old_first_free_rec;
+        return LY_EMEM;
+    }
 
-    /* reset used and invalid, it will increase again */
+    /* reset used, it will increase again */
     ht->used = 0;
-    ht->invalid = 0;
 
     /* add all the old records into the new records array */
-    for (i = 0; i < old_size; ++i) {
-        rec = lyht_get_rec(old_recs, ht->rec_size, i);
-        if (rec->hits > 0) {
-            LY_ERR ret = lyht_insert(ht, rec->val, rec->hash, NULL);
+    for (i = 0; i < old_size; i++) {
+        for (rec_idx = old_hlists[i], rec = lyht_get_rec(old_recs, ht->rec_size, rec_idx);
+             rec_idx != LYHT_NO_RECORD;
+             rec_idx = rec->next, rec = lyht_get_rec(old_recs, ht->rec_size, rec_idx)) {
+            LY_ERR ret;
+
+            ret = lyht_insert(ht, rec->val, rec->hash, NULL);
 
             assert(!ret);
             (void)ret;
@@ -198,111 +227,11 @@
 
     /* final touches */
     free(old_recs);
+    free(old_hlists);
     return LY_SUCCESS;
 }
 
 /**
- * @brief Search for the first match.
- *
- * @param[in] ht Hash table to search in.
- * @param[in] hash Hash to find.
- * @param[out] rec_p Optional found record.
- * @return LY_SUCCESS hash found, returned its record,
- * @return LY_ENOTFOUND hash not found, returned the record where it would be inserted.
- */
-static LY_ERR
-lyht_find_first(struct ly_ht *ht, uint32_t hash, struct ly_ht_rec **rec_p)
-{
-    struct ly_ht_rec *rec;
-    uint32_t i, idx;
-
-    if (rec_p) {
-        *rec_p = NULL;
-    }
-
-    idx = i = hash & (ht->size - 1);
-    rec = lyht_get_rec(ht->recs, ht->rec_size, idx);
-
-    /* skip through overflow and deleted records */
-    while ((rec->hits != 0) && ((rec->hits == -1) || ((rec->hash & (ht->size - 1)) != idx))) {
-        if ((rec->hits == -1) && rec_p && !(*rec_p)) {
-            /* remember this record for return */
-            *rec_p = rec;
-        }
-        i = (i + 1) % ht->size;
-        if (i == idx) {
-            /* we went through all the records (very unlikely, but possible when many records are invalid),
-             * just return not found */
-            assert(!rec_p || *rec_p);
-            return LY_ENOTFOUND;
-        }
-        rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-    }
-    if (rec->hits == 0) {
-        /* we could not find the value */
-        if (rec_p && !*rec_p) {
-            *rec_p = rec;
-        }
-        return LY_ENOTFOUND;
-    }
-
-    /* we have found a record with equal (shortened) hash */
-    if (rec_p) {
-        *rec_p = rec;
-    }
-    return LY_SUCCESS;
-}
-
-/**
- * @brief Search for the next collision.
- *
- * @param[in] ht Hash table to search in.
- * @param[in,out] last Last returned collision record.
- * @param[in] first First collision record (hits > 1).
- * @return LY_SUCCESS when hash collision found, \p last points to this next collision,
- * @return LY_ENOTFOUND when hash collision not found, \p last points to the record where it would be inserted.
- */
-static LY_ERR
-lyht_find_collision(struct ly_ht *ht, struct ly_ht_rec **last, struct ly_ht_rec *first)
-{
-    struct ly_ht_rec *empty = NULL;
-    uint32_t i, idx;
-
-    assert(last && *last);
-
-    idx = (*last)->hash & (ht->size - 1);
-    i = (((unsigned char *)*last) - ht->recs) / ht->rec_size;
-
-    do {
-        i = (i + 1) % ht->size;
-        *last = lyht_get_rec(ht->recs, ht->rec_size, i);
-        if (*last == first) {
-            /* we went through all the records (very unlikely, but possible when many records are invalid),
-             * just return an invalid record */
-            assert(empty);
-            *last = empty;
-            return LY_ENOTFOUND;
-        }
-
-        if (((*last)->hits == -1) && !empty) {
-            empty = *last;
-        }
-    } while (((*last)->hits != 0) && (((*last)->hits == -1) || (((*last)->hash & (ht->size - 1)) != idx)));
-
-    if ((*last)->hits > 0) {
-        /* we found a collision */
-        assert((*last)->hits == 1);
-        return LY_SUCCESS;
-    }
-
-    /* no next collision found, return the record where it would be inserted */
-    if (empty) {
-        *last = empty;
-    } /* else (*last)->hits == 0, it is already correct */
-    return LY_ENOTFOUND;
-}
-
-/**
  * @brief Search for a record with specific value and hash.
  *
  * @param[in] ht Hash table to search in.
@@ -319,9 +248,9 @@
 lyht_find_rec(struct ly_ht *ht, void *val_p, uint32_t hash, ly_bool mod, struct ly_ht_rec **crec_p, uint32_t *col,
         struct ly_ht_rec **rec_p)
 {
-    struct ly_ht_rec *rec, *crec;
-    uint32_t i, c;
-    LY_ERR r;
+    uint32_t hlist_idx = hash & (ht->size - 1);
+    struct ly_ht_rec *rec;
+    uint32_t rec_idx;
 
     if (crec_p) {
         *crec_p = NULL;
@@ -331,41 +260,18 @@
     }
     *rec_p = NULL;
 
-    if (lyht_find_first(ht, hash, &rec)) {
-        /* not found */
-        return LY_ENOTFOUND;
-    }
-    if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
-        /* even the value matches */
-        if (crec_p) {
-            *crec_p = rec;
-        }
-        if (col) {
-            *col = 0;
-        }
-        *rec_p = rec;
-        return LY_SUCCESS;
-    }
-
-    /* some collisions, we need to go through them, too */
-    crec = rec;
-    c = crec->hits;
-    for (i = 1; i < c; ++i) {
-        r = lyht_find_collision(ht, &rec, crec);
-        assert(!r);
-        (void)r;
-
-        /* compare values */
+    LYHT_ITER_HLIST_RECS(ht, hlist_idx, rec_idx, rec) {
         if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
             if (crec_p) {
-                *crec_p = crec;
-            }
-            if (col) {
-                *col = i;
+                *crec_p = rec;
             }
             *rec_p = rec;
             return LY_SUCCESS;
         }
+
+        if (col) {
+            *col = *col + 1;
+        }
     }
 
     /* not found even in collisions */
@@ -390,8 +296,8 @@
         lyht_value_equal_cb collision_val_equal, void **match_p)
 {
     struct ly_ht_rec *rec, *crec;
-    uint32_t i, c;
-    LY_ERR r;
+    uint32_t rec_idx;
+    uint32_t i;
 
     /* find the record of the previously found value */
     if (lyht_find_rec(ht, val_p, hash, 1, &crec, &i, &rec)) {
@@ -399,12 +305,9 @@
         LOGINT_RET(NULL);
     }
 
-    /* go through collisions and find the next one after the previous one */
-    c = crec->hits;
-    for (++i; i < c; ++i) {
-        r = lyht_find_collision(ht, &rec, crec);
-        assert(!r);
-        (void)r;
+    for (rec_idx = rec->next, rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
+         rec_idx != LYHT_NO_RECORD;
+         rec_idx = rec->next, rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx)) {
 
         if (rec->hash != hash) {
             continue;
@@ -437,65 +340,36 @@
     return lyht_find_next_with_collision_cb(ht, val_p, hash, NULL, match_p);
 }
 
-LIBYANG_API_DEF LY_ERR
-lyht_insert_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal,
+static LY_ERR
+__lyht_insert_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal,
         void **match_p)
 {
+    uint32_t hlist_idx = hash & (ht->size - 1);
     LY_ERR r, ret = LY_SUCCESS;
-    struct ly_ht_rec *rec, *crec = NULL;
-    int32_t i;
+    struct ly_ht_rec *rec;
     lyht_value_equal_cb old_val_equal = NULL;
+    uint32_t rec_idx;
 
-    if (!lyht_find_first(ht, hash, &rec)) {
-        /* we found matching shortened hash */
-        if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
-            /* even the value matches */
-            if (match_p) {
-                *match_p = (void *)&rec->val;
-            }
-            return LY_EEXIST;
+    if (lyht_find_rec(ht, val_p, hash, 1, NULL, NULL, &rec) == LY_SUCCESS) {
+        if (rec && match_p) {
+            *match_p = rec->val;
         }
-
-        /* some collisions, we need to go through them, too */
-        crec = rec;
-        for (i = 1; i < crec->hits; ++i) {
-            r = lyht_find_collision(ht, &rec, crec);
-            assert(!r);
-
-            /* compare values */
-            if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
-                if (match_p) {
-                    *match_p = (void *)&rec->val;
-                }
-                return LY_EEXIST;
-            }
-        }
-
-        /* value not found, get the record where it will be inserted */
-        r = lyht_find_collision(ht, &rec, crec);
-        assert(r);
+        return LY_EEXIST;
     }
 
-    /* insert it into the returned record */
-    assert(rec->hits < 1);
-    if (rec->hits < 0) {
-        --ht->invalid;
-    }
+    rec_idx = ht->first_free_rec;
+    assert(rec_idx < ht->size);
+    rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
+    ht->first_free_rec = rec->next;
+    rec->next = ht->hlists[hlist_idx];
+    ht->hlists[hlist_idx] = rec_idx;
+
     rec->hash = hash;
-    rec->hits = 1;
-    memcpy(&rec->val, val_p, ht->rec_size - (sizeof(struct ly_ht_rec) - 1));
+    memcpy(&rec->val, val_p, ht->rec_size - SIZEOF_LY_HT_REC);
     if (match_p) {
         *match_p = (void *)&rec->val;
     }
 
-    if (crec) {
-        /* there was a collision, increase hits */
-        if (crec->hits == INT32_MAX) {
-            LOGINT(NULL);
-        }
-        ++crec->hits;
-    }
-
     /* check size & enlarge if needed */
     ++ht->used;
     if (ht->resize) {
@@ -525,60 +399,50 @@
 }
 
 LIBYANG_API_DEF LY_ERR
+lyht_insert_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal,
+        void **match_p)
+{
+    return __lyht_insert_with_resize_cb(ht, val_p, hash, resize_val_equal, match_p);
+}
+
+LIBYANG_API_DEF LY_ERR
 lyht_insert(struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p)
 {
-    return lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p);
+    return __lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p);
 }
 
 LIBYANG_API_DEF LY_ERR
 lyht_remove_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal)
 {
-    struct ly_ht_rec *rec, *crec;
-    int32_t i;
-    ly_bool first_matched = 0;
+    struct ly_ht_rec *found_rec, *prev_rec, *rec;
+    uint32_t hlist_idx = hash & (ht->size - 1);
     LY_ERR r, ret = LY_SUCCESS;
     lyht_value_equal_cb old_val_equal = NULL;
+    uint32_t prev_rec_idx;
+    uint32_t rec_idx;
 
-    LY_CHECK_ERR_RET(lyht_find_first(ht, hash, &rec), LOGARG(NULL, hash), LY_ENOTFOUND); /* hash not found */
+    LY_CHECK_ERR_RET(lyht_find_rec(ht, val_p, hash, 1, NULL, NULL, &found_rec),
+                     LOGARG(NULL, hash), LY_ENOTFOUND); /* hash not found */
 
-    if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
-        /* even the value matches */
-        first_matched = 1;
-    }
-
-    /* we always need to go through collisions */
-    crec = rec;
-    for (i = 1; i < crec->hits; ++i) {
-        r = lyht_find_collision(ht, &rec, crec);
-        assert(!r);
-
-        /* compare values */
-        if (!first_matched && (rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
+    prev_rec_idx = LYHT_NO_RECORD;
+    LYHT_ITER_HLIST_RECS(ht, hlist_idx, rec_idx, rec) {
+        if (rec == found_rec)
             break;
-        }
+        prev_rec_idx = rec_idx;
     }
 
-    if (i < crec->hits) {
-        /* one of collisions matched, reduce collision count, remove the record */
-        assert(!first_matched);
-        --crec->hits;
-        rec->hits = -1;
-    } else if (first_matched) {
-        /* the first record matches */
-        if (crec != rec) {
-            /* ... so put the last collision in its place */
-            rec->hits = crec->hits - 1;
-            memcpy(crec, rec, ht->rec_size);
-        }
-        rec->hits = -1;
+    if (prev_rec_idx == LYHT_NO_RECORD) {
+        ht->hlists[hlist_idx] = rec->next;
     } else {
-        /* value not found even in collisions */
-        return LY_ENOTFOUND;
+        prev_rec = lyht_get_rec(ht->recs, ht->rec_size, prev_rec_idx);
+        prev_rec->next = rec->next;
     }
 
+    rec->next = ht->first_free_rec;
+    ht->first_free_rec = rec_idx;
+
     /* check size & shrink if needed */
     --ht->used;
-    ++ht->invalid;
     if (ht->resize == 2) {
         r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
         if ((r < LYHT_SHRINK_PERCENTAGE) && (ht->size > LYHT_MIN_SIZE)) {
@@ -595,21 +459,6 @@
         }
     }
 
-    /* rehash all records if needed */
-    r = ((ht->size - ht->used - ht->invalid) * 100) / ht->size;
-    if (r < LYHT_REHASH_PERCENTAGE) {
-        if (resize_val_equal) {
-            old_val_equal = lyht_set_cb(ht, resize_val_equal);
-        }
-
-        /* rehash */
-        ret = lyht_resize(ht, 0);
-
-        if (resize_val_equal) {
-            lyht_set_cb(ht, old_val_equal);
-        }
-    }
-
     return ret;
 }
 
@@ -622,23 +471,16 @@
 LIBYANG_API_DEF uint32_t
 lyht_get_fixed_size(uint32_t item_count)
 {
-    uint32_t i, size = 0;
+    if (item_count == 0)
+        return 1;
 
-    /* detect number of upper zero bits in the items' counter value ... */
-    for (i = (sizeof item_count * CHAR_BIT) - 1; i > 0; i--) {
-        size = item_count << i;
-        size = size >> i;
-        if (size == item_count) {
-            break;
-        }
-    }
-    assert(i);
+    /* return next power of 2 (greater or equal) */
+    item_count--;
+    item_count |= item_count >> 1;
+    item_count |= item_count >> 2;
+    item_count |= item_count >> 4;
+    item_count |= item_count >> 8;
+    item_count |= item_count >> 16;
 
-    /* ... and then we convert it to the position of the highest non-zero bit ... */
-    i = (sizeof item_count * CHAR_BIT) - i;
-
-    /* ... and by using it to shift 1 to the left we get the closest sufficient hash table size */
-    size = 1 << i;
-
-    return size;
+    return item_count + 1;
 }
diff --git a/src/hash_table_internal.h b/src/hash_table_internal.h
index eaadbc7..1921fca 100644
--- a/src/hash_table_internal.h
+++ b/src/hash_table_internal.h
@@ -35,9 +35,6 @@
 /** when the table is less than this much percent full, it is shrunk (half the size) */
 #define LYHT_SHRINK_PERCENTAGE 25
 
-/** when the table has less than this much percent empty records, it is rehashed to get rid of all the invalid records */
-#define LYHT_REHASH_PERCENTAGE 2
-
 /** never shrink beyond this size */
 #define LYHT_MIN_SIZE 8
 
@@ -46,32 +43,71 @@
  */
 struct ly_ht_rec {
     uint32_t hash;        /* hash of the value */
-    int32_t hits;         /* collision/overflow value count - 1 (a filled entry has 1 hit,
-                           * special value -1 means a deleted record) */
+    uint32_t next;        /* index of next collision */
     unsigned char val[1]; /* arbitrary-size value */
 } _PACKED;
 
+/* real size, without taking the val[1] in account */
+#define SIZEOF_LY_HT_REC (sizeof(struct ly_ht_rec) - 1)
+
 /**
  * @brief (Very) generic hash table.
  *
- * Hash table with open addressing collision resolution and
- * linear probing of interval 1 (next free record is used).
- * Removal is lazy (removed records are only marked), but
- * if possible, they are fully emptied.
+ * This structure implements a hash table, providing fast accesses to stored
+ * values from their hash.
+ *
+ * The hash table structure contains 2 pointers to tables that are allocated
+ * at initialization:
+ * - a table of records: each record is composed of a struct ly_ht_rec header,
+ *   followed by the user value. The header contains the hash value and a
+ *   next index that can be used to chain records.
+ * - a table of list heads: each list head entry contains the index of the
+ *   first record in the records table whose hash (modulo hash table size)
+ *   is equal to the index of the list head entry. The other matching records
+ *   are chained together.
+ *
+ * The unused records are chained in first_free_rec, which contains the index
+ * of the first unused record entry in the records table.
+ *
+ * The LYHT_NO_RECORD magic value is used when an index points to nothing.
  */
 struct ly_ht {
     uint32_t used;        /* number of values stored in the hash table (filled records) */
     uint32_t size;        /* always holds 2^x == size (is power of 2), actually number of records allocated */
-    uint32_t invalid;     /* number of invalid records (deleted) */
     lyht_value_equal_cb val_equal; /* callback for testing value equivalence */
     void *cb_data;        /* user data callback arbitrary value */
     uint16_t resize;      /* 0 - resizing is disabled, *
                            * 1 - enlarging is enabled, *
                            * 2 - both shrinking and enlarging is enabled */
     uint16_t rec_size;    /* real size (in bytes) of one record for accessing recs array */
+    uint32_t first_free_rec; /* index of the first free record */
+    uint32_t *hlists;     /* pointer to the hlists table */
     unsigned char *recs;  /* pointer to the hash table itself (array of struct ht_rec) */
 };
 
+/* index that points to nothing */
+#define LYHT_NO_RECORD UINT32_MAX
+
+/* get the record associated to */
+static inline struct ly_ht_rec *
+lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx)
+{
+    return (struct ly_ht_rec *)&recs[idx * rec_size];
+}
+
+/* Iterate all records in a hlist */
+#define LYHT_ITER_HLIST_RECS(ht, hlist_idx, rec_idx, rec)               \
+    for (rec_idx = ht->hlists[hlist_idx],                               \
+             rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);       \
+         rec_idx != LYHT_NO_RECORD;                                     \
+         rec_idx = rec->next,                                           \
+             rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx))
+
+/* Iterate all records in the hash table */
+#define LYHT_ITER_ALL_RECS(ht, hlist_idx, rec_idx, rec)              \
+    for (hlist_idx = 0; hlist_idx < ht->size; hlist_idx++)           \
+        LYHT_ITER_HLIST_RECS(ht, hlist_idx, rec_idx, rec)
+
 /**
  * @brief Dictionary hash table record.
  */
diff --git a/tests/utests/basic/test_hash_table.c b/tests/utests/basic/test_hash_table.c
index efb5554..041af26 100644
--- a/tests/utests/basic/test_hash_table.c
+++ b/tests/utests/basic/test_hash_table.c
@@ -19,8 +19,6 @@
 #include "common.h"
 #include "hash_table.h"
 
-struct ly_ht_rec *lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx);
-
 static void
 test_invalid_arguments(void **state)
 {
@@ -103,7 +101,6 @@
 test_ht_resize(void **state)
 {
     uint32_t i;
-    struct ly_ht_rec *rec;
     struct ly_ht *ht;
 
     assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));
@@ -120,13 +117,12 @@
     for (i = 0; i < 16; ++i) {
         if ((i >= 2) && (i < 8)) {
             /* inserted data on indexes 2-7 */
-            rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-            assert_int_equal(1, rec->hits);
-            assert_int_equal(i, rec->hash);
+            assert_int_not_equal(UINT32_MAX, ht->hlists[i]);
+            assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, i, NULL));
         } else {
             /* nothing otherwise */
-            rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-            assert_int_equal(0, rec->hits);
+            assert_int_equal(UINT32_MAX, ht->hlists[i]);
+            assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
         }
     }
 
@@ -164,6 +160,8 @@
     uint32_t i;
     struct ly_ht_rec *rec;
     struct ly_ht *ht;
+    uint32_t rec_idx;
+    int count;
 
     assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));
 
@@ -172,66 +170,64 @@
     }
 
     /* check all records */
-    for (i = 0; i < 2; ++i) {
-        rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-        assert_int_equal(rec->hits, 0);
+    for (i = 0; i < 8; ++i) {
+        if (i == 2)
+            assert_int_not_equal(UINT32_MAX, ht->hlists[i]);
+        else
+            assert_int_equal(UINT32_MAX, ht->hlists[i]);
     }
-    rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-    assert_int_equal(rec->hits, 4);
-    assert_int_equal(GET_REC_INT(rec), i);
-    ++i;
-    for ( ; i < 6; ++i) {
-        rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-        assert_int_equal(rec->hits, 1);
-        assert_int_equal(GET_REC_INT(rec), i);
+    for (i = 0; i < 8; ++i) {
+        if (i >= 2 && i < 6)
+            assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, 2, NULL));
+        else
+            assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, 2, NULL));
     }
-    for ( ; i < 8; ++i) {
-        rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-        assert_int_equal(rec->hits, 0);
+    rec_idx = ht->hlists[2];
+    count = 0;
+    while (rec_idx != UINT32_MAX) {
+        rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
+        rec_idx = rec->next;
+        assert_int_equal(rec->hash, 2);
+        count++;
     }
+    assert_int_equal(count, 4);
 
     i = 4;
     assert_int_equal(lyht_remove(ht, &i, 2), 0);
 
     rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-    assert_int_equal(rec->hits, -1);
 
     i = 2;
     assert_int_equal(lyht_remove(ht, &i, 2), 0);
 
     /* check all records */
-    for (i = 0; i < 2; ++i) {
-        rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-        assert_int_equal(rec->hits, 0);
+    for (i = 0; i < 8; ++i) {
+        if (i == 2)
+            assert_int_not_equal(UINT32_MAX, ht->hlists[i]);
+        else
+            assert_int_equal(UINT32_MAX, ht->hlists[i]);
     }
-    rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-    assert_int_equal(rec->hits, 2);
-    assert_int_equal(GET_REC_INT(rec), 5);
-    ++i;
-    rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-    assert_int_equal(rec->hits, 1);
-    assert_int_equal(GET_REC_INT(rec), 3);
-    ++i;
-    for ( ; i < 6; ++i) {
-        rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-        assert_int_equal(rec->hits, -1);
+    for (i = 0; i < 8; ++i) {
+        if (i == 3 || i == 5)
+            assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, 2, NULL));
+        else
+            assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, 2, NULL));
     }
-    for ( ; i < 8; ++i) {
-        rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-        assert_int_equal(rec->hits, 0);
+    rec_idx = ht->hlists[2];
+    count = 0;
+    while (rec_idx != UINT32_MAX) {
+        rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
+        rec_idx = rec->next;
+        assert_int_equal(rec->hash, 2);
+        count++;
     }
+    assert_int_equal(count, 2);
 
-    for (i = 0; i < 3; ++i) {
-        assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
-    }
-    assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_SUCCESS);
-    ++i;
-    assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
-    ++i;
-    assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_SUCCESS);
-    ++i;
-    for ( ; i < 8; ++i) {
-        assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
+    for (i = 0; i < 8; ++i) {
+        if (i == 3 || i == 5)
+            assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_SUCCESS);
+        else
+            assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
     }
 
     i = 3;
@@ -240,17 +236,8 @@
     assert_int_equal(lyht_remove(ht, &i, 2), 0);
 
     /* check all records */
-    for (i = 0; i < 2; ++i) {
-        rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-        assert_int_equal(rec->hits, 0);
-    }
-    for ( ; i < 6; ++i) {
-        rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-        assert_int_equal(rec->hits, -1);
-    }
-    for ( ; i < 8; ++i) {
-        rec = lyht_get_rec(ht->recs, ht->rec_size, i);
-        assert_int_equal(rec->hits, 0);
+    for (i = 0; i < 8; ++i) {
+        assert_int_equal(UINT32_MAX, ht->hlists[i]);
     }
 
     lyht_free(ht, NULL);