-- Simultaneous and independent work by Katoh and Goto (https://arxiv.org/abs/1709.08900) achieves a stronger result: 1 bit of redundancy with O(1) time per operation, worst case, deterministically. They also show how to achieve this result even when the number of bits per array cell entry can be much less than the word size. (9/27/2017)