# Week 7 - Hashing

## Team

Team name: **Group [497441]**
Date: 03/31/2021

Members: Max Thielen

| Role | Name |
| - | - |
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Max Thielen |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Max Thielen |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Max Thielen |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Max Thielen |

## Activities

### Activity 1: cost of maintaining order

To maintain order in the sorted array holding the RecordPairs [8609, 6348, 4992, 5839, 1622, 5450, 7197, 4827], **20** pairs will have to be relocated throughout adding the 8 entries.

### Activity 2: Making numbers fit

The time complexity of look-up, insertion, and removial in a map where the keys are transformed into indices directly would be O(1) since it would work with the random accessing of an array. No enteries would have to be moved for inserting or removing.

### Activity 3: Calculate the moduli


This is a very viable option for reducing the range of indeces especially since the lower the number the smaller the range becomes. However, as seen in mod 17 the indeces can repeat with certain numbers and therefor the reduceded have to be chacked for overlaps first.

### Activity 4: Hash functions

Hash functions are used in order to turn big integers and string into smaller more practical intergers which can be used as indexes to store the values in an array.
This can be done in many different ways for example the moduli calculations above would count as a hash function know as the division method. Another example would be the multiplication method.

### Activity 5: Implement FNV-1a

hash_t hash_fnv_gen(const void* data_, size_t size){
    hash_t hash = FNV_OFFSET_BASIS;
    const unsigned char* ptr = (const unsigned char*)data_;
    while (size--) {
        hash ^= *ptr++;
        hash *= FNV_PRIME;
    }
    return hash;
}

hash_t hash_fnv_str(const char* str){
    hash_t hash = FNV_OFFSET_BASIS;
    while (*str) {
        hash ^= (unsigned char) *str++;
        hash *= FNV_PRIME;
    }
    return hash;
}

### Activity 6: Implement hash-based indexing

size_t hash_index_gen(const void* data, size_t size, size_t M){
    hash_t hash = hash_fnv_gen(data, size);
    size_t index = hash % M;

    return index;
}

size_t hash_index_str(const char* str, size_t M){
    hash_t hash = hash_fnv_str(str);
    size_t index = hash % M;

    return index;
}

### Activity 7: Word counting

Alice: 400
the: 1685
rabbit: 2
it: 0

### Activity 8: Hash collisions

Before:
collisions: 11553

After:
collisions: 5385

Alice: 400
the: 1685
rabbit: 2
it: 521

### Activity 9: Collision-free capacity
Size: 499
Count: 3873

### Activity 10: Implement rehashing (optional)

## Look back

### What we've learnt

Hash maps

### What were the surprises

Different types of hashing

### What problems we've encountered

Hashing, Collisions

### What was or still is unclear

n/a

### How did the group perform?

n/a