12.3.Hashing的实现方法(2)

\(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\)中使用的方法)。就算此时发生了哈希冲突,我们也可以用上面的方法处理它。