对于hash表的理解

1. hash表的概念

    hash表技术是直接查找技术的推广， 其主要目标是提高查找效率。

2. 几种 hash 表

    <1>. 链式 hash 表。 这种 hash 表是在实际应用中最常用的 hash 表。如图所示
      
          |------|
          |      |--> 1 --> 11
          |------|
          |      |--> 2 --> 12
          |------|
          |      |--> 3 --> 13
            ...
            ...

         链式 hash 表的填入：
          · 计算关键字 K 的 hash 码 i = i(k).
          · 获得新的结点 P, 并将关键字 K 及有关信息填入结点P中。
          · 将结点 P 链入以 H(i) 为头指针的链表的链头。

         链式 hash 表的取出
          · 计算关键字 K 的 hash 码 i = i(k).
          · 在以 H(i) 为头指针的链表中查找关键字为 K 的结点。


    <2>. 溢出 hash 表。
          溢出 hash 表包括 hash 表与溢出表两部分。
          在 hash 表填入过程中，将冲突的元素顺序填入到溢出表中。
          而当查找过程中发现冲突时，就在溢出表中进行顺序查找。

    <3>. 顺序 hash 表是一种简单的 hash 表，其中存在很多问题，在实际开发中基本上不使用。

    <4>. 随机 hash 表。它与顺序 hash 表基本相同，只不过当发生冲突时它使用随即数来解决冲突。