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. Consider the specification written below of a graph G V(G ) = {1,2,3,4} E(G ) = {(1,2), (1,3), (3,3), (3,4), (4,1)} (i)        Draw the undirected graph. (

Let a be a well-formed formula. Let c be the number of binary logical operators in a. (Recall that ?, ?, ?, and ? are the binary logical operators). Let s be the number of proposit

A Binary Search Tree is binary tree which is either empty or a node having a key value, left child & right child. By analyzing the above definition, we notice that BST comes int

A Red-Black Tree (RBT) is a type of Binary Search tree with one extra bit of storage per node, i.e. its color that can either be red or black. Now the nodes can have any of the col

write short note on algorithms

What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

write an algorithm for stack using array performing the operations as insertion ,deletion , display,isempty,isfull.

what is queues? how it work? and why it used? i want an assignment on queue .....

Krushkal's algorithm uses the concept of forest of trees. At first the forest contains n single node trees (and no edges). At each of the step, we add on one (the cheapest one) edg

Queue is a linear data structure utilized in several applications of computer science. Such as people stand in a queue to get a specific service, several processes will wait in a q