Unordered Data Structure # WEEK 1 - Hashing 개념

1.1.1 Hashing Introduction

 

this algorithm's often computer science's favorite algorithm, because you're going to find the results of hashing, it's going to give us a fantastic run time for certain operations. 

 

Mathematically, we define hashing as a keyspace(table) that we want to transform into a number of different values. So, everything inside of our keyspace is going to be every possible key that we can have inside of our dictionary.

 

our goal of a hash table is to be able to map every single key to the value that it contains in that dictionary, and do so as quickly and as efficiently as possible.

 

 

there was a mapping between the student who owned the locker and the locker number. So given any locker number you could quickly look up which student had that locker. A has table is going to allow us to do exactly that. We're going to input a number into our hash table, and we're going to use some functions, so we can go ahead and map every possible number input into a fixed sized output.

 

Because ultimately, in a locker key space, we might know exactly how many lockers there are, but we may also consider things like identifier, such as a social security number or other identifier that may be a random number that's not entirely filled up in the key space.

 

identifier such as a social security number(주민등록번호) or other identifier that may be a random number that's not entirely filled up in the key space. So we know the key space can be any possible integer, and we want to be able to map any possible integer into our output space. The entire goal of hashing is always going to revolve around. this diagram. Here we have input coming in, this is going to be something like an integer. 

 

A Hash Table based Dictionary (3)

 

A Hash Table consists of three things:

• we need some a hash function, that's going to map our input space into an array index.
  • string input type down to some integer between 0 ~ n
• we need to look at is we need to actually have an array that stores the actual data
  • we have an array that's going to store data, that's going to be indexed in by our hash function
• we can imagine that sometimes we're going to have two things in the same spot in the array, and we know that's not allowed. we need some way to decide what we want to do in collisions.
  • handle the collisions that occur when our hash function map two different values to the same point in the array.