CloComp 2526 Hashing 1

Hello, good afternoon everyone. Eh, we

meet again for the lecture on

algorithmic complexity or algorithmic

complexity. In

this meeting, we will discuss

a concept that we know as

hashing

. especially we will see we

focus on why hashing is

important for eh computer science or

computer science and also some of the things that

make it have to be implemented or

applied considering ee maybe ee

traditional methods or methods

that have been ee old can not

speed up or cannot support the

process that will be carried out by computers

or ee machines yes.

ee especially for the retrieval area

where we have to input data

or store data, process it,

then also extract or

take out data from storage or

storage location. Okay.

Well, let's start with why hashing is

necessary. Well,

we know that especially in the

ee field, it was pulled by rivals

before, maybe it wasn't too clear

and

in the eh data

retrieval field.

So

what is the meaning of data retrieval? Eh, the meaning of

data is where we have to store

data, retrieve data, yes, remove

data from storage, how

to organize the data in memory or in

storage so that it can be

retrieved again to

see what information is in the data

. Yes. Em in the field of data

retrieval we can see that some

eh we call it traditional methods

or traditional methods

such as eh linear search or binary

search including binary search

have several obstacles to

storing or

extracting data from memory

a few weeks ago Then maybe a

few days ago you might have

heard or received information or received a

lecture about eh linear search

or binary search which what is it

called has time complexity or

the time to eh wait when the data is

extracted or issued is O yes

from e big o. Well, imagine if

you want time

complexity, time complexity,

time complexity.

Imagine with such time complexity

, you

try to search for example the

stored data or ee contacts,

e telephone contacts, contact numbers

stored in the ee phone book which are

not in sequence, right? What's more, this is

storage or a storage place

where the data here is not

sequential

. E,

well, if for example you want to look for

information to remove

from this storage place,

you automatically have to search or check

one by one, check one by one the

storage places or what is it called?

If this is considered like rooms,

you have to check

each room one by one to find the data

you want to extract or you

want to ee what is it called? Take it or you guys

look for it. This becomes very

inefficient, especially for

large amounts of data or large

sets. Because you have to

check each e room. Okay,

and so you have to

check one by one until the data

you want to search for is found,

so with this O time complexity, it is

very inefficient for large data types

.

Then the binary search which has a

time complexity of O logarithm of N, yes,

this is indeed what is it called, eh, it is

faster than O eh N because

it is the logarithm of N. only

research requires data to be

sorted.

It requires that the data we want to

extract is in sequential

or sorted form.

And it is indeed faster than what

we had before in linear

search. But the process of sorting

data, if you calculate the time

complexity,

is also quite expensive just for

sorting the data, not to mention extracting the

data. If you extract data from data

that has been sorted or ordered, it is

indeed fast. But the process for us

to sort the data is what we consider to be

more expensive or more costly

in terms of time and effort or eh

computational

.

So the time complexity is quite high

and the competitive cost is quite high

too.

Well, one of the techniques that was

developed is what is it called?

To overcome this problem is

binary search 3 which changes or

what is called has a time

complexity between O log N to

ON. only at

certain times, in the worst case scenario,

it

can make the time return to O

eh to ON. Well, the

worst cases where the time or time

complexity is UN are often

caused by the size or shape of the

tree or data being unbalanced

or the data being unbalanced.

What do you call it? If you understand

the shape of three, the shape is like

this graph, right?

like this, each one has an

eh age and eh notes, where the notes

have children or parents or

parents.

Well, for example, if it's unbalanced,

what's it called? It's

not balanced, for example, if this

is the starting point, then we

call it ROT.

If the root end is there,

we can see that in that trigon

, there

is an imbalance

between the right position and the

left position, where the search process

in the left position will definitely

take a long time because it has to

go down to the roots to

get the

desired data. So, if the

desired data is in a position

like this, it automatically has to

walk or explore to the very

root.

Or even worse if

the data is actually on the

right. That meant he had to

explore the entire left position

first. Well, before finally moving to

the window on the right to

get the data, okay?

In fact, if we have a

smart enough mechanism

for this free binary search, we

can, if we already know the position of

the data on the right, automatically, maybe

we can,

what is called, eliminate the

search process on the left

. So for balance 3, it is

still an obstacle when we

carry out the data retrieval process or

eh data to take data from

storage.

Here we already have a

demand or request because if we

look at the current process of receiving data

or creating data, it is very

fast.

Moreover, with the term big data

, the term big data means that the

volume of data is already very large

. Hopefully so that we need

eh what is it called? Explosion of data,

yes. Data grows

exponentially once in an exponential graph,

yes.

Then we need a

method or technique or whatever way

it is to

make ee what is it called data search

or data receiver, data extraction

more efficient,

precise and access is more eh scalable

can be developed or ee what is it

called can be

multiplied. Please provide it based on

data growth or development.

Okay. Well, let's see now what

haing is, okay? Hing is a technique that

transforms or changes input data.

Usually the input data is in the form of an

integer or string. Suddenly

you understand the data. Change the input data,

yes. input

input data is a fixed value

or

fixed size value, a

fixed size value,

usually in the form of an array or

integer

that represents the

original data that you have or that

you want to hash the presentation

. So once again, hashing is a

technique used to transform

or change input values ​​into

fixed size values. Oh, sorry, fix the

size value. ee fixed values

that represent your input values

yeah. Well,

ee these fixed values, yes

these fixed values ​​or

this size value, we usually know

it as eh usually we know it as

ee

sor

we can call it

Well,

later this high code will be used

as an index, as an index,

yes, to store and receive data

effectively and efficiently, yes. So

remember, hashing is a

technique to transform input values

into fixed size values ​​that we know as

has codes, which are later

used as indexes to

store and retrieve data

efficiently.

Make sure eh what's the name? Imagine

you have a

locker, for example at UKIM there is a locker.

Of course, each locker has a

eh, what is it called? Different key combinations

. Yes, if you want to

receive or take items from

the locker

, of course you will not open

each locker individually. You

just go to the locker number that has been

indexed, locker 1, locker 2, 3. Then

just open the locker, okay?

with the codes that have been

provided, yes. Well, how does

hashing work?

So, to change the input data

into a

hash code, there is a function that will be

applied to the input value.

For example, if we have the word "

apple" yes,

apple may be the result of the function

from the function that has been implemented or

created,

this apple is then changed to a

fixed size value or coded to have a value of

5 yes.

Well,

then these five are stored in what

we call a hash table.

So, the hash table is an array

that is used to store the index

of the high score,

taking the index of the high code

.

So, from there to uh uh

what's it called? Storing the H code

requires a trivial insertion process

to the hash table.

So if we want to store eh

Apple for example or appel appel yes

into the has table, we enter index

number 5 into the table. Then,

if we want to

extract the word apple, we go to

index number 5 and then we extract

the information e about the apple.

Well, with a mechanism like this,

it is not impossible for a mechanism like this to

happen, eh, what is it called,

what we call collusion.

Yes, what is collusion?

Well, collusion is a data collision.

In Indonesian, collusion is

like a collision, right?

Well, maybe eh when we hash eh the

apple it outputs the value H5

according to the function we already ee what is it

called? the functions we create. But

for example, if we take

bananas, for example,

bananas, perhaps with the

same function, they issue index 5

so that a collision occurs between the

apple storage area for storing

apples and this banana. Well,

there are two

most commonly used mechanisms to avoid

or handle this collusion.

The first one is

caning or in Indonesian,

chain. That will store the values

of ee apples and bananas into a

sort of list.

So in a typical table there will be index

5. Well, index 5 has a value

or has the value of apples, comma

bananas

. So if

this function's special function or this special function

returns the same value that already

exists or is owned by the previous data ee

, it will still insert the

new data according to the existing ee index

into a list. There

may be others that will be

saved to make the list longer.

Well, that's the first way. The second way

is to use the term open

addressing.

Well, this open addressing will

try to find an empty slot, the

next empty slot by exploring

the table. So, for example, if the

index number 5 is already filled by the

apple, then the banana will also

contain the number 5, then it will look for an

empty index or an empty slot to

store the banana data. Maybe

index number 6 is where to place

ee what is the name of the data regarding bananas.

Well, the choice of technique between

these hashing methods really determines

how effective

and efficient hashing becomes.

Again, this is a case by case basis

. If it is to choose when it is suitable,

choose the opening when it is suitable,

determine the effective or

efficient way to determine how to use

hashing effectively and efficiently.

yes.

Well, the implementation or application

of this hashing is

actually

very widely applied in the world of

databases and indexing

. To query data

quickly, an index is usually used from the

database used to

store the data.

Then in cryptography

to

guarantee the security and integrity of the

data,

yes. Then there are lots of hashings

used because they are a

basic concept for storing and receiving

or outputting data.

Yes, even so, it is not without

challenges, Racing also has

some

limitations or weaknesses. One

of the things that could have happened earlier is collusion

. Then how is the function of

this hashing developed.

If the function is good or strong, it

might indirectly

reduce collisions too. Okay.

Well, that's about the meaning of

hashing.

Okay. Eh, one of the functions that is quite eh

sorry one of the aspects that we learned

from the previous slide is the has

function.

This is an important aspect when we want to

process data with hashing.

Eh, as explained,

this has function is a function.

This function changes the input data.

N so if there is input data, we

apply the function then it

will become a

fixed

size value. What does it mean, eh, what is the value or value

called? We still hope

that the value remains automatic when

we perform a query or want to retrieve

data,

so the time complexity is close to or

similar to O1.

This is the time complexity which is

independent of the size of the dataset.

So, even if the data set is large or

small, if all our queries or eh

information retrieval that we do

are close to the time complexity

or sorry all 1, it is close to ideal.

Okay.

So,

what's it called?

Uh, this has function has

functions that are very important.

Among them, as already explained,

it makes data retrieval or

data retrieval and accessing or

searching for data more efficient

or in other words, increases

efficiency

in accessing data. Okay.

Oh, it's just a

coincidence, sorry. Then it also

supports data structuring. Because

by accelerating, we change

our input into a hash which

will later or eh

hash code, it will make our data

more organized,

well organized so that it

minimizes the search time, which

of course is very useful when ee

what is the name of ee our data is in the form of a

very very large or large data

set.

Then it also increases security

because this has function is often used

to guarantee or make data more

integrity

and more authentic.

Hmm.

So, to make has functions that are

more robust or oh wait, more

robust or more, ee, what do we call it

, robust or tough or strong

, solid, sturdy, the term is

sturdy, ee, the ideal function, right?

What is the ideal function like?

The use of the ideal function must

guarantee that the

data that we distribute

is ee un uniform or

distributed ee evenly.

So when we apply the has

function,

okay, the

result we get is the result that is

issued by the has function in the form of a

has code,

or we call it has, or

hash value. whatever it is, it is spread

evenly in the hash table

or special table, yes. So if we

have the input earlier, if in the

previous slide we input it, we use the

function to produce the has code, right?

This H code will be stored in the

hash table.

So, if the distribution of the keys is

even in the has a table,

it indicates that our has function

is an ideal has function,

which is good, as expected.

Then the second indicator is when there is

a little collusion,

yes. If the collusion

generated by these functions is

small in number or rare,

it indicates that our H functions

are designed ideally. Well, so

pay attention to these two indicators. Uniform

key distributions and collision

resolution methods indicate or

are indicators of whether our H function is

optimal or not.

Eh, then how do we

implement the

has function study? Has function

as we know

is a function. So

whatever mathematical operator you want to

use as long as it is a

function and produces an output, that is the

output, the hash code.

We can categorize it as a

hash function. So that's a function,

yes, an arithmetic function. Okay, one of the

simple arithmetic functions that

we usually use for the

simplest hash function

is modular hashing or

modulus-based hashing.

What modulus modulus? The modulus is the remainder, right?

remainder for. For example, if ee 5 modulus 4

means it is equal to 1. This means the remainder of

5 and 4 is 1. 7 modulus 3 is

also 1 because the result of dividing 7 by 3 is 1.

If 7 modulus 4 means

3. This means the remainder

is 3. Yes, that is the meaning of ee

modulus.

Well, eh, the simplest of the H

functions,

the simplest H function

that we can quickly use is the

modulus based on eh, sorry,

modulus-based modular hashing which is usually

indicated or

represented written as

this percentage, right? So ee with the

hash formula our input value.

we put the modulus of the size from the table.

So, what table? This is the size of the

hash table.

Well, has tableemic eh sor selection of

size from this table depends on eh

individual choice. For example,

I choose the has table of 16.

So, if for example we

apply this function,

we apply this function for the

hashing process, for example, we

want to hash the number 10 so we write

hash 10, yes, it is the same as 10 modulo or

modulo of 16, the size of the table is equal

to

10, yes, the remainder for it

or hash

ee 26, yes, it

means 26

modulo

of 16 is 10 too.

hash. Another example is 42, for example

42

modulo

17, eh sorry, modulo 16

= 10. So the remainder for the module is the

remainder for the division. So you can use

this function

to ee using

ee used as a hash table.

Well, if you look at it, oh

my, the selection of a simple function that is

quite simple will

cause

me to change the color, it

will cause this, what is it called? There are lots of

collisions like the example

we just saw, there are 10 10 of these.

This will produce the same has code

or in other words its function is

to produce ee which is quite easy to produce

collusion.

Although collusions like the ones

we heard yesterday or some of the previous slides

can be overcome or handled

with two methodologies, namely caning and

open dressing. But still, if you have a

lot of collusion that occurs,

if a lot of collusion

occurs, of course this process will also

take time, thus increasing the

processing time. Ha, and so

if we think that less

collision is better. If we

have a lot of collisions, that's something

we don't expect. And many

collisions that occur could be

caused by the selection or

design of the hashing function

not being optimal or not good.

Well, in this case, because the design is

very simple, the formula is very

simple, that's why collusion can easily occur

. Okay. Well, one trick

to reduce collusion is choosing the

table size. The size of this table,

according to arithmetic, is

better to use prime numbers

. 17

23 is a prime number, right? Because with

prime numbers, the modulation process

will often, eh, so it will rarely

result in collusion occurring. There are still some,

but not as many as

if the table size selection is not a

prime number.

One more thing, eh, for example,

ee oh yes, eh, the limitation or limitation or

weakness of this modular hashing is

because of its simple nature, the formula is

very simple,

the distribution of the ee key in the

table is very bad, not very

good, yes, it has the same pattern,

yes.

Eh, sorry or ee if for example Q,

these Q values ​​have the

same patterns, ee, it

will probably produce numbers that are not

evenly distributed.

Okay. So, ee because

basically this formula is a

simple formula, right?

So the distribution of numbers is uneven.

Even though the

uniform key distributions

from the previous slide are an

indication or are the

most important or primary thing in the

hard function.

Then the second limitation is or the

second weakness or the second deficiency

is clustering.

Well, this clustering occurs when

some groups become or slots some

slots or groups

become full so that it reduces

performance

reduces

performance.

Well, the ee slot is

full,

the slot in the table becomes full so that it

reduces performance when we

do queries or searches.

What is the name for improving the simplicity

of this modular haing? Usually

we develop more

complex functions that are quite advanced.

Oh wait a minute.

One of the advanced ones is that

we can use the

harsh murmur.

Well, this is a more complex function process

using arithmetic

or a more complex function

so that it

reduces or reduces collusion

and makes the distribution of Q

more even.

So, next, let's look at

collisions, OK? Eh, this collision, eh,

collision is almost impossible to

avoid in hashing, right? in

terms of hashing.

Eh in the hashing process especially we ca

n't nearly avoid

collisions. Our only goal is to

reduce the occurrence of these collisions.

Well, trying to make sure that the

coalition happens at least. So, when we

try to reduce the ee, suppress

the level of collisions or when

the collision occurs, yes, when the collision

occurs, there are two mechanisms to

handle the collision, yes. There is something

we call chaining

or chains

or chains, chaining.

E wait a minute I

or the second method is eh open

addressing

eh

ah wait a minute open addressing

open addressing which is open

addressing which

applies the technique of applying the rehearsing technique

can also be used

to implement the

ee rehousing technique, yes. So, if

we choose chain, the chaining method, well, the

mechanism is in

the previous slides,

I briefly mentioned what

chain and open tracing are. If it's a chain, it

will make the index into a

link list. So the list is related

to each other elements.

to save ee data that ee

collides with, what is the name of the has code?

For example, if

we try to use this function,

the easiest way to

cause a collision is the modular function.

If we want to have a function value of eh 12

for example, with what is it called ee

what is it called em modulu ee the size of the table is

5 for example,

so the Q is 12 we modulo it with

the size of the table 5 yes, the result is the

has code 2 yes, if we for example

want to hash 22 yes 22 modulo of

the size of the table 5 yes, that is also du well this is an example of two what are the names of two what are the names of two keys that collide or become a collusion well with this C method yes before when we enter the values ​​where we enter the values ​​we enter the values ​​into the has

table

Well,

for example, suppose this is a hash table index

that two will contain a link list or link

or list whose elements are what are they

called ber ee related berlink yes it

eh

contains the

first link list maybe 12 yes because the

result of the module is 2 then

goes to 22 yes. Later, if there is another ee key

whose module is 2. For example,

in the slide there are 32 and

so on until the list is

full.

Okay. Well, this is the table that is the

hash table if we use the

chaining mechanism. If we

use the chaining mechanism

to handle collusion. Okay.

Well, it's like this. Well, the advantage

of this chaining method is that it is

simple, easy, so it is easy to

implement

.

Ah, the hope is that if for example there is

not too much collusion, yes, it

doesn't happen too often,

this CN method is more

desirable or better to use

because it is simple and easy to

implement.

But the downside is that if there is

a lot of collusion, then

this link list will become longer

. This link will be longer,

which because it is longer automatically

results in a longer search time,

so

the retrieval is quite long and

with this chaining method, when we

want to use the link list, it

requires quite a

lot of memory. We have to prepare the memory

to prepare the link list

. So, one of the drawbacks is

higher memory usage.

Quite high memory usage.

Okay.

Well, the second method, what's the name of it,

that we can use for collusion

is eh, open addressing, right?

open tracing, which

can also

use

re-hashing

rehashing techniques. Okay. Well, ee, by definition

or simply put, this open opening

is looking for an empty slot

to fill the colluded

or collided data. It looks for the next

available slot or empty slot in the

hash table to fill with the

colluded data. Well, one way

to

find that slot or empty slot

is to apply

another rehearsing function or

another rehearsing technique. So, for

example, when uh 12 modulo 5 earlier it

produced 2 then 22 modulo 5 earlier

produced 2, yes, in the has table, index

number 2 is filled with the first one,

uh 12.

Now, for 22, what is the name? Eh,

with the open addressing method, it will

look for an empty slot after the

empty slot slide in the hash table

to be filled with the value 22. Maybe

after doing the search, it will be

here. The index doesn't know what number it is,

maybe 21, but it contains the value of 22

hashes. Okay and so on.

Well, this search is what we

know as rehearsing

. This rehearsing will also be called

rehassing, yes, or hashing that is done

again or repeated hashing, of

course it is a function again, yes. So

here we will use the second function to

look for the next ee index which is

empty.

we can use

other functions or we can use a

short technique, a simple technique,

for example linear, yes. For the reheing process

we can use linear. So,

maybe after filling in the value 12 in index

number 2, when we found

the collusion with the number 22, it turned out that

index number 3 was empty.

It could be because we filled 30 with 22.

Well, this is linear.

Well, what is he just looking for? He searches

sequentially for empty sequences. The

next empty slot sequence is immediately filled

with the colluding index.

Or we can also search with

certain intervals.

for example, from two, yes, to

store the number 22,

is it not just eh sorry, not looking for

what the next empty slot is, but the

empty slot, ee, is a multiple of two, so 2 4 6,

then the empty one will be

filled with 22, yes, something like that is

called quadratic, yes, so for those who are

rehearsing this, yes. For

this reheing process, we can use

linear to search for

empty slots sequentially

or in order. We can use

quadratic

probing linear probing for

sequential ones. Then quadratic probing

to search quadratically

based on certain intervals,

yes.

yes. Or we can also use

double hashing

or reharsing, namely using the

next function, the second function to

search for empty slots.

Okay.

Well, the advantage of using

open addressing is that it doesn't

use up too much memory. Doesn't

take up too much memory. So

what is the name of the space we use?

what's wrong? No, not much like

if we use chaining. But

there is a big possibility that clustering will occur

. The possibility of clustering occurring exists

because we, after searching,

for example, use double hashing.

Well, it turns out that the second function

also finds a slot that is already

occupied, so another collision occurs

. Well, that's clustering,

right? Well,

choosing which technique we want to

use really depends on

each case. We'd better

use a chain when, yes, in

our case, there are a lot of

changes. If there are a lot of

deletions,

it is better to use

chaining because if it is deleted,

for example, the link list will

be empty, so it is faster and takes

up less memory. But

when our memory is limited,

yes, our memory is limited, it is better

to use rehearsing or open

addressing

.

Well, in the open addressing technique

to overcome collusion, we

briefly looked at linear

probing and quadratic probing. Well,

these are two techniques that are also used if

we choose the open addressing technique

apart from the rehearsing mentioned

earlier.

Um

yes, if linear probing is as

explained earlier, searching for slots

sequentially, searching for cost slots

sequentially or

sequentially. Well, that automatically makes

this technique simpler

to implement quickly and

easily. Besides that, because

the data is sequential, the

performance is good for case by case.

Sequential access

always makes the case performance

better, right? Apart from that, it is also

efficient with memory, it doesn't

require

additional memory, it doesn't require

additional memory structures. Okay.

Well, but the downside is that there

could still be a clustering risk or a

tendency for EE to form clusters, yes,

that still exists and the high tendency is for

what? the cluster that occurred was still

high. So if clustering

occurs, it will result in ee ee

longer, what is it called?

What is this Longer called? Ee

ee ee

searching. I'm looking for the

Indonesian version. Search. Long search

. Remember the search. So remember, eh, the

linear probing technique and the quadratic

problem technique, eh, the quadratic problem probing, the

function or purpose of this is to

find empty slots, right? empty slot

search

empty slot search because of

collusion or collusion. Well, if

clustering occurs in the hash table, the

slot search in the H table will take

longer. So if the slot search

takes longer,

automatically when we do a

retrieval, it will increase the

search time too.

Well, it's different from quadratic probing

, its advantage is that it tries to

solve the clustering problems

that exist in linear probing. So,

rest clustering makes

the data more uniform,

the data is distributed fairly evenly, and the

spread is better. If we look at eh

good hashing is if eh uniform

ski distributions yes. So if the data is

evenly distributed, it indicates that

our hashing is optimal.

But it is

quite complex to have limitations

that must be what are they called? It is filled

before we use

this quadratic probing,

okay? such as load vector limitations.

If the load vector exceeds the threshold

or exceeds a certain limit, the

quadratic problem of quadratic

probing becomes a problem. Okay. So,

when do we use linear? When do

we use what is it called?

This is quadratic probing. Yes,

we use linear probing if, for example, our conditions

are

suitable for us to look for

simple things

that are easy. Simple and easy.

Then also if we prioritize the case

, prioritizing case performance,

we prioritize case performance

and the load factor is low.

low load

or low load low load factor yes. So

if our priority is simplicity and cash

performance, then it's better

to use linear probing.

But if

our main goal or priority is to

reduce clustering, then it's

better to use a

quadratic problem, to

reduce

the number of clusters, reduce the number of clusters, and the

loot factor, what's the name? It's

high.

high vector loot. Well, it's better to

use quadratic probing, yeah.

So, once again, if we

use linear probing,

we should prioritize simplicity

and cash usage, and one of

the indicators is that if our load factor is

low, we can immediately use linear. But

if the load factor is high, we

immediately use quadratic because it can

reduce the clusters that occur.

So, we saw earlier about open

addressing. Now we see that it

becomes eh we see separate chaining

or just chaining is actually often

called that, right? Yes, it has been repeated

many times regarding the use of

this chaining. We use a linked

list, yes. So for the hash table there is an

index. Then the second column of the hash table

is a linked list. Well, if the

link list is 15, then if the key is 15, that

means the hash value is 10, right?

For this link list, it occupies an

empty index, right? So, for the

data search or retrieval process,

we only

go to the ee index of the hash table

. Well, the processes that occur

in chaining clearly

require an insertion or

data entry process. Yes, for example, if we are

after the H table, we have to enter

the em key along with what the link list looks

like. If the

so-called link list is not yet

available, we just enter it directly.

If the key is not yet available in the

table, in the hash table, we just

enter it directly. But if the key is already

available in the hash table, then we

form a linked list because that means

collusion has occurred.

Well,

then there is a search process

in the hash table itself using the

link list method. So, if we want to

retrieve data, we have to do a

search process first to see which index our data is

at.

Yes, that's why, for example, if the

link list becomes longer, the

search process will automatically take longer.

Well, automatically a lot of collusion occurs,

right? If it's a link, if the link list

becomes long, it's usually long,

that's an indicator that there's

a lot of collusion, so you have to

fix the function, the hash

function. Because a good has function

should not

have many collusions, right?

Then there is delation. So,

if there is a

data change, the data is deleted, that

means it will remove

one of the values ​​in what is

called the

hash table. If for example

the ee link list only has one element and

that element is deleted, what does the index mean,

for example, what is it called?

At index 1, the only Q that exists is

21. When 21 is deleted, it means that the boarding slot eh 1

has index 1, which means it is an empty slot,

right?

Well, what's the name for?

eh chaining.

Well,

besides the simplicity of

chaining, it is simple and easy

to implement, so it is interesting

to implement it straight away. C

also has several shortcomings, as

we have seen in the previous slide,

namely that chaining requires a

lot of memory. So when we

choose to use a

training method, make sure we also have a

large enough memory. Why?

Because every element in the links,

eh, every element in the link list

in the has table, yes, it

definitely requires memory for pointers.

So if our link list is

long, our link list is long, it

will automatically take up a lot of memory. So,

this link is long and will take up

memory. Thus, the search time

will also increase significantly

. If time

increases, it will automatically have

an impact on performance.

performance or ability to

perform searches.

Well, eh cashing also has disadvantages,

especially in terms of eh cash performance,

yeah. maybe the link list might

experience pur eh have a

performance case that is not very good

because ee

ee the memory allocation is not

continuous, not sequentially yes.

For example, ee,

where was that on the previous slide? Um, wait

a minute,

ee,

this is for example,

for the one earlier, it seems like there was a

table that was quite long, but there wasn't one, right?

Oh okay.

For example, for the key value index

number 2,

what is the name of the circle? This is 20 12 22

32, not sequential, there

are still 13 14 15 and

so on, so that if for example the

storage is not sequential and

not sequential,

unordered storage like this or non-sorted,

it will take up memory and will also

reduce the search time too, right? So

that's the

drawback of what's it called ee

ee what's it called ee chain yeah.

CAS performance is a

fairly classic problem when we choose what is

called chaining. That's why it was

resolved with open addressing

. If you are focusing

on cash performance, it is better

to choose open addressing.

Okay, after we see how

hashing is done and the

benefits of hashing, eh, the performance

of the hand sori of this hashing is of

course, eh, what is it called, it is better if

we don't use hashing, yes, for

cases that, what are they called, yes,

when we apply, eh, the hashing process

or implement

hashing, ee, the average case is

close to O1,

yes, meaning it is better than if

we don't apply hashing,

eh, the time complexity is O N, yes,

for each insert, eh, search, and

delation. So, whatever we want to use,

whatever the hashing technique,

as long as we use hashing, it is

expected to be able to

make the performance of the insertion of the

search deletions in

our operation better,

increase the time or speed up

our time complexity.

Well,

earlier we saw two kinds of techniques,

eh eh hashing eh oh sorry, two kinds of

techniques to overcome chain

chain collusion and eh open addressing. We

also see how eh

chaining methods are done and how

open addressing is done.

Well, this is

just a summary or conclusion of the

operators of the chaining and open

addressing techniques to help you in

choosing

which collusion technique you want to use.

Yes, one way to choose eh

collusion eh technique is to look at the load

factor, yes. If the load factor is

large, it is better to

use chaining. So

ideally when your vector load is

between 1 and 3, it's better to

use the chain directly. Even though the

load factor is true, the load factor is getting higher

. And if the load vector,

the higher the vector load, the

lower the performance.

Performance is getting worse. So, if

we increase load vector 1 to load

vector 3, we hope that load vector 1 will be

faster than when we increase load vector

to 3.

So, for chaining, if our

load factor is more than one, it is

better to use a chain directly.

Because if we use open

addressing, the performance will

drop significantly when

it approaches one. So when the load

factor is below 1, yes, 0.6

or 0.7, below one, immediately

use opened racing. Ideally, the low

detector is 0.6 to 0.75. Well,

that's ideal for using

tracing, right?

And again, performance decreases

if the load is high. So, if the

load factor is less than one, it is

better to use the

ideal addressing of 0.6 to 0.7. That's

why in the previous slide

you saw that there are several constraints

that must be met when we

use open addressing. Okay,

so one of the concerns is

that this load vector must be less

than

one

. You can still use it, eh,

if your load factor is less

than one, you can use

chaining. Changing is fine, but it's

not optimal.

There is a more optimal option when the load

vor factor is less than one, namely open

addressing, right? Please feel free to

use any collusion technique you like

, but again, choose the

most appropriate one or the one that is

most profitable.

with your condition, yes.

Well, for the implementation

of hashing, it is widely used

for databases,

for database management, then

cash management, and password storage. Because it can be

said that hashing is also like an

encryption process. So for ee

password it is also quite ee good.

Okay. Well, the

factors

that make eh hashing eh can be

said to be good hashing

are that we have seen

uniformity earlier, right? If the key is distributed

uniformly, it is called

uniform

key

distribution. Well, that's sudden,

uh, what's it called? Our hashing is

good. Then efficiency. If it

increases our efficiency, from

our searches or our data retrieval,

it indicates that our hashing is

useful or good for us to implement. Yes,

the irreversibility issue is

related to the

actual password of this encryption. If for example

we can have several ee factors,

there are some things that we should

not be able to

restore the value or it is very difficult to

restore the original value for

protection problems such as this password.

So, for example, if we have

entered the functions of

this hash, the input hash function

, we enter the function, there must be a

mechanism, there must be a mechanism that is

sufficient, what is sufficient? It's safe enough or secure enough

so that we can see the original input.

Well, this is usually used by

passwords or ee encryption processes,

yes.

So it is not easy to restore the

original value to protect the

existing data.

Well, er, determinism means that

if the input is the same,

if the input is the same, it must

produce the same output too.

So

yes, if the input is the same, the output must

also be the same.

This is another word for consistency,

yes. So there should be no

randomization process that could cause the

input and output to be

different. That means later you won't be

able to, ee, what's it called? What we query

may not be able to retrieve ee

what is the name ee original data.

Right? Well, that is the material that we

can discuss regarding this ee hasing.