diff -r 9c176073e771 -r a6aaa77b6809 src/kv_list.c
--- a/src/kv_list.c	Thu Sep 11 20:17:43 2025 +0200
+++ b/src/kv_list.c	Fri Sep 12 16:56:04 2025 +0200
@@ -96,6 +96,10 @@
     }
 }
 
+static CxHashKey *cx_kv_list_loc_key(cx_kv_list *list, void *node_data) {
+    return (CxHashKey*)((char*)node_data + list->list.base.collection.elem_size);
+}
+
 static void cx_kvl_deallocate(struct cx_list_s *list) {
     cx_kv_list *kv_list = (cx_kv_list*)list;
     // patch the destructors
@@ -150,10 +154,20 @@
 ) {
     cx_kv_list *kv_list = (cx_kv_list*)list;
     // patch the destructors
+    // we also have to do that when targetbuf is NULL,
+    // because we do not want wrong destructors to be called when we remove keys from the map
     cx_kv_list_update_destructors(kv_list);
-    // TODO: always use the target buffer to get the element first,
-    //       then obtain the key, remove it from the map,
-    //       and finally call any destructors manually
+    // iterate through the elements first and remove their keys from the map
+    CxIterator iter = kv_list->list_methods->iterator(list, index, false);
+    for (size_t i = 0; i < num && cxIteratorValid(iter); i++) {
+        void *node_data = cxIteratorCurrent(iter);
+        CxHashKey *key = cx_kv_list_loc_key(kv_list, node_data);
+        // when the hash is zero, there is no key assigned to that element
+        if (key->hash != 0) {
+            kv_list->map_methods->remove(&kv_list->map->map_base.base, *key, NULL);
+        }
+        cxIteratorNext(iter);
+    }
     return kv_list->list_methods->remove(list, index, num, targetbuf);
 }
 
@@ -236,6 +250,13 @@
         &kv_list->list.base, kv_list->list.base.collection.size,
         kv_list->list.base.collection.store_pointer ? &value : value);
     if (node_data == NULL) return NULL; // LCOV_EXCL_LINE
+    // if the hash has not yet been computed, do it now
+    if (key.hash == 0) {
+        cx_hash_murmur(&key);
+    }
+    // copy the key to the node data
+    CxHashKey *key_ptr = cx_kv_list_loc_key(kv_list, node_data);
+    *key_ptr = key;
     // then insert the key into the map, referring to the node data
     return kv_list->map_methods->put(map, key, node_data);
 }
@@ -402,9 +423,16 @@
 
 int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key) {
     cx_kv_list *kv_list = (cx_kv_list*)list;
-    char *node_data = kv_list->list_methods->at(list, index);
-    char *loc_key = node_data + list->collection.elem_size;
-    memcpy(loc_key, &key, sizeof(key));
+    void *node_data = kv_list->list_methods->at(list, index);
+    if (node_data == NULL) {
+        return 1;
+    }
+    // if the hash has not yet been computed, do it now
+    if (key.hash == 0) {
+        cx_hash_murmur(&key);
+    }
+    CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
+    *loc_key = key;
 
     // TODO: what happens when we are _replacing_ an existing key?
     kv_list->map_methods->put(&kv_list->map->map_base.base, key, node_data);