Define the following terms hash table hash function perfect

Define the following terms; hash table hash function perfect hash function What is the collision? Explain three ways of handling collisions (a program is not needed; a clear brief explanation suffices). Consider a hashing scheme that uses linear probing to resolve collisions. Design an algorithm (no code necessary) to delete an item from the hash table. What precautions do you need to take to make it work property?. Given the following data: 25-42-96-101 -102-162-197 Construct a hash table using the hash function, h(key) = key mod tablesize where the size of the table is 11. Use the rehash function, rh(key) = (key + 3) mod tablesize to resolve collisions. Construct a second hash table using the same hash function as above, but use chaining to resolve collisions

Solution

Hi, I have answered first two.Please repost others in separate post.

1)
   Hash Table:
       It is a Data structure where the data elements are stored(inserted), searched, deleted based on the keys generated for each element, which is obtained from a hashing function. In a hashing system the keys are stored in an array which is called the Hash Table. A perfectly implemented hash table would always promise an average insert/delete/retrieval time of O(1).

   Hash Function:
       A function which employs some algorithm to computes the key K for all the data elements in the set U, such that the key K which is of a fixed size. The same key K can be used to map data to a hash table and all the operations like insertion,deletion and searching should be possible. The values returned by a hash function are also referred to as hash values, hash codes, hash sums, or hashes.

   Perfect hash function:
   Given a collection of items, a hash function that maps each item into a unique slot is referred to as a perfect hash function.

2.
   a. Collision:
       A situation when the resultant hashes for two or more data elements in the data set U, maps to the same location in the has table, is called a hash collision. In such a situation two or more data elements would qualify to be stored/mapped to the same
       location in the hash table.

   b. Handling Collision
       Linear Probing
           linear probing basically does a linear search for an empty slot when there is a collision
           When inserting a key K in a table of size M, with hash function H(K)
               1. Set indx = H(K)
               2. If table location indx already contains the key, no need to insert it. Done!
               3. Else if table location indx is empty, insert key there. Done!
               4. Else collision. Set indx = (indx + 1) mod M.
               5. If indx == H(K), table is full! (Throw an exception, or enlarge table.) Else go to 2.
       Double hashing
           Linear probing collision resolution leads to clusters in the table, because if two keys collide, the next position probed will be the same for both of them.
           The idea of double hashing: Make the offset to the next position probed depend on the key value, so it can be different for different keys
           Need to introduce a second hash function H 2 (K), which is used as the offset in the probe sequence (think of linear probing as double hashing with H 2 (K) == 1)
           For a hash table of size M, H 2 (K) should have values in the range 1 through M-1; if M is prime, one common choice is H2(K) = 1 + ( (K/M) mod (M-1) )
           The insert algorithm for double hashing is then:

           1. Set indx = H(K); offset = H 2 (K)
           2. If table location indx already contains the key, no need to insert it. Done!
           3. Else if table location indx is empty, insert key there. Done!
           4. Else collision. Set indx = (indx + offset) mod M.
           5. If indx == H(K), table is full! (Throw an exception, or enlarge table.) Else go to 2.
           With prime table size, double hashing works very well in practice
       Open Hashing (Separate chaining)
           Open Hashing, is a technique in which the data is not directly stored at the hash key index (k) of the Hash table. Rather the data at the key index (k) in the hash table is a pointer to the head of the data structure where the data is actually stored. In the most simple and common implementations the data structure adopted for storing the element is a linked-list.
           In this technique when a data needs to be searched, it might become necessary (worst case) to traverse all the nodes in the linked list to retrieve the data.