CSC2100B Tutorial 6

Chlaw

Description

CSC2100BTutorial 6 HashingTom Chao ZhouYi LIUMar 4, 2004{zzz{zzHashing - overviewHash functionCollision resolutionSeparate Chaining (Open hashing)Open addressing (Closed Hashing)Linear probingQuadratic probingDouble hashingCSC2100B Tutorial 2z{Hashing - hash functionHash functionA mapping function that maps a key to a number in the range 0 to TableSize -1int hashfunc(int integer_key){return integer_key % HASHTABLESIZE;}CSC2100B Tutorial 3zHashing - separate chainingIf two keys map to same value, the elements are chained together.CSC2100B Tutorial 4zzHashing - exampleInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining. The hash function is key % 10Initial hash tableCSC2100B Tutorial 5zzHashing - exampleInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining. The hash function is key % 1022 % 10 = 2After insert 22CSC2100B Tutorial 6zzHashing - exampleInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining. The hash function is key % 1084 % 10 = 4After insert 84CSC2100B Tutorial 7zzHashing - exampleInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining. The hash function is key % 1035 % 10 = 5After insert 35CSC2100B Tutorial 8zzHashing - exampleInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining. The ...

Informations

• Publié par: Fiwyug
• Nombre de lectures: 17
• Langue: English

Extrait

CSC2100B Tutorial 6 Hashing

Tom Chao Zhou

Yi LIU Mar 4, 2004

Hashing - overview

zHash function zCollision resolution {Separate Chaining (Open hashing) {Open addressing (Closed Hashing) zLinear probing zQuadratic probing zDouble hashing

CSC2100B Tutorial

2

Hashing - hash function

zHash function {mapping function that maps a key to aA number in the range0toTableSize -1

_ int hashfunc(int integer key) { }

_ return integer key % HASHTABLESIZE;

CSC2100B Tutorial

3

Hashing -

z

separate chaining

If two keys map to same value, the elements are chained together.

4

Hashing - example

zInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining.

zThe hash function iskey % 10

Initial hash table

CSC2100B Tutorial

5

Hashing - example

zInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining.

zThe hash function iskey % 10

22 % 10 = 2

After insert 22

CSC2100B Tutorial

6

Hashing - example

zInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining.

zThe hash function iskey % 10

84 % 10 = 4

After insert 84

CSC2100B Tutorial

7

Hashing - example

zInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining.

zThe hash function iskey % 10

35 % 10 = 5

After insert 35

CSC2100B Tutorial

8

Hashing - example

zInsert the following four keys 22 84 35 62 into hash table of size 10 using separate chaining.

zThe hash function iskey % 10

62 % 10 = 2

After insert 62

CSC2100B Tutorial

9

Hashing

zOpen addressing {Open addressing hash tables store the records directly within the array. {A hash collision is resolved byprobing, or searching through alternate locations in the array. zLinear probing zQuadratic probing zRandom probing zDouble hashing

CSC2100B Tutorial

10

Hashing - Open addressing

#define HASHTABLESIZE 51

typedef struct { int key[HASHTABLESIZE]; int state[HASHTABLESIZE]; /* -1=lazy delete, 0=empty, 1=occupied */ } hashtable;

/* The hash function */ int hash(int input) { return input % HASHTABLESIZE; }

CSC2100B Tutorial

11