title: Java data structure that has efficient add, delete, and random
body: <p>I need a Java data structure that I can efficiently add, delete, and access a random object.</p>
  
  <p>This is what doesn't work:</p>
  
  <p>ArrayList has efficient add (constant time), and random access (just "get" with a random integer), but deletes can take linear time because it has to potentially search the whole list for it.</p>
  
  <p>TreeSet or HashSet has efficient add and delete, but I can't figure out how to get a random object.</p>
  
  <p>Any ideas?</p>
  
  <p>In theory, a B Tree would work, if I could traverse the tree myself with random Lefts or Rights, but I don't think a standard Java class gives me this ability.</p>
  
  <p>I'm willing to use a third party library if nothing in the standard Java classes will work.</p>
  
  <p>I do not need to support duplicates or nulls, nor does it need to be thread safe.</p>
  
  <p>Thanks.</p>