Mumbai University > COMPS > Sem 3 > Data Structures

Marks: 10 M

Year: May 2014

• Hashing is a technique by which updating or retrieving any entry can be achieved in constant time O(1).
• In mathematics, a map is a relationship between two sets. A map M is a set of pairs, where each pair is in the form of (key, value). For a given key, its corresponding value can be found with the help of a function that maps keys to values. This function is known as the hash function.
• So, given a key k and a hash function h, we can compute the value/location of the value v by the formula v = h(k).
• Usually the hash function is a division modulo operation, such as h(k)=k mod size, where size is the size of the data structure that holds the values.
• Collision is the event of two keys hashing to the same location.
• A collision can be dealt with by linear probing (looking at the next available location-i+1, i+2,…), quadratic probing (same as linear probing with quadratic spaces-i+1, i+4, i+9,…) and chaining (process of creating a linked list of values if they hash into the same location)

• The following is the solution to the given hashing problem:-

  1. 99 mod 10 is 9. Since it’s vacant, 99 gets stored at position 9.
  2. 33 mod 10 is 3. Since it’s vacant, 33 gets stored at position 3.
  3. 23 mod 10 is 3. Since 3 is already occupied by 33, 23 gets stored at the next available location, 4. (1 collision)
  4. 44 mod 10 is 4. Since 4 is already occupied by 23, 44 gets stored at the next available location, 5. (1 collision)
  5. 56 mod 10 is 6. Since it’s vacant, 56 gets stored at position 6.
  6. 43 mod 10 is 3. Since 3 is already occupied by 33, 43 gets stored at the next available location, 7. (4 collisions)
  7. 19 mod 10 is 9. Since it is already occupied by 99, 19 gets stored at the next available location, 0. (1 collision)

  So, in the end, this is how the structure looks like.