Реализация таблицы постоянного хеширования

В программе, над которой я работаю, я разрабатываю большое «дерево потоков» (не более k дочерних элементов на узел), где каждый поток вносит некоторые изменения в хеш-таблицу, унаследованную от своей родитель. Есть ли способ реализовать хеш-таблицу, которая была бы несколько «постоянной» (в смысле http://en.wikipedia.org/wiki/Persistent_data_structure )?

А именно, есть ли способ для реализации пары ключ-значение с поиском, вставкой и удалением не менее O (log n), которые являются полностью постоянными, но столь же "экономичными" (худший случай) как обычная хеш-таблица?