12.3.Hashing的实现方法(2)

发表于 更新于 分类于 ， 阅读次数： 本文字数： 344 阅读时长 ≈ 1 分钟

\(12.3\)\(Hashing\)的实现方法(2)

1.冲突处理

  假如我们得到一个对象的\(hashCode\)为\(h\)：

  • 当\(h\)索引不存在时，我们就对\(h\)索引创建一个新的LinkedList，并把这个对象插入链表中。
  • 当\(h\)索引存在时，我们就将对象插入已有的链表中。

  \(p.s.\)我们的数据结构是不允许重复的，因此在插入时，我们必须将待插入对象与链表中所有已插入对象进行比较。当该对象已经存在时，就直接跳过。这说明我们会需要遍历整个链表。

  这样，我们就可以得到\(Hashing\)的具体流程了：

  • add item

    • Get hashcode (i.e., index) of item.
    • If index has no item, create new List, and place item there.
    • If index has a List already, check the List to see if item is already in there. If not, add item to List.

  • contains item

    • Get hashcode (i.e., index) of item.
    • If index is empty, return false.
    • Otherwise, check all items in the List at that index, and if the item exists, return true.

2.内存的处理

  为了避免使用过大的数组，我们可以固定数组的大小，然后采用取模的方法，让所有的\(hashCode\)都落入该数组的索引范围内(类似我们在\(ArrayList\)中使用的方法)。就算此时发生了哈希冲突，我们也可以用上面的方法处理它。