Hashing Performance (cont)
Two important measures for hash files:
- load factor: L = r/bc
- average overflow chain length: Ov = bov/b
Three cases for distribution of tuples in a hashed file:
| Case |
L |
Ov |
| Best |
≅ 1 |
0 |
| Worst |
>> 1 |
** |
| Average |
< 1 |
0<Ov<1 |
(** performance is same as Heap File)
To achieve average case, aim for 0.75 ≤ L ≤ 0.9.
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}