Если не сказано иное, в хеш-таблице должно быть изначально >= 50 элементов.
Если не сказано иное, ключи сравниваются строгим совпадением их содержимого.
Если не указана хеширующая функция, подберите её на своё усмотрение. Помните, что H(K1) должно быть равно H(K2) когда K1 == K2.
Там, где указана в качестве ключа или значения структура, можно использовать как непосредственно структуру, так и указатель на неё, если не сказано иное.
Там, где указан массив строк или структур, выделение памяти под содержимое массива должно быть динамическим (т.е., с помощью calloc).
Если требуется игнорировать регистр для хеширующей функции, приводите перед хеширование символы к нижнему регистру, не к верхнему.
Разрешаются и рекомендуются к использованию все стандартные функции языка C (переизобретать фукнции вроде strlen() и strchr() не надо).
Вариант 1: ключ: структура struct birthday { int day, month, year; } (нумерация дня и месяца с 0) значение: строка хеширующая функция: year*12*31 + month*31 + day Вариант 2: ключ: строка значение: строка сравнение ключей: точное совпадение не-пробелов; пробелы в начале и конце строки не должны учитываться, любые последовательности пробелов внутри строки должны считаться как один пробел
Вариант 3: ключ: double значение: строка сравнение ключей: с точностью до 0.01 (т.е., ключи 0.12, 0.123 и 0.129999999) должны считаться одинаковыми хеширующая функция: последние три разряда целой части ключа (в десятичном представлении).
Вариант 4: ключ: строка значение: строка сравнение ключей: по первому слову в строке без учёта регистра (вставка строк без слов не должна допускаться) хеширующая функция: сумма кодов символов
Вариант 5: ключ: строка с цифрами и пробелами значение: строка такой же длины, как ключ сравнение ключей: точное совпадение цифр, пробелы никакие не учитываются хеширующая функция: длина строки
Вариант 6: ключ: строка значение: struct { char manuf[200]; char model[200]; } сравнение ключей: сравнение строк без учёта пробелов и регистра букв
Вариант 7: ключ: строка вида ГГГГ-ММ-ДД значение: массив указателей на struct { char *firstname, *lastname; int year }, последний элемент всегда NULL; добавление/обновление значения требует заполнения всех полей хеширующая функция: любое взаимооднозначное преобразование ключа в целое число
Вариант 8: ключ: строка — нормализованный путь в файловой системе (гарантируется отсутствие ".." и удвоенных разделителей пути) значение: булево сравнение ключей: сравнение строк (под Windows — без учёта регистра) хеширующая функция: количество элементов пути ("C:\\foo\\bar" — 3 элемента, "/q/w/e/r" — 4), умноженное на среднюю длину одного элемента; элементы разделяются '/' или '\\', на выбор.
Вариант 9: ключ: struct { int week; int wday; int pair; char auditory[8]; } значение: struct { char teacher[200]; } сравнение ключей: week, wday, pair — точное совпадение; auditory — сравнение строк без учёта регистра. хеширующая функция: ((week<<18) + (wday<<11) + pair) ^ (aunum), где aunum — unsigned long long, взаимооднозначно получаемый из auditory
Вариант 10: ключ: число произвольной точности в виде строки (цифры и не более одной точки) значение: число с плавающей запятой сравнение ключей: сравнение строк
Вариант 11: ключ: строка с датой вида ГГГГ-ММ-ДД значение: массив строк, последний элемент массива всегда NULL сравнение ключей: сравнение строк хеширующая функция: любое взаимооднозначное преобразование ключа в целое число
Вариант 12: ключ: строка вида ГГГГ-ММ-ДД ЧЧ:ММ:СС.ККК (ККК — миллисекунды) значение: double сравнение ключей: сравнение от ГГГГ до ММ включительно; при обновлении значения ключ также должен обновиться
Вариант 13: ключ: строка — автомобильный номер, включая трёхбуквенный код страны, без пробелов, буквы только латинские по принципу похожести написания значение: struct { char regdate[8]; char owner[200]; } сравнение ключей: сравнение строк без учёта регистра
Вариант 14: ключ: int значение: текстовая строка сравнение ключей: равными считаются ключи со значениями одного порядка (13 и 42, 543 и 345, но не 13 и 543)
Вариант 15: ключ: строка — полное доменное имя (строка из латинских букв, цифр, дефиса и точки, заканчивающаяся точкой) значение: массив 32-битных целых чисел сравнение ключей: сравнение строк без учёта регистра хеширующая функция: количество элементов имени ("president.kremlin.ru." — три элемента), умноженное на среднюю длину одного элемента
Вариант 16: ключ: строка значение: массив указателей на struct { int goals, shots, removals; }, последний элемент массива всегда NULL сравнение ключей: сравнение строк
Вариант 17: ключ: строка значение: массив строк, последний элемент массива всегда NULL сравнение ключей: без учёта регистра хеширующая функция: среднее значение кода символа в строке (хеш типа float)
Вариант 18: ключ: строка, закодированная в Base64 значение: struct { double latitude, longtitude; int year; } сравнение ключей: сравнение строк хеширующая функция: исключающее ИЛИ декодированных символов ключа; функцию декодирования можно взять, например, из Apache: ap_base64.c https://github.com/dhamidi/apache-httpd-1.3.42/blob/master/src/ap/ap_base64.c
Вариант 19: ключ: случайное целое число, генерируемое функцией rand() значение: int 1 количество элементов: от 100 до 10 000 000 задание: произвести измерение производительности операций на различных размерах (минимум 6 разных размеров). Каждое измерение должно производиться минимум три раза. Доверительный интервал ±7%. Все измерения должны производиться за один запуск программы, результаты измерений должны выводиться сводной таблицей.
Вариант 20: ключ: название города значение: struct { char *country; int population; } сравнение ключей: без учёта регистра, пробелов и знаков препинания
Вариант 21: ключ: строка с ФИО (не более четырёх слов, слова отделяются пробелами, формат: [префикс] фамилия имя отчество) значение: булево сравнение ключей: без учёта регистра хеширующая функция: каждый октет 32-битного целочисленного хеша (unsigned int) — сумма кодов символов (используются только младшие 8 разрядов суммы), соответствующего по порядку поля ключа. Например, для «de Wansa Viktor Vikramaratne» получится 0xC9FA7FE5.
Вариант 22: ключ: struct { size_t len; unsigned char *data; } значение: struct { size_t len; unsigned char *data; } сравнение ключей: побайтовое сравнение значения длиной len, доступного по указателю data. хеширующая функция: сумма значений всех байтов в data.
Вариант 23: ключ: последовательность цифр от 0 до 9 в виде строки, без каких-либо ещё символов значение: строка сравнение ключей: сравнение поразрядно, игнорируя нули
Вариант 24: ключ: палиндром в виде строки значение: struct { int refs; } сравнение ключей: сравнение строк, игнорируя регистр, пробелы и знаки препинания хеширующая функция: сумма значений первой (или второй) половины символов, игнорируя регистр, пробелы и знаки препинания
Вариант 25: ключ: короткая текстовая строка (до 10 символов), состоящая только из букв верхнего регистра и цифр значение: struct { char plane_model[60]; char gate[4]; char take_off_time[16]; } сравнение ключей: сравнение строк
Вариант 26: ключ: double значение: текстовая строка сравнение ключей: равными считаются ключи со значениями одного порядка (345 и 901, 0.12 и 0.74, но не 0.12 и 0.07)
Вариант 27: ключ: число от 1 до 99 включительно значение: массив строк, последний элемент массива всегда NULL
Вариант 28: ключ: текстовая строка вида «AAAA-BBBBBBB», где первая часть («AAAA») одинаковая у многих ключей; обе части состоят только из букв и цифр значение: struct { char *mnfct; int mfct_year; int cap_year; } хеширующая функция: сумма значений символов второй части.
Вариант 29: ключ: struct { int data[50]; } значение: struct { int data[50]; } сравнение ключей: побайтовое сравнение значения длиной len, доступного по указателю data. хеширующая функция: исключающее ИЛИ всех значений в data.
Вариант 30: ключ: строка в виде набора разделённых пробелами слов значение: массив строк, последний элемент всегда NULL сравнение ключей: сравнение строк, игнорируя пробелы, регистр, а также слова, заканчивающиеся точкой (сокращения типа «ст.», «пл.» и т.д.).