Programmers Dojo

Hashes begin with an array.  That array is indexed with a mathematical function called a hash function.  Since the hash function is based on the key of the element you can jump "close" to the right element very quickly. The main distinction between types of hashes is in how they handle collisions. In a closed hash you iterate through the array to find the next open slot in the array. In a chained hash there is actually a linked list in each slot in the array.  Each element is simply added to the list. Both types of hashes have pros and cons but I'll elaborate those in a later post.

For our purposes I will propose 5 classes of data structures.  These being the array, list, tree, hash, and graph. Arrays Arrays are one of the most basic data structures and are characterized by direct access to every element in the structure.  It is easy to picture them as a line of numbered buckets where you can place an element into or remove an element from any bucket. Lists Lists are another very basic data structure.  In a list each node has one of more connections to other nodes.  Access to the list is only at one or both ends.  From any given element you can access any element which you have a connection to.  Here is an example of a simple list. Trees Trees are similar to lists in that each element has connections to other elements but in a tree the connections are more structured.  Each element in a tree can have children.  The number of children an element can have is an important property of a tree.  The top element in ...