There are two settings under which you can get O(1) worst-case times.

1. If your setup is static, then FKS hashing will get you worst-case O(1) guarantees. But as you indicated, your setting isn't static.

2. If you use Cuckoo hashing, then queries and deletes are O(1) worst-case, but insertion is only O(1) expected. Cuckoo hashing works quite well if you have an upper bound on the total number of inserts, and set the table size to be roughly 25% larger.

There's more information here.

There are two settings under which you can get $O(1)$ worst-case times.

1. If your setup is static, then FKS hashing will get you worst-case $O(1)$ guarantees. But as you indicated, your setting isn't static.

2. If you use Cuckoo hashing, then queries and deletes are $O(1)$ worst-case, but insertion is only $O(1)$ expected. Cuckoo hashing works quite well if you have an upper bound on the total number of inserts, and set the table size to be roughly 25% larger.

There's more information here.