HashBiMap appears to replace the old value instead of throwing. I think it's probably go to throw, but there should also be a replace(k, v) method.