假设我有一个包含 59 个元素的哈希表(每个元素值都是一个整数)。索引 15 是空白的,表的其余部分都是数据。根据我要插入的数字,二次探测公式永远不会达到元素 15!
假设我想插入数字 199(应该使用我在下面使用的 hashFunc() 函数散列到 22。:
public int hashFunc(int key)
{
return key % arraySize; //199 % 59 = 22
}
public void insert(DataItem item)
{
int key = item.getKey(); // extract the key (199)
int hashVal = hashFunc(key); // hash the key (22)
int i = 1;
//The while loop just checks that the array index isn't null and isn't equal to -1 which I defined to be a deleted element
while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1)
{
hashVal = hashFunc(key) + (i * i); //This never hits element 15!!!
i++;
hashVal %= arraySize; // wraparound when hashVal is beyond 59
}
hashArray[hashVal] = item; // insert item
}