Implement an open hash table, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Implement an open hash table

Darw a flowchart to input 3 numbers, This algorithm inputs 3 numbers, every...

This algorithm inputs 3 numbers, every number goes through successive division by 10 until its value is less than 1. An output is produced which comprise the number input and a val

Insertion of a node into a binary search tree, A binary search tree is cons...

A binary search tree is constructed through the repeated insertion of new nodes in a binary tree structure. Insertion has to maintain the order of the tree. The value to the lef

Convertion, how we can convert a graph into tree

how we can convert a graph into tree

Indexed sequential file organisation, When there is requirement to access r...

When there is requirement to access records sequentially by some key value and also to access records directly by the similar key value, the collection of records may be organized

Lilz, I need to know about data structure and algorithms. can you help me?

I need to know about data structure and algorithms. can you help me?

What is binary search, What is binary search?   Binary search is most ...

What is binary search?   Binary search is most useful when list is sorted. In binary search, element present in middle of the list is determined. If key (the number to search)

Define big omega notation, Define Big Omega notation Big Omega notatio...

Define Big Omega notation Big Omega notation (?) : The lower bound for the function 'f' is given by the big omega notation (?). Considering 'g' to be a function from the non-n

Difference between prism''s and kruskal''s algorithm, Difference among Pris...

Difference among Prism's and Kruskal's Algorithm In Kruskal's algorithm, the set A is a forest. The safe edge added to A is always a least-weight edge in the paragraph that lin

Java, Ask consider the file name cars.text each line in the file contains i...

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd