数组里面每一个槽位放的是8个字节，用于一个指向外部类的引用。这个外部类可以是链表对象，也可以是红黑树对象，都可以存一个或者一个以上的元素，也可以是空链表或空树。散列表在某种意义上需要的数组空间可以比直接寻址表要少的很多。

除了线性探测法，还有二次探测还有双重探测。

线性探测法是，通过散列函数得到散列值，检查这个散列值是否被占用，如果被占用，将索引增大，到达数组结尾时折回数组的开头，直到找到没有被占用的散列值。

线性探测采用的散列函数为：

双重探测采用的散列函数为：

显然，短小的键簇才能保证较高的效率，不管是插入、查找还是删除算法。随着插入的键越来越多，较长的键簇越来越多，有可能插入一个元素就将两个很长的键簇合并。所以才有了两次探测和双重探测，可以降低这种情况出现。

面试官很客气，一直送我到门口，我依依不舍地离开这个地方。嗯，面试官真是个好人。

我出去大门，看见一个面试者在拿着A4纸一直默读，我想那个面试官待会要面这个人吧。小伙子，你运气真好，希望你面试成功。