03 Hash

Now we're going to learn about hash and hash table

You can imagine array and linked list combine, you get hash

Complexity depends on the data but it can be O(1) :)

Now imagine you have a hotel that only has one floor, each room represents the array, now when you get inside there are boxes, that's linked list.

Okay let's get simpler

example you have 5 number, 16 28 49 31 78

In array you just put arr[0] =16 and so on.

In hash you need to mod the value, for example:

Int arr[10];

The hash most of the time is the number of the data or input (example there 1 to 10, so the hash is 10) or if you want to make it more efficient uses a prime number like 7 or 13(don't use below 5 since almost all number have it).

key=input % 10; //% is mod btw

the key is the number in the array

so 16 % 10 = 6

arr[6] = 16;

Yay, you have learned hash.

The technique I just use before is the most basic and the weakest(Division), there's another way to input data

Example:

-Mid square: pow2 the value and take the middle part example: 16^2 = 256 take 5 well this more useful if your data is big but not too big like 1533, 6923, 1024.

-Folding: Now you divided into many parts and add them, repeat till the number is below the size of the array Example: 3464321 now when you see using mid square is not efficient and using division is the same now you divide it to 2 numbers like this 34,64,32,1 now add them, 34+64+32+1 = 131 and if the size of array is lower than the answer do it again, 13+1=14

arr[14] =3464321;

-Digit Extraction: take the 1st, 3rd, whatever you please and combine them example: 18593, for example, I take the first and the last digit 1,3 and arr[13] =18593;

-Rotating Hash: Rotate the number and fold it, for example: 1564 rotate it becomes 4651, fold it becomes 79. arr[79] = 1564.

The limit is just your imagination, you can create it however you please.

Now let's get back to the first data (16 28 49 31 78)if you see the entire data you will spot 78 %10 is 8 and 28 % 10 is also 8...

What to do?

Well, there are 2 methods:

1. Linear just like linear search go top/bottom and check if the array is empty and add the data to the empty array not efficient at all.

2. Chaining now this is where the linked list comes in when you create the array it connects to a struct that has value next when you input it if there's value just struct a new data and add the next from the previous data to the curr data.

Done you have learn Hash Good luck.

Why it's useful to compare to the other method like linked list or just plain array.

It's more useful because if the data is a lot more linked list comes in handy but when you have a certain aspect you wanna search linked list is long also array, example:

you want to search hello

There are 4000000 data in linked list and array... How long will it take you? Compare to arr[7] which belongs to the first word h.

*Well I use this in my first project to create a complexity 1 program with no knowledge of this exist XD, all the other part works except name since I didn't know how to code it

Okay let's see the practical example

Bitcoin uses hash, why?

For example, how do you encrypt something, well their something called SHA-256 used by bitcoin, this program encrypts a key that can be use to decrypt a message example like Hi the hash is 239wqhnowfiqn92913nqfe(just example), when you change to Ho the hash is 2834iwsnivnwi32u93n443v8g the will always 256 bits and no matter how little the change the hash change drastically. This makes it very hard to copy and even in bitcoin and other their something called public key and private key, which public key can make a hash and many public people can see even with public key you cannot translate it back you need a private key to translate it, and it goes the other way too. Want to learn more about blockchain and cryptography learn it here https://blockgeeks.com/guides/what-is-hashing/

So Hash is very useful if you need to make a program that quick and efficient.