That's right, deleting a texture would require to update the array. For I'm not telling you the exact manner, it is clearly the best way yours.
Let's say a collection of texture would imply 2 key-bindings : one for an unique identifier for the texture and the second (let it be the value of each mapping) be the OpenGL binding.
As the Texture is deleted, the corrsponding mapping must be cleared off.
I'm using for myself hashCode() and openGL bindings in a static HashMap that is updated each time it is needed.
One thing really I'm sure : storing int's--hashCode's are and bindings so they are--is faster than running over String's. BTW String's have unique hashCode's too.
At least you can (watch out you have to re-define hashCode() with correct values--e.g. System.nanoTime()) specify each texture as Object's with specific parameters such as size or color mode.