Hashing

Hashing

This refers to the process of converting a into an index in a table by performing some simply computed operation on the .

Hash Tables

These are data structures that very efficiently map keys to values. When we use a to look up in a hash table, we convert the into a hash code and then use the hash code to map to an index in the table. In other words, we use hashing go from in a hash table.

Advantages

Hashing is really important because it allows you to map an infinite number of keys to some finite number of values. This means you can store your mapped values in a table that's significantly smaller than the number of potential keys or hash codes.

Disadvantages

Because there are generally an infinite number of keys mapping to a finite number of hash codes, two distinct keys can map to the same table index. We call these keys synonyms, and we call the actual phenomenon of having multiple keys whose hash codes map to the same table index a collision. One way of dealing with this is something called chaining where we store each colliding pair in a linked list located at their mapped index (i.e., collision site). It's important to store the with the , or you won't know which in the list maps to which .

Asymptotic Analysis: Inserting, Finding, and Deleting

For a good hash table, this is . For a terrible hashtable with a lot of collisions, this is .

 
Go to Top
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score