Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

2.3.4. П
РОЕКТ 
«Т
ЕЛЕФОННЫЙ СПРАВОЧНИК
» 
Рассмотрим работу с хеш-таблицей на примере простейшего телефон-
ного справочника. В каждом элементе хеш-таблицы будем хранить структу-
ру, содержащую два строковых поля: номер телефона и фамилию абонента. 
struct TInfo 
{ 
public string phone; 
public string fio; 
} 
В качестве ключа будем использовать номер телефона. Тогда можно 
предложить хеш-функцию, код которой представлен в листинге 2.11. 
Листинг 2.11. Хеш-функция 
int hashKey(string s) 
{ 
int result = 0; 
10 / 23

---

34 
for (int i = 0; i < s.Length; i++) 
{ 
result += Convert.ToInt32(s[i]) * i; 
result %= sizeTable; 
} 
return result; 
} 
Выбор хеш-функции является самой сложной проблемой хеширования. 
В этой функции с целью исключения коллизии для телефонных номеров (на-
пример, 123456 и 654321) суммируются коды цифр с весами, равными поряд-
ковому номеру цифры. 
Операции с хеш-таблицей: 
− добавление элемента в таблицу; 
− удаление элемента из таблицы; 
− поиск элемента в таблице. 
При выполнении этих операций могут возникать коллизии и поэтому 
необходимо предусмотреть метод их разрешения. Будем использовать метод 
открытой адресации с линейным поиском. Из дальнейшего станет ясно, что 
для реализации функции поиска необходимо наличие у элемента хеш-
таблицы признаков посещаемости и занятости. Таким образом, структура 
элемента хеш-таблицы должна иметь следующий вид: 
Листинг 2.12. Структура элемента в хеш-таблице 
struct THashItem 
{ 
public TInfo info; 
public bool empty; // 
признак занятости 
public bool visit; // 
признак посещения 
} 
Создадим класс для работы с хеш-таблицей.