Implement an open hash table, Data Structure & Algorithms

In a chained hash table, each table entry is a pointer to a collection of elements. It can be any collection that supports insert, remove, and find, but is commonly a linked list. The elements in the list can be stored by key value order, by frequency of access or by insertion time. Each list forms a bucket in which we place elements hashing to a specific position in the array. Because each bucket is a linked list, an unlimited number of elements can be inserted. However, performance degrades if the table becomes full.

"Chained hash tables have a simple solution for resolving collisions: elements are simply placed in the bucket where the collision occurs. One problem with this, however, is that if an excessive number of collisions occur at a specific position, a bucket becomes longer and longer. Thus, accessing its elements takes more and more time. Ideally, we would like all buckets to grow at the same rate so that they remain nearly the same size and as small as possible. In other words, the goal is to distribute elements about the table in as uniform and random a manner as possible. This theoretically perfect situation is known as uniform hashing; however, in practice it usually can only be approximated.

Even assuming uniform hashing, performance degrades significantly if we make the number of buckets in the table small relative to the number of elements we plan to insert. In this situation, all of the buckets become longer and longer. Thus, it is important to pay close attention to a hash table's load factor. The load factor of a hash table is defined as: where n is the number of elements in the table and m is the number of positions into which elements may be hashed. The load factor of a chained hash table indicates the maximum number of elements we can expect to encounter in a bucket, assuming uniform hashing.

For example, in a chained hash table with m = 1699 buckets and a total of n = 3198 elements, the load factor of the table is a = 3198/1699 = 2. Therefore, in this case, we can expect to encounter no more than two elements while searching any one bucket. When the load factor of a table drops below 1, each position will probably contain no more than one element. Of course, since uniform hashing is only approximated, in actuality we end up encountering somewhat more or less than what the load factor suggests. How close we come to uniform hashing ultimately depends on how well we select our hash function."

Problem

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

You will use the table to compare two Shakespeare plays: Hamlet and As You Like It. You will report the number of words that Shakespeare used in both plays. Have your program read the file hamlet.txt and insert each word into the table. For this assignment, a word will be delimited by a white space, so simple input with >> can be used. Some of the words will, of course, be nonsense, but we will ignore this. After inserting all the words from Hamlet, do a lookup for words from the file asyoulikeit.txt. Store and count the words that are duplicated in the two plays (i.e. words for which the search is successful). Your count may be slightly less than accurate in reality, since we will not strictly parse the words. However, each student should come up with the same list of words and the same count. For each word you insert, compute the number of elements in the bucket that are searched. Likewise, compute the number of unsuccessful searches. Report the average number of elements inspected during a search (average number per bucket). Determine if this is close to the expected size based on the load factor after all words have been inserted.

Posted Date: 5/6/2013 2:46:15 AM | Location : United States







Related Discussions:- Implement an open hash table, Assignment Help, Ask Question on Implement an open hash table, Get Answer, Expert's Help, Implement an open hash table Discussions

Write discussion on Implement an open hash table
Your posts are moderated
Related Questions
Q. Convert the following given Infix expression to Postfix form using the stack function: x + y * z + ( p * q + r ) * s , Follow general precedence rule and suppose tha

Comparison Techniques There are several techniques for determining the relevancy and relative position of two polygons. Not all tests may be used with all hidden-surface algori

Question 1 What is a data structure? Discuss briefly on types of data structures Question 2 Explain the insertion and deletion operation of linked list in detail Qu

Data type An implementation of an abstract data type on a computer. Therefore, for instance, Boolean ADT is implemented as the Boolean type in Java, and bool type in C++;

Unlike a binary-tree, each node of a B-tree may have a number of keys and children. The keys are stored or saved in non-decreasing order. Each key has an related child that is the

Adjacency list representation An Adjacency list representation of Graph G = {V, E} contains an array of adjacency lists mentioned by adj of V list. For each of the vertex u?V,

PART- Pest Control Program Prepare a Pest Control Program for the facility that will address the management of Rodents, Insects and Birds. Your Pest Control Program should

Implement a linear-expected-time algorithm for selecting the k th smallest element Algorithm description 1. If |S| = 1, then k = 1 and return the element in S as the an

Explain in brief about the Container An entity which holds finitely many other entities. Just as containers such as boxes, baskets, bags, pails, cans, drawers, and so for

A B-tree of minimum degree t can maximum pointers in a node T pointers in a node.