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?

Back

Card 4

Front

How can we try to make it efficient without Index?

Back

Card 5

Front

What is a Hash Algorithm? Define

Back

View more cards

Get Revising

Hash Tables