# Hash Tables

?
• Created by: arrey
• Created on: 23-04-19 10:32
What are Hash Tables
'Hash Tables are arrays which store data in and retrieve it from positions generated using a hash algorithm'
1 of 9
Why have them? Think Efficiency in Arrays
Because arrays hold a fixed data type, we are able to jump to the tem using an algorithm GIVEN ITS INDEX using a formula [Start Po + (Index * Field lenght))]. This Gives DIRECT ACCESS = Big O(1).
2 of 9
What happens if we don't have the index?
We would need to find the item in a linear fassion, hence Big O(n), so we lost the efficiency.
3 of 9
How can we try to make it efficient without Index?
To get back to O(1) Efficiency, we need a Hash Algorithm that can generate Index Values for our values to both place and relocate them; the calculated position is related to the value itself, making it reproducible.
4 of 9
What is a Hash Algorithm? Define
A function or algorithm which transforms a key (a value) into an address where the item may be stored.
5 of 9
Factors to be considered in our Hash Algorithm:
1) The Size of the array (needs to be big enough to accommodate). 2) The nature of the data (Numeric, text...)
6 of 9
Formula to hash Numeric Values
Address = Value MOD (Size of Array). Use Howard 2 practice https://www.dropbox.com/sh/6esie37qlk73l45/AABMaqW-bqJ9JBQi6GNj1RqCa/Hashing!%20D?dl=0&preview=Hash+Tables+Qns+%26+Answers.docx&subfolder_nav_tracking=1
7 of 9
Formula to hash Text
Address = (Sum of ASCII values) MOD (size of array). Revise via Howard.
8 of 9
What are Collisions?
When a Hash table tries to map two values in the same Index position. 2 Solutions: Open Addressing Or Closed Addressing
9 of 9

## Other cards in this set

### Card 2

#### Front

Why have them? Think Efficiency in Arrays

#### Back

Because arrays hold a fixed data type, we are able to jump to the tem using an algorithm GIVEN ITS INDEX using a formula [Start Po + (Index * Field lenght))]. This Gives DIRECT ACCESS = Big O(1).

### Card 3

#### Front

What happens if we don't have the index?

### Card 4

#### Front

How can we try to make it efficient without Index?

### Card 5

#### Front

What is a Hash Algorithm? Define