# Week 7 - Hashing

## Team

Team name: Groep 2
Date: 31-03

Members:
Nian Luisman
Thom Kistemaker
Anton Vorderman

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

## Activities

### Activity 1: cost of maintaining order

[8609], geen realloc.
[8609, 6348], 1 verplaatst.
[6348, 8609, 4992], 2 verplaatst
[4992, 6348, 8609, 5839], 2 verplaatst
[4992, 5839, 6348, 8609, 1622] 4 verplaatst
[1622, 4992, 5839, 6348, 8609, 5450], 3 verplaatst
[1622, 4992, 5450, 5839, 6348, 8609, 7197], 1 verplaatst
[1622, 4992, 5450, 5839, 6348, 7197, 8609, 4827], 6 verplaatst

[1622, 4827, 4992, 5450, 5839, 6348, 7197, 8609] 19 Totaal verplaatst, 7 realloc

### Activity 2: Making numbers fit

met gebruik van modulo zou je dit aantal elementen nog kleiner kunnen maken.

time complexity van alles = O(1)

### Activity 3: Calculate the moduli
|id | 8609 | 6348 | 4992 | 5839 | 1622 | 5450 | 7197 | 4827 |
|----|------|------|------|------|------|------|------|------|
|% 8 | 1| 4| 0| 7| 6| 2| 5| 3|
|% 16| 1| 12| 0| 15| 6| 10| 13| 11|
|% 17| 7| 7| 11| 8| 7| 8 | 6| 16|

### Activity 4: Hash functions
Een hash functie is een functie die invoer uit een breed domein omzet in een (meestal) kleiner bereik, meestal een deelverzameling van de getallen.

bitcoin mining
wachtwoorden

### Activity 5: Implement FNV-1a

hash_t hash_fnv_gen(const void* data_, size_t size){

    const unsigned int* data = data_;

    hash_t hash = FNV_OFFSET_BASIS;
    for (unsigned long i = 0; i < size; i++){
        hash = hash ^ data[i];
        hash *= FNV_PRIME;
    }

    return hash;
}

hash_t hash_fnv_str(const char* str){
    // TODO [Activity 5]

    hash_t hash = FNV_OFFSET_BASIS;
    for (int i = 0; str[i] != '\0'; i++){
        hash = hash ^ str[i];
        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){
    // TODO [Activity 6]
    size_t index;
    hash_t hash = hash_fnv_gen(data, size);
    index = hash % M;
    return index;
}

size_t hash_index_str(const char* str, size_t M){
    // TODO [Activity 6]
    size_t index;
    hash_t hash = hash_fnv_str(str);
    index = hash % M;
    return index;
}

### Activity 7: Word counting

int main(void) {
    HashMap hash_map = processFile("alice0.txt");

    // TODO [Activity 7]
    hm_getOrDefault(&hash_map, "Alice", 0);
    hm_getOrDefault(&hash_map, "the", 0);
    hm_getOrDefault(&hash_map, "rabbit", 0);

    hm_destroy(&hash_map);    return 0;
}

### Activity 8: Hash collisions

else{
        // TODO [Activity 8]
        // HASH COLLISION
        count_collision++;
        printf("Collision %d:%c collides with %c", count_collision, key, hash_map->data[index]);
        return count_collision;
    }

### Activity 9: Collision-free capacity

### Activity 10: Implement rehashing (optional)

## Look back

### What we've learnt

Fill in...

### What were the surprises

Fill in...

### What problems we've encountered

message("Comment the line below if your project doesn't load")
Deze regel hebben we gemist

### What was or still is unclear

Fill in...

### How did the group perform?

How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?