Думаю, не проще. По сути, за каждой операцией стоит изменение списка элементов в DOM. Поэтому, даже если ковырять и переписать плагин, все равно вставка 100 элементов одним махом из кэша будет медленнее чем замена одного элемента в списке (а большинство операций затрагивают один элемент). По факту вставка/удаление одного элемента обходится плагину в пол секунды.

Это да, но есть подозрение, что операции доступа к элементам ассоциативного массива должны быть отлично оптимизированы движком браузера. Или не так? И O(log n) будет, при длине ключа равной длине массива. Обычно же ключи это не очень длинные последовательности. Если ключ из 10 символов, то сложность будет O(n*log 10)