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