HashTable是一块线性的连续区域，如下图：
┍━━━━┯━━━━┯━━━━━┯━━━┯━━━┯━━━┯━━━┑
┕━━━━┷━━━━┷━━━━━┷━━━┷━━━┷━━━┷━━━┙
每一格（或块）内存被称为Bucket。TableSize即为Bucket总数。Bucket实际对应一个由用户指定的ValueType。
Bucket状态有三种：Empty, Deleted, Good。
当插入一个Value时，检查Bucket，找出一个可用的Bucket。方法如下：
初始状态：输入<Key, Value>根据Key找到Table上的初始Bucket：h = hash(Key) à i = h & sizeMask àBuckets[i]检查当前Bucket是否为空，若为空，则跳转到8；否则继续。检查Key与否与当前Bucket上的值相等：Translator::equal(Extractor(Bucket), Key)。若相等，则return <Key_iterator, false>, false代表该Key已存在，插入失败；否则，继续。检查当前Bucket是否是Deleted Bucket。是，则由deletedEntry记录此Bucket。继续。重新计算i。（认为发生了冲突）当前Bucket = Buckets[i]跳转到3。如果deletedEntry存在，则清空此Bucket。并把此Bucket设为当前可用Bucket。deletedCount减一。HashTranslator::translate(Bucket, key, value)尝试Expandreturn <Key_iterator, true>。true代表插入成功。Expand的条件：Table为空或者(KeyCount + DeletedCount) * MaxLoad > TableSize。MaxLoad为系数，应该是实验值。目前为2。
转载于:https://www.cnblogs.com/lotushy/archive/2012/06/20/2556275.html
相关资源：数据结构—成绩单生成器