Define the following terms: a) hash table b) hash function c) perfect hash funct

Question

Define the following terms: a) hash table b) hash function c) perfect hash function a) What is a collision? b) 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. a) Design an algorithm (no code necessary) to delete an item from the hash table. b) What precautions do you need to take to make it work properly? Given the following data: 25 - 42 - 96 - 101 - 102 - 162 - 197 a) 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. b) Construct a second hash table using the same hash function as above, but use chaining to resolve collisions.

Explanation / Answer

(a)    A hash table (hash map) is a data structure used to realize an associative array, a structure that can map keys to values. A hash table uses a hash function to figure an index into an array of bucket or slots, from which the preferred value can be establish.

(b)   The hash function will allocate each key to a unique bucket, but most hash table design utilize an defective hash function, which may cause hash collisions where the hash purpose generates the same index for more than one key. Such collisions must be accommodate in some

A hash function is any function that can be used to map data of random size to data of preset size. The standards return by a hash charge are called hash values, hash codes, digest, hash sums, or simply hashes. One use is a data structure called a hash table, extensively used in computer software for fast data find. Hash functions step up table or database lookup by detect duplicated records in a large folder. An example is finding similar stretch in DNA sequence. They are also useful in cryptography.

(c)    A perfect hash function can be use to generate a perfect hash table that has no collisions. If minimal perfect hashing is use, each location in the hash table can be used as well

Perfect hashing allow for constant time lookups in all belongings. This is in difference to most chain and open address methods, where the time for lookup is low on average, but may be very large, O(n), for some sets of keys

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.