Data Structures and Algorithms

Singly Linked List Example</summary>
</details>
Think About It

• What is the advantage of using a linked list?
• What is the difference between a singly linked, doubly linked, and circularly linked list?

Work to do:

1. Open this gist and copy the contents into an appropriate folder structure:
   • node.rb and linkedlist.rb will go in a lib/ folder
   • linked_list_test.rb will go in a test/ folder
2. Write some code to make the tests pass

Hash Maps

Hashes, at a high level are “key-value” data structures, but how do they actually work?

The “hash” name comes from a mathematical formula about how the hash knows where to store each piece of data in memory. The more complex a “hashing” algorithm is, the more easily things can be stored into “unique” places in memory, but will take longer to actually do the calculation. Less-complex hashing algorithms are much faster, but risk more “collisions” of data. (eg, if our “hashing” algorithm was only storing strings, and we used the first letter of the string to define where it was put in memory, and our strings were student names, then “James”, “Jamal”, “Jackie”, etc would all “collide” in memory.

So, hash maps use an array (commonly referred to as “buckets”), where each “bucket” is a “head” node of a linked list. Back to our “student names” example, we’d have 26 “buckets”, one for each letter of the alphabet, and the “J” bucket would be a linked list where each node contains the names for James, Jamal, Jackie, etc.. This is the “map” explanation of the name of “hash map”, it’s using a “hash” algorithm to generate a “map” of where things get stored in memory. You might also hear the term “hash table”.

In a typical Hash Map, if there’s a “collision” (ie, the letter “J”), every value is shifted to the right and the newer data is stored as the new start of that bucket’s linked list.

The main difference with this linked list, though, is that a hash has a name and a value.

In our students example, we might want to store the ages of our students like this:

{
  'James': 27,
  'Jamal': 31,
  'Jackie': 29,
  etc
}

Since our Linked List only has a value, if we just stored “27”, “31”, and “29”, we would lose track of which student had which age. So now our Hah Map’s Linked List “node” has to be a little more advanced. We have to store the original “key” value, plus that key’s “value” (in this example, the student age).

class Node
  attr_reader :key, :value
  attr_accessor :next

  def initialize(key, value)
    @key = key
    @value = value
    @next = nil
  end
end

When we want to recall a student’s age, say Jamal, we run our hash algorithm on the “key” (“Jamal”), which would produce our “J” value, go to our “J” bucket, and then traverse that linked list until we find a node which has a payload which includes a “key” attribute with “Jamal” in it, and then return the “value”.

Work to do:

1. Build some Ruby code that does a very rudimentary “hashing” algorithm for a given string that just returns the first letter of the string, something like this should suffice:

   def hash(string)
     string[0]
   end
   

2. Make an array of 26 Linked Lists, one for each letter of the alphabet, and write some code to insert and retrieve some key/value pairs from your hash.
3. Hint: the word “Hash” will be reserved in Ruby, so call it something else

Looking for More?

This repo has several computer science exercises to deepen your understanding.