What about using a linked list for variables added after the start of the process, which can be implemented atomically? Then once it gets "too long", a thread executing setenv could construct a new hashmap and replace the pointer to the old one with the pointer to the new one atomically, all without locking? To prevent two threads from rehashing at the same time, use an atomic flag for whether a thread is rehashing right now. That means if other threads call setenv in the meantime, the extra added variables would be appended to the list to be processed by a later setenv call (if one happens). That list could grow unbounded if enough threads call setenv quickly enough, but I think the simplicity of atomically swapping pointers might be worth it and setenv isn't called very frequently.