title: Collision Checking in Hashing
body: <p>I am having some <strong>understanding problem</strong> with <strong>Hashing</strong> concept as follows:</p>
  
  <p>Suppose, I have implemented hash table(1-D array, say <strong>A[100]</strong>) having keys as numbers. I have one simple hash function <strong>H(Key) % Table_Size</strong>, which will return target index into the hash table(while accessing value associated with this particular key).</p>
  
  <p>Suppose, I want to store <strong>0</strong>(key) into the table. When I pass this key to <strong>H</strong>(hash function), it returns random index, say 25.</p>
  
  <p>There are 2 possibilities for this location in array A(having index 25):</p>
  
  <ol>
  <li>A[25] contains some key other than <strong>0</strong>, as already been stored(previously)</li>
  <li>A[25] contains <strong>0</strong></li>
  </ol>
  
  <p>First possibility has collision and it is easily identifiable(because current key:0 and  already stored key:k are different), so no problem in first one.</p>
  
  <p>But, for second one, how would I know weather there is a collision or not ?</p>
  
  <p>As long as I know, hash table or array would be part of main memory. Suppose A[25] is stored into memory location 500.</p>
  
  <p>How would I know weather this location(500) is actually <strong>empty</strong> or has been already <strong>filled</strong> by some other key ?</p>
  
  <p>What status or value of memory cells represents <strong>EMPTY</strong> or <strong>NULL</strong> or <strong>UNUSED</strong> location ?</p>
  
  <p>And, what if I want to store <strong>0</strong> as a key into this location doing collision check ?</p>
  
  <p>I am currently assuming that if any memory location is <strong>EMPTY</strong> or <strong>NULL</strong> or <strong>UNUSED</strong>, then it would be in RESET state(all cells are 0's). Is this true ?</p>
  
  <p>It may be silly question but I am wondering how to check collision in such cases.</p>
  
  <p>--</p>
  
  <p>Thanks in advance!!
  (Hitein, Hyderabad)</p>