Хеш-таблица. Как квадратичное хеширование переделать в линейное?
Ребята, подскажите пожалуйста, как квадратичное хеширование переделать в линейное?
public class Hash_Table
{
DataItem[] hashArray; // Массив ячеек хеш-таблицы
int arraySize;
DataItem nonItem=null; // Для удаленных элементов
public Hash_Table(int size) // Конструктор
{
arraySize = size;
hashArray = new DataItem[arraySize];
// nonItem = new DataItem (-1);
}
// -------------------------------------------------------------
public void displayTable()
{
Console.WriteLine("Table: ");
for (int j = 0; j < arraySize; j++)
{
if (hashArray[j] != null)
{
Console.WriteLine(hashArray[j].getKey() + " " + hashArray[j].getValue() + " ");
}
else
Console.WriteLine("** ");
}
Console.WriteLine("");
}
// -------------------------------------------------------------
public int hashFunc1(int key) // для хэширования ключа
{
return key % arraySize;
}
public int hashFunc2(int key) // для расчета шага
{
int i = 1;
return (hashFunc1(key) + (i * i)) % arraySize;
}
public int hashFunc3(String key)
{
int hashVal = 0;
int pow27 = 1; // 1, 27, 27*27 и т. д.
char[] c = key.ToCharArray();
for(int j=c.Length-1; j>=0; j--) // Справа налево
{
int letter = Convert.ToInt32(c[j]) - 96; // Получение кода символа
hashVal += pow27 * letter; // Умножение на степень 27
pow27 *= 27; // Следующая степень 27
}
return hashVal % arraySize;
}
/// </summary>
/// <param name="key"></param>
/// <param name="item"></param>
public void insert(int key, DataItem item)
// (Метод предполагает, что таблица не заполнена)
{
int hashVal = hashFunc1(key); // Хеширование ключа
int i = 0;
while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1)// пустая ячейка или -1
{
i++;
hashVal = (hashVal + (i * i)) % arraySize;
}
hashArray[hashVal] = item;
}
public DataItem delete(int key) // Удаление элемента данных
{
int hashVal = hashFunc1(key); // Хеширование ключа
int stepSize = hashFunc2(key); // Вычисление смещения
while (hashArray[hashVal] != null) // Пока не найдена пустая ячейка
{ // Ключ найден?
if (hashArray[hashVal].getKey() == key)
{
DataItem temp = hashArray[hashVal]; // Временное сохранение
hashArray[hashVal] = nonItem; // Удаление элемента
return temp; // Метод возвращает элемент
}
hashVal += stepSize; // Прибавление смещения
hashVal %= arraySize; // Возврат к началу
}
return null; // Элемент не найден
}
public DataItem find(int key) // Поиск элемента с заданным // (Метод предполагает, что таблица не заполнена)
{
int hashVal = hashFunc1(key); // Хеширование ключа
int stepSize = hashFunc2(key); // Вычисление смещения
while (hashArray[hashVal] != null) // Пока не найдена пустая ячейка
{ // Ключ найден?
if (hashArray[hashVal].getKey() == key)
return hashArray[hashVal]; // Да, метод возвращает элемент
hashVal += stepSize; // Прибавление смещения
hashVal %= arraySize; // Возврат к началу
}
return null; // Элемент не найден
}
}