Таблица будет содержать несколько десятков тысяч элементов и, фактически, будет статична (т.е. после чтения из файла добавление элементов будет происходить довольно редко). А вот обращение к таблице - часто. Какая структура данных лучше подойдёт в данном случае?
KeSqueer Обычный массив (конструктор хеш-таблицы принимает предполагаемое максимальное число элементов). Проблемой при реализации хеш-таблицы будет скорее удаление элементов. Надо предусмотреть параллельный массив целых значений, хранящий для каждого поля исходного массива число коллизий.
l_inc У массива есть недостатки. 1) Если массив упорядочен (удобно для бинарного поиска), будет медленным добавление/удаление элемента. 2) Если массив неупорядочен, для поиска его нужно будет отсортировать (быстрой сортировкой или ещё какой). Удаление элемента остаётся сложной задачей, добавление происходит ещё дольше (т.к. перед добавлением надо удостовериться, что элемента с таким хешем ещё нет, т.е. сделать поиск). Если учесть, что удаление элементов мне, в принципе, не нужно, и коллизий точно не будет (64-битный ключ, 100 000 эл-тов, но не по этой причине), то сложность вставки элемента в центр массива в первом случае наводит на мысли об исползьовании двусвязного списка. Но в таком случае возникает две сложности: 1) нужно будет писать свой менеджер памяти, ибо фрагментация последней будет довольно большой; 2) непонятно, как осуществить быстрый поиск в данном случае. Как вариант можно попробовать такой вариант: разбить все хеши, скажем, по первому байту. Таким образом, получим 256 таблиц, примерно по 400 элементов в каждом (при 100 000 элеметнов в целом). В этом случае в разы сокращается время сортировки, время поиска остаётся примерно таким же. Будет ли это достойным вариантом?
кнут описывает 2 конструкции 1) таблица, где хэш является адресом в ней, а значение - ссылка на цепочку (вектор, массив, другой хэш) значений у которых хэш совпадает (коллизий). и добавляется и ищется и удаляется элементарно. 2) таблица, где адрес является продуктом хэша и спец функции для разрешения коллизий во всех кругом используется вариант 1. используйте и вы и ничего мудрить не надо
qqwe Это само собой, но вот с элементарностью Вы переборщили. Алгоритм, безусловно, прост, но вот как быть со временем?
KeSqueer с каким временем? алгоритм он 1, описан кругом, используется кругом. разница только в деталях (функция расчета хэша. способ разрешения коллизий, точнее контейнеры для их хранения)
например, для функции хэширования строки int hash = 0; for(char *pstr = str; *pstr; pstr++){ hash += *pstr; } hash %= 13; хэши для строк "aab", "aba", "baa" совпадут. как разрешать будете? поэтому и используются доп структуры. обычно простые, тк цепочки коллизий редко длинные. но можете и деревья прицепить
qqwe У меня такое ощущение, что вы не читали сообщений темы. Я писал как про то, что коллизий нет, так и про недостатки списка. Повторюсь: 1) хеш 64-битный, это 18,5E18 комбинаций. В таблице будет содержаться число элементов порядка 1E6. Теоретическая возможность существования коллизий, я не отрицаю, есть, но в моём случае их точно не будет. 2) в линейный список сложно добавлять элемент а) если массив держится отсортированным, вставка элемента в центр списка является трудоёмкой задачей (нужно сдвигать часть массива после позиции вставки). б) если массив неотсортирован, перед вставкой нужно проверить, нет ли уже элемента с таким хешем (т.е. провести сортировку и поиск, поскольку для неотсортированного массива придётся перебирать все элементы), что ещё дольше. Однако, если разбить всю таблицу на 256 подтаблиц по первому байту хеша, работа значительно упрощается. Идеальным вариантом вижу использовать avl-деревья. Но стоит ли овчинка выделки? Может быть достаточно вышеприведённого варианта?
Я когда писал хеш таблицу, скажу одно хеш брал crc32,так как именно он обеспечивал равномерное распределение по ячейкам. В других хешах колизий было очень много. Возми сорсы Sphinx Search Engine тм же се ест
СFF Вопрос не в выборе хеш-функции, а в выборе структуры данных для хранения пар ключ-значение. Выбранная хеш-функция обеспечивает хорошее распределение, низкую вероятность коллизий.
KeSqueer такое ощущение, что вы не читали теорию по хэш таблицам и счас морочите голову вместо того чтоб почитать теорию по этим простейшим алгоритмам. ну, или глянуть почти любые исходники с ними размер хэша должен соответствовать размеру таблицы. у вас есть комп с > (sizeof(YourElement))*(2^64) байт памяти? будут или не будут коллизии вы заранее не знаете. и потому способы разрешения предусмотреть должны. (имхо, вы плохо представляете для чего это было придумано) struct ListItem{ struct ListItem* next; // .... поля всякие ; struct ListItem* list_root = 0; void AddToList(struct ListItem* item){ item->next = list_root; list_root = item; } снова повторю, почитайте теорию. все это уже решено и все куда проще и не так. заодно и разберетесь что такое хэши и с чем их едят.
qqwe Почему Вы не можете принять тот факт, что коллизий нет? Это так, и не потому что , а просто так есть и всё. нет проверки, что элемент уже не содержится в списке. Хеш-функцию я тоже не выбираю, она задана и даёт 64 бита на выходе.
+1. Похоже, автор не понимает, что есть хеш-карта, и для чего она нужна. Возможно, путает с более общим понятием отображения. Но я бы всё-таки использовал (точнее таки использовал) вариант с функцией зондирования для разрешения коллизий. Во-первых, это чуть меньше памяти требует, во-вторых, не надо городить дополнительно никаких связных списков (обойтись только массивом) и, в-третьих, при удачно выбранной функции зондирования коллизия обойдётся дешевле.
KeSqueer 1) Хеш-функция не может давать 64 бита. Она даёт значения в диапазоне от нуля до числа элементов в таблице. Иначе это какая-то Вами выдуманная структура данных, не имеющая отношения к хеш-таблицам. Готовы выделить табличку размером в 2^64 элементов? Если да, то подыщите себе 128-битную машину. 2) Либо диапазон хешей, возвращаемых хеш-функцией должен искусственно сокращаться до числа элементов в таблице. Но тогда хеш-функцией называется функция, возвращающая уже сокращённый диапазон хешей, что возвращает нас к пункту 1. 3) Нет в хеш-таблицах никаких сортированных массивов!
KeSqueer Чего тут не понятного. Возьми не 64 бита, а 23бита да так чтобы коллизии были. Не нравятся хэши используй деревья к примеру AVL.
Попробую изложиться ещё яснее. Есть взаимно-однозначное соответствие между некоторыми данными и 64-хбитным числом. Это можно описать как std::set<uint64_t, data_t>, причем число вычисляется из данных с помощью некоторой хеш(?)-функции. Какая внутренняя реализация std::set при своей простоте будет давать приемлемые результаты для случая большого количества элементов (порядка 1е6)?
KeSqueer В общем случае это будет называться хеш-функцией. В контексте хеш-таблицы, содержащей элементы, от которых она находит хеши, уже нет (тогда исходный 64-битный хеш называется ключом). То, что Вы хотите, — отображение (тогда пост Pavia как раз в тему). Реализуется оно многими способами. Теперь важно разобраться, что для Вас является приемлемым результатом. 1) Если важна скорость, но приемлемо выделить табличку под 2^21 — 2^23 указателей (удачный выбор для порядка 10^6 элементов полезной нагрузки), то хеш-таблица — самое оно (21-23 бита для хеша хеш-таблицы находятся хешированием исходного 64-битного хеша). Поиск будет моментальным. 64-битный хеш используется для проверки "попадания". 2)Если желательно с памятью обращаться по-экономнее, но можно слегка поступиться скоростью, то берите самобалансирующееся дерево (в среднем 20 сравнений для поиска элемента понадобится). Кроме того, очевидное преимущество дерева в том, что оно позволит искать диапазоны значений. В то время, как хеш-таблица здесь бесполезна. Но это, похоже, не требуется.
qqwe В ком кругом? Я заглядывал в несколько реализаций хеш-таблиц, в glibc, gawk и ruby. Везде использовался вариант 2). Или glibc, gawk и ruby являют собою редкое исключение? Я один раз видел реализованный вариант 1), и это была хеш-таблица написанная мною в глубокой юности, по мотивам где-то услышанного описания принципа работы хеш-таблицы. Впоследствии, после прочтения Кнута, я тоже предпочитаю вариант 2).
