EDIT: Actually, on second thought, there may be performance issues depending how you assign sprite IDs. Suppose you remove a sprite and then insert it again. Does the sprite have the same ID as it did before? Then it will always land in the same bucket of the hash table, or in this case, starting position. So some sprites might be penalized by slow lookup since they always land in "bad" places in the table.
You could salt them with a random value.