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
differentiate between indexing and hashing in file organization


Hubs - In reality a multiport repeater - Connects stations in a physical star topology - As well may create multiple levels of hierarchy to remove length limitation of 10

In the book the following methods are presented: static void selectionSort(Comparable[] list) static void insertionSort(Comparable[] list) static boolean linearSearch(Comparable

merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}. If we take a closer look at the diagram, we can see that the array is recursively divided in two halves till the

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

RENDERING, SHADING AND COLOURING By introducing hidden line removal we have already taken one step away from wire-frame drawings towards being able to realistically model and d

Have you ever thought about the handling of our files in operating system? Why do we contain a hierarchical file system? How do files saved & deleted under hierarchical directories

5. Implement a stack (write pseudo-code for STACK-EMPTY, PUSH, and POP) using a singly linked list L. The operations PUSH and POP should still take O(1) time.

How can we convert a graph into a tree ? Do we have any standardized algorithm for doing this?