首先算一下 1e8 * 1% = 1000000个非零元素。
假设元素在矩阵中是处于均匀分布的。因此Hash表长度可以设置为1000000至少。
装填因子不能太大,但是这种情况下。还好
然后看看hash函数,可以这样设计
int Hash(int row, int col)
{
return row * 100 + col / 100;
}
明白这个意思嘛,每100个元素存一行的零元素。在这一百个元素的相对位移取列的压缩映射。
在遇到冲突的时候可以采用拉链法。
查找效率基本上是O(1)的,最好情况一次就可以查到,最差为100次