title: hashing in Java -- structure & access time
body: <p>I am looking for verification on two different but related arguments-- those above <strong>(A)</strong> and below <strong>(B)</strong> the first line line-comment here in the Q. </p>
  
  <p><strong>(A)</strong> The way <strong>HashMap</strong> is structured is:</p>
  
  <p>a <strong>HashMap</strong> is a plain table. thats direct memory access (DMA).  </p>
  
  <p>The whole idea behind <strong>HashMap</strong> (or hashing in general) at the first place 
  is to put into use this constant-time memory access for </p>
  
  <p>a.) accessing records by their own data content (&lt; K,V >), 
  not by their locations in DMA (the table index)</p>
  
  <p>b.) managing variable number of records-- a number of 
  records not of a given size, and may/not remain constant 
  in size throughout the use of this structure. </p>
  
  <p>So, the overall structure in a Java Hash is:</p>
  
  <p>a table: <strong><em>table</em></strong> //     i`m using the identifier used in <strong>HashMap</strong></p>
  
  <p>each cell of this table is a <strong><em>bucket</em></strong>. </p>
  
  <p>Each <strong><em>bucket</em></strong> is a linked list of type <strong>Entry</strong>-- 
  i.e., each node of this linked list (not the linked list of Java/API, but the data structure) is of type <strong>Entry</strong> which in turn is a &lt; K,V > pair.  </p>
  
  <p>When a new  pair comes in to be added to the hash, 
  a unique <strong><em>hashCode</em></strong> is calculated for this &lt; K,V > pair. 
  This <strong><em>hashCode</em></strong> is the key to the index of this &lt; K,V > in <strong><em>table</em></strong>-- it tells 
  which bucket this &lt; K,V > will go in in the hash. 
  Note: <strong><em>hashCode</em></strong> is "normalized" thru the function <strong>hash()</strong> (in <strong>HashMap</strong> for one)
  to better-fit the current length of the <strong><em>table</em></strong>. <strong>indexFor()</strong> is also at use 
  to determine which bucket, i.e., cell of table the &lt; K,V > will go in. </p>
  
  <p>When the bucket is determined, the &lt; K,V > is added to the beginning of the linked list in this bucket-- as a result, it is the first &lt; K,V > entry in this bucket and the first entry of the linked-list-that-already-existed is now 
  the "next" entry that is pointed by this newly added one. </p>
  
  <p>//===============================================================</p>
  
  <p><strong>(B)</strong>
  From what I see in <strong>HashMap</strong>, the resizing of the <strong><em>table</em></strong>-- the hash is only done upon a decision based on 
  hash size and capacity, which are the current and max. # entries in the entire hash. </p>
  
  <p>There is no re-structuring or resizing upon individual bucket sizes-- like "resize() when the max.#entries in a bucket exceeds such&amp;such". </p>
  
  <p>It is not probable, but is possible that a significant number of entries may be bulked up in a bucket while the rest of the hash is pretty much empty. </p>
  
  <p>If this is the case, i.e., no upper limit on the size of each bucket, hash is not of constant but linear access-- theoretically for one thing. It takes $O(n)$ time to get hold of an entry in hash where $n$ is the total number of entries. But then it shouldn't be.  </p>
  
  <p>//===============================================================</p>
  
  <p>I don't think I'm missing anything in Part (A) above. </p>
  
  <p>I'm not entirely sure of Part (B). It is a significant issue and I'm looking to find out how accurate this argument is. </p>
  
  <p>I'm looking for verification on both parts. </p>
  
  <p>Thanks in advance. </p>
  
  <p>//===============================================================</p>
  
  <p>EDIT:</p>
  
  <p>Maximum bucket size being fixed, i.e., hash being restructured whenever 
  the #entries in a bucket hits a maximum would resolve it-- the access time is plain 
  constant in theory and in use. </p>
  
  <p>This isn't a well structured but quick fix, and would work just fine for sake of constant access. </p>
  
  <p>The hashCodes are likely to be evenly distributed throughout the buckets and it isn`t so likely 
  that anyone of the buckets will hit the bucket-max before the threshold on the overall size of the hash is hit. 
  This is the assumption the current setup of HashMap is using as well.</p>
  
  <p>Also based on Peter Lawrey`s discussion below.</p>