let dequeue_with_key t =
    ensure_can_modify t;
    match Doubly_linked.remove_first t.queue with
    | None -> None
    | Some kv -> Hashtbl.remove t.table kv.key; Some (kv.key, kv.value)