Xem mẫu
- Skip List: Implementation
S3
S2 34
S1 23 34
S0 12 23 34 45
- Lecture No.41
Data Structure
Dr. Sohail Aslam
- Implementation: TowerNode
head tail
Tower Node
20 26 30 40 50 57 60
TowerNode will have array of next pointers.
Actual number of next pointers will be
decided by the random procedure.
Define MAXLEVEL as an upper limit on
number of levels in a node.
- Implementation: QuadNode
A quad-node stores:
• item
quadnode
• link to the node before
• link to the node after
• link to the node below
• link to the node above x
This will require copying the
key (item) at different levels
- Skip Lists with Quad Nodes
S3
S2 31
S1 23 31 34 64
S0 12 23 26 31 34 44 56 64 78
- Performance of Skip Lists
In a skip list with n items
• The expected space used is proportional
to n.
• The expected search, insertion and
deletion time is proportional to log n.
Skip lists are fast and simple to implement
in practice
- Implementation 5: AVL tree
An AVL tree, ordered by key
key entry
insert: a standard insert; (log n)
find: a standard find (without
removing, of course); (log n) key entry key entry
remove: a standard remove;
(log n) key entry
and so on
- Anything better?
So far we have find, remove and insert
where time varies between constant logn.
It would be nice to have all three as
constant time operations!
- Implementation 6: Hashing
An array in which
TableNodes are not stored key entry
consecutively
Their place of storage is
4
calculated using the key and
a hash function
10
hash array
Key index
function
123
Keys and entries are
scattered throughout the
array.
- Hashing
insert: calculate place of
storage, insert
key entry
TableNode; (1)
find: calculate place of
4
storage, retrieve entry;
(1) 10
remove: calculate place
of storage, set it to null;
(1) 123
All are constant time (1) !
- Hashing
We use an array of some fixed size T to
hold the data. T is typically prime.
Each key is mapped into some number
in the range 0 to T-1 using a hash
function, which ideally should be
efficient to compute.
- Example: fruits
Suppose our hash function 0 kiwi
gave us the following 1
values: 2 banana
hashCode("apple") = 5 3 watermelon
hashCode("watermelon") = 3
4
hashCode("grapes") = 8
hashCode("cantaloupe") = 7 5 apple
hashCode("kiwi") = 0 6 mango
hashCode("strawberry") = 9 7 cantaloupe
hashCode("mango") = 6
hashCode("banana") = 2 8 grapes
9 strawberry
- Example
Store data in a table 0 kiwi
1
array:
table[5] = "apple"
2 banana
table[3] = "watermelon" 3 watermelon
table[8] = "grapes" 4
table[7] = "cantaloupe" 5 apple
table[0] = "kiwi"
table[9] = "strawberry" 6 mango
table[6] = "mango" 7 cantaloupe
table[2] = "banana" 8 grapes
9 strawberry
- Example
Associative array: 0 kiwi
1
table["apple"]
2 banana
table["watermelon"]
table["grapes"]
3 watermelon
4
table["cantaloupe"]
table["kiwi"] 5 apple
table["strawberry"] 6 mango
table["mango"] 7 cantaloupe
table["banana"] 8 grapes
9 strawberry
- Example Hash Functions
If the keys are strings the hash function is
some function of the characters in the
strings.
One possibility is to simply add the ASCII
values of the characters:
length 1
h( str ) str[i ] %TableSize
i 0
Example : h( ABC ) (65 66 67)%TableSize
- Finding the hash function
int hashCode( char* s )
{
int i, sum;
sum = 0;
for(i=0; i < strlen(s); i++ )
sum = sum + s[i]; // ascii value
return sum % TABLESIZE;
}
- Example Hash Functions
Another possibility is to convert the string
into some number in some arbitrary base b
(b also might be a prime number):
length 1
h( str ) str[i ] b i %T
i 0
0 1 2
Example : h( ABC ) (65b 66b 67b )%T
- Example Hash Functions
If the keys are integers then key%T is
generally a good hash function, unless the
data has some undesirable features.
For example, if T = 10 and all keys end in
zeros, then key%T = 0 for all keys.
In general, to avoid situations like this, T
should be a prime number.
nguon tai.lieu . vn
