title: Java LinkedHashSet remove(Object obj) method constant/linear time complexity?
body: <p>In the docs, it is stated that</p>
  
  <blockquote>
    <p>Like HashSet, [LinkedHashSet] provides constant-time performance for the basic operations (add, contains and <strong>remove</strong>), assuming the hash function disperses elements properly among the buckets.</p>
  </blockquote>
  
  <p>I understand how HashSet can provide constant-time performance for remove(Object obj), but since LinkedHashSet needs to maintain a linked list as well, and removing a specific element involves traversing the list, then it seems to me that remove(Object obj) should take linear time. Am I missing anything?</p>
  
  <p>The only explanation I can think of is that each entry in the hash table (maintained by LinkedHashSet) contains a reference to the corresponding node in the linked list, so it takes constant time to locate the node in the linked list. But I am not sure if it is really the implementation...</p>
  
  <p>Thanks!</p>