Hashing - Algoviz Wiki

Works

Yes

Description

A complete tutorial for teaching hashing, largely based on the presentation in "A Practical Introduction to Data Structures and Algorithm Analysis" by Clifford A. Shaffer. A series of HTML pages takes the reader through the topics of hash functions, open vs. closed hashing, collision resolution, deletion. The web pages are interspersed with visualizations that demonstrate a variety of hash functions and collision resolution methods, as well as applets that show aspects of the performance for the various methods.

Evaluation

The presentation is fairly detailed. This tutorial can stand alone as an introduction to hashing, and has been classroom tested in that mode. The series of applets that show the various hash functions and collision resolution methods allow students (optionally) to working in "test" mode where they must first predict where the next key will go in the hash table. The applets that demonstrate performance are fairly unique in that AVs usually only show how things work, not their performance. However, the performance graphs might not always be sufficiently clear.

Step Control; User Data; Random Data; Questions; Exploration

Lecture Aid; Lab Exercise; Self Study; Comparison

Screenshots

Videos

References

Clicking on the link above will take you to a "table of contents" for the hashing tutorial. You can click on any entry to go to a page on that topic, or you can start at the beginning and use the navigation links at the bottom of each page to progress through the tutorial. Most tutorial pages have one or more Java applets that either let you try out something or compare the performance of various implementations.

First Visited

2008-05-05

Last Visited

2008-05-05

Last Updated

2008-05-02

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.auckland.ac.nz/software/AlgAnim/hash_tables.html#hash_anim

Edit

You may edit this entry if you have an account.

Auckland - Hash Tables

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

John Morris

Institution

University of Auckland

Project

Morris' Collection

Works

Yes

Description

Web pages give an explanation of hashing. The AV allows user a choice of a couple of collision resolution methods. The focus is more on overall performance of the hash system than on explaining how the given collision resolution method takes place, with a couple of graphs for showing access costs.

Evaluation

The screen is rather busy. It is a bit difficult to figure out what you can do. There is a lot of performance information available, which is helpful. User can run in continuous mode or step mode.The input set of keys is pre-populated and on pressing the next or on using animation, the tool simply pulls up a word from a pre-populated text file and uses it as a key for putting in the hashing table. In case of a collision of the generated hash values, the AV provides re-Hash functionality in the AV window and the tool automatically rehashes the key and puts it in the appropriate place in the hash table. Unfortunately, the does not make clear what hash function is being used. Further, in quadratic probing, the user can not manually input the value of “c” used in the hash function, the user is restricted to use any of the three values for it i.e. 1, 2 and 4. The author has used the graphs to plot Collision stats and Hashing Frequency stats to good effect. The coloring scheme is pretty nice and visually appealing.

Animation; Step Control; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-11-06

Last Visited

2008-07-17

Last Updated

1998

Topic

Community

Average rating:	4.0
Your rating:	You must be logged in to Rate.

Edit

You may edit this entry if you have an account.

JHAVÉ - Hashing

Recommendation

Has Potential

Link

http://jhave.org/learner

Delivery Method

Java Web Start

License

CreativeCommons

Language

English

Author

Tom Naps

Institution

University of Wisconsin - Oshkosh

Project

JHAVÉ

Works

Yes

Description

A set of four visualizations for specific topics in hashing, including linear probing, quadratic probing, chaining, and double hashing. Associated HTML page gives some guidance on using the AV, but it is not extensive..

Evaluation

The AV is set up as a series of "slides" in one pane, and pseudocode in the adjacent pane. As the user steps through the "slides", the associated pseudocode is highlighted. Occasional questions pop up for the user to answer. The AV is fairly clear within its limited agenda for each collision resolution method. The associated explanatory material is fairly limited, and needs to be fleshed out.

Step Control; Questions; Canned Data; User Data

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

Clicking on the link above will take you to a login page for Jhave. If you do not want to create an account at jhave.org, use anonymous@anonymous.com as your user name and anonymous as your password when you are asked to login. You will then be taken to the Jhave page for this AV. Some Jhave AVs include a tutorial on how the AV itself or the underlying algorithm works. At the bottom are links to the AV (you can run it with a built-in quiz system on or off). The first time you try to run any Jhave exercise, you will have to download the Jhave webstart application. This should happen automatically when you click the link. (You might need to install Java WebStart if it is not on your machine.) Once you download the Jhave application, the AV should start automatically. You can then step through the AV by repeatedly clicking the right arrow button. Occasionally, you will be given a multiple-choice or short-answer question to answer.

First Visited

2008-07-08

Last Visited

2008-07-10

Last Updated

2008-07-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.animal.ahrgr.de/showAnimationDetails.php3?anim=29

Edit

You may edit this entry if you have an account.

Animal - Hashing Presentations

Recommendation

Has Potential

Link

Delivery Method

Animal Animation

License

Non-Commercial

Language

English; German

Author

Guido Rössling

Institution

TU Darmstadt, Darmstadt, Germany

Project

Animal

Works

Yes

Description

The Animal site has a number of hashing walkthroughs, including quadratic and linear probing examples. Shows how a fixed set of elements is entered into a Hashtable using the probing method. Also gives pseudo code description and number of accesses for each inserted element.

Evaluation

Reasonably clear, though the computation for where a record goes when there is a collision is a bit hard to follow.

Animation; Step Control; Canned Data

Lecture Aid

Screenshots

Videos

References

For detailed instructions on how to install Animal and run Animal AVs, see: http://www.algoanim.info/Animal2/?q=node/290. Once you have installed the Animal .jar file and downloaded/unpacked the .zip file of Animal animations, you are now ready to run Animal. Run the .jar file to start Animal. Then go to the "Open" menu item, and browse to where you put the animal animations you got in the .zip file. Pick this AV from the list. You can then step through the animation, or use "kiosk mode" to have the steps fed to you at a constant pace.

First Visited

2007-07-21

Last Visited

2010-02-05

Last Updated

1999-04-18

Topic

Community

Average rating:	3.0
Your rating:	You must be logged in to Rate.

http://www.cs.duke.edu/courses/cps100/fall02/lects/oct29/hash10.html

Edit

You may edit this entry if you have an account.

JAWAA - Hashing Tutorial

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Non-OSI Open Source

Language

English

Author

Susan Rodger

Institution

Duke University

Project

JAWAA

Works

Yes

Description

A set of class notes including AVs for linear probing and quadratic probing.

Evaluation

The tutorial isn't very deep, but it gives the basic idea of hashing. The visualization clearly illustrates collisions in various cases. But, it could have been better with good use of color changes when a collision occurs. The linear probing example could also have shown wrap-around. The quadradic probing example is good, but the animation needs some better explanatory text to go with it.

Animation Only; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-09-02

Last Visited

2008-07-23

Last Updated

2002

Topic

Community

Average rating:	3.0
Your rating:	You must be logged in to Rate.

http://www.cs.usfca.edu/galles/visualization/download.html

Edit

You may edit this entry if you have an account.

Data Structure Visualization - Closed Hashing

Recommendation

Has Potential

Link

Delivery Method

Java Application

License

Unlicensed Sourcecode

Language

English

Author

David Galles

Institution

University of San Francisco

Project

Data Structure Visualization

Works

Yes

Description

Demonstrates standard closed hashing with a simple (mod) hash function. Allows choice of various collision resolution policies: linear probing, quadratic probing, and double hashing.

Evaluation

Simple presentation. Generally clear, with some weak points. Only supports mod function for hash function. The hash table size of 23 makes this hard to understand. Would have been better to pick a table size easier to mod in one's head (such as 20). String hash function is incomprehensible. No explanation of what the 2nd hash function is for double hashing. And since the computation explanation goes away at the last step, the user doesn't get to see what is going on to figure it out. Better step-by-step explanations would help make things clearer.

Animation; Step Control; User Data

Lecture Aid; Debugging

Screenshots

Videos

References

First Visited

2006-09-01

Last Visited

2008-07-02

Last Updated

2006-04-05

Topic

Community

Average rating:	2.0
Your rating:	You must be logged in to Rate.

http://www.cs.usfca.edu/galles/visualization/download.html

Edit

You may edit this entry if you have an account.

Data Structure Visualization - Open Hashing

Recommendation

Not Recommended

Link

Delivery Method

Java Application

License

Unlicensed Sourcecode

Language

English

Author

David Galles

Institution

University of San Francisco

Project

Data Structure Visualization

Works

Yes

Description

Simple demonstration of open hashing. Two variations: one for integers and one for strings.

Evaluation

Rather limited AV. The integer version uses a simple mod function for the hash function. Using a hash table of size 11 for this purpose is therefore a poor choice, since it is hard for users to compute mod 11 in their head to verify their understanding. The string hash function is totally incomprehensible (and takes too many steps to present, so that there is a can't-see-the-forest-for-the-trees feel). Given how simple the concept of open hashing is, this AV isn't so useful.

User Data

Lecture Aid

Screenshots

Videos

References

First Visited

2006-09-01

Last Visited

2008-07-02

Last Updated

2006-04-05

Topic

Community

Average rating:	1.0
Your rating:	You must be logged in to Rate.

http://www.eece.unm.edu/faculty/heileman/hash/code/hash.html

Edit

You may edit this entry if you have an account.

UNMhash

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unlicensed Sourcecode

Language

English

Author

BJ Smith; GL Heilman; CT Abdallah

Institution

University of New Mexico

Project

StandAlone

StandAlone

Works

Yes

Description

This tool is in the form of a Java Applet that lets the user experiment and compare exponential and double hashing on the clustered data. The user can input a cluster size between 1% and 100%, and a table size between 100 and 10,000 elements. On pressing the run button two hash tables (one for exponential hashing and one for double hashing) are created each filled to 95% capacity. The applet also provides a “Graph” button, which lets you compare the number of probes required at different points, in form of a line graph, on way to filling the Hash table to 95% capacity. The tool is highly compact, and can be used to see the just number of Probes required for each Hashing Algorithm i.e. Exponential and Double hashing that fills the hash table at different capacities, say 5%, 10%, 15%,….95%.

Evaluation

Limited usefulness. Doesn't really demonstrate any hashing algorithms, but rather shows performance under a rather specialized set of circumstances. While showing performance data is a good thing to encourage in AVs, in this case this AV needs better explanation of what is being described.

User Data

Lecture Aid

Screenshots

Videos

References

First Visited

2007-10-25

Last Visited

2008-07-02

Last Updated

1996

Topic

Community

Average rating:	1.5
Your rating:	You must be logged in to Rate.

http://www.cs.pitt.edu/~kirk/cs1501/animations/CHashing.html

Edit

You may edit this entry if you have an account.

Pitt ClosedHash

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Unknown

Institution

UIUC

Project

Kirk Pruhs' Collection

Works

Yes

Description

Shows closed hashing (chaining from a hash table) for a fixed-size table of 10 slots and modulus as the hash function. Note that this applet was written somewhere else, but the link to the original site is dead.

Evaluation

Very limited ability, shows only putting elements into the right bin of the 10 slot table, to form a linked list on collisions.

Lecture Aid

Screenshots

Videos

References

First Visited

Last Visited

2008-06-11

Last Updated

Topic

Community

Average rating:	1.0
Your rating:	You must be logged in to Rate.

http://www.csanimated.com/animation.php?t=Hash_table

Edit

You may edit this entry if you have an account.

CS Animated - Hash Table

Recommendation

Not Recommended

Link

Delivery Method

Flash

License

Non-Commercial

Language

English

Author

Bill Jacobs

Institution

None

Project

Jacobs' AV Lectures

Works

Yes

Description

A basic introduction to hashing. A multimedia lecture, with audio used to explain the data structure and a series of slides for the visual component. Each slide has its own video component, so it is easy to move through the lecture. Each slide has flash animation as appropriate.

Evaluation

The main problem with this AV is that it barely scratches the surface of hashing. There are better presentations available. Not interactive, but in that sense it is certainly no worse than a standard animation. The presentation is generally clear, so far as it goes.

Animation Only; Canned Data

Self Study

Screenshots

Videos

References

First Visited

2008-06-23

Last Visited

2008-06-23

Last Updated

2008-06-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.hut.fi/Research/TRAKLA2/exercises/index.shtml

Edit

You may edit this entry if you have an account.

Trakla - Hashing

Recommendation

Not Recommended

Link

Delivery Method

Java Application

License

GPL

Language

English

Author

Ville Karavirta; Ari Korhonen; Lauri Malmi; Kimmo Stålnacke

Institution

Helsinki University of Technology

Project

Trakla2

Works

Yes

Description

Exercises related to hashing, including linear probing, quadratic probing, and double hashing.

Evaluation

This is a great idea. Users would click on where they expect the entry to go in the hash table. Unfortunately, it has the fatal flaw that users have to hand-calculate non-intuitive hash functions like taking the modulus 19, which makes it impractical to use. Another problem is that users just show the final outcome for the entry, not the probing steps involved. This means that when the user goes through the "model answer" for the exercise, they don't see the probing steps, just the final result. These exercises are not stand alone, users will have to have background in the relevant collision resolution methods to be able to do the exercises. If the mod 19 issue were fixed, these exercises might be "recommended".

Canned Data; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References