I am not sure why you think deletion has to be O(log n), but can assure you that it is O(1). Of course, this is assuming you consider a hash table lookup to take constant time. If that can help, this is implementation of deletion for the OrderedDict collection:
def __delitem__(self, key):
'od.__delitem__(y) <==> del od[y]'
# Deleting an existing item uses self.__map to find the link which is
# then removed by updating the links in the predecessor and successor nodes.
dict.__delitem__(self, key)
link = self.__map.pop(key)
link.prev.next = link.next
link.next.prev = link.prev