CS2040s: DG 4

Imagine we are taking inventory and we want to check what types of fruits is in the house so we add the differnt fruits into the hashset. We are not concern how many there are but more of the existence

HASHMAP

Lests imagine we have an inventory checklist, we want to add a variable to it. 

HASHSET VS HASHMAP

Same structure but one needs a variables

Insert -> o(1)

Lookup o(1)

Floor/ceiling-> O(n)

Max/min -> O(n)

It still unordered so we need to do a look up.

A good hash functions:

- Fast to compute

- Uses minimum slots as possible

- Scatter as uniform

- Minimal collision

     Insert:  Just iterate through

     Delete: Iterate through, change to del instead of just removing it

     Search: Using the hashing, iterate, if counter del just continue until reach the end

Relative better than linear ...

But will cause a secondary clustering, there will be many empty slots that are not used

     Insert: Iterate but also with ^2 movement, h(x) + (s)^2 starting from the first slot not the next one\

     

Using h(v) + step * h2(v) %M

h2(v) > 1

Give a differnt prob sequence for similar keys. More complicated

   Its a linked list with an hash

   We need to traverse the list.

    Search: to search for a number, look for the position and traverse the list, return not found when empty slot is reach

Simple to implement

Convert to ascii, multiply each chara's ascii with p^[index number] sum everything and mod it with p

abs it so that we wont get any negative numbers

There might be a collision because are modulo M. When mod m we are dealing with smaller numbers. Use M = 10^9+9

1. Hash value

2. Key

3. Value

The hash value is calculated from the key, if element hash zero is 0, we will just put it tehre an just return

- (number mod 10) to get the starting position

- Distance start from 0

- If the distance of the existing slot is less than current, increase distance by one and move to next slot

- if can replace and its not an empty, swap and continue search position for the swapped out item

But we need to check the existing distance of the current thing if its occupyied. If my current distance is more than what is there, check if its deleted,

If its already deleted, we just put the value there.

If its not, we will check whose distance is bigger and swap

if not iterate

Distance is always incremented by 1 and stored together with each node.

When we swap the values, we 

we will swap\

Deleting:

We replace value with del but do not change the distance value

Searching:

Linear search but when it reaches the max distance, should stop searching