linear probing

linear probing

1. Linear probing M.Rajshree m.SC(it)

2. HASHING Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string. Hashing is used to index and retrieve items in a database because it is faster to find the item using the shorter hashed key than to find it using the original value

3. Hashing is nothing but by implementing a hash function Hashing is a technique used for performing insertions, deletions and finds in constant average time Hash table Hash table ADT which supports only a subset of the operations allowed by binary search trees. Hash table structure is merely an array of some fixed size, containing the items

4. Open addressing In an open addressing hashing system, all the data go inside the table In open addressing, Unlike separate chaining, all the keys are stored inside the hash table. No key is stored outside the hash table   There are three common collision resolution strategies: Linear Probing Quadratic probing Double hashing

5. Linear probing Linear probing is s technique for resolving hash collisions of values of hash function. Linear probing   is a scheme in computer programming for resolving collisions in hash tables, data structures for maintaining a collection of key–value pairs and looking up the value associated with a given key .  Linear probing can provide high performance because of its good locality of reference, but is more sensitive to the quality of its hash function than some other collision resolution schemes .

6. Linear probing is a component of open addressing schemes for using a hash table to solve the dictionary problem . The linear probing hash table is a fairly simple structure where data items are stored directly inside the hash element array. It gets its name by the way it handles the unique problems that exist when storing the data items in the table directly. It takes constant expected time per search, insertion, or deletion when implemented using a random hash function

7. insertion To insert a key–value pair ( x , v ) into the table (possibly replacing any existing pair with the same key), the insertion algorithm follows the same sequence of cells that would be followed for a search, until finding either an empty cell or a cell whose stored key is  x . The new key–value pair is then placed into that cell If the insertion would cause the load factor of the table (its fraction of occupied cells) to grow above some preset threshold, the whole table may be replaced by a new table, larger by a constant factor, with a new hash function, as in a dynamic array.

8. Insert Operation   Hash function is used to compute the hash value for a key to be inserted. Hash value is then used as an index to store the key in the hash table .   In case of collision, Probing is performed until an empty bucket is found. Once an empty bucket is found, the key is inserted. Probing is performed in accordance with the technique used for open addressing .  

9. Search Operation To search any particular key, Its hash value is obtained using the hash function used. Using the hash value, that bucket of the hash table is checked. If the required key is found, the key is searched. Otherwise, the subsequent buckets are checked until the required key or an empty bucket is found. The empty bucket indicates that the key is not present in the hash table.

10. Advantage It is easy to compute .   Disadvantage The main problem with linear probing is clustering. Many consecutive elements form groups. Then, it takes time to search an element or to find an empty bucket .  

11. Linear Probing has the best cache performance but suffers from clustering. Quadratic probing lies between the two in terms of cache performance and clustering. Double caching has poor cache performance but no clustering.