title: Duplicate element search and replacement logic in HashMap
body: <p>This question was asked to me in a job interview and I still don't know answer so ask here. Lets say hashCode() of key object returns a fixed integer so HashMap would look like a LinkedList. </p>
  
  <blockquote>
    <p>How would a duplicate element be found and replaced by new value in map?</p>
  </blockquote>
  
  <p>e.g. if following 1001 puts are performed in order listed below, </p>
  
  <blockquote>
    <p>put(1000,1000), put(1,1), put( 2, 2), put ( 3,3 ) ....put(999,999), put(1000,1000 )</p>
  </blockquote>
  
  <p>Would map be traversed all the way to end and then new one be inserted at head when last put(1000,1000) is performed? </p>
  
  <p>OR </p>
  
  <p>Map has some other way to locate and replace duplicate keys?</p>