Assume : | every even numbered slot occupied and every odd |

numbered slot empty | |

any hash value between 0 . . . m-1 is equally likely | |

to be generated. | |

linear probing | |

empty |

occupied |

empty |

occupied |

empty |

occupied |

empty |

occupied |

Expected number of probes for an unsuccessful search

= | (1) + (2) | ||

= | 1.5 |

eEL,CSA_Dept,IISc,Bangalore