[C] хэш списков в линейный список

тоесть 4000 списков - каждый список в ней элементы один и тотже ХЕШ имеют ? так ?

а чтоб долго нелочила - лочить нужно имхо только при удалении элемента - все остальное может и так работать

~4000 списков, в какой конкретно список добавлять элемент определяет хэш функция, сейчас я тупо прогоняю два вложенных цикла и вывожу результаты, при большом кол-ве элементов может занимать существенное время

хм, может не мучатся преждевременной оптимизацией и посмотреть что получится в результате :-)

собственно это libalias
и там lock-и используются, когда оно крутится в ядре FreeBSD, буду раскруивать, зачем они лочат при поиске

Я не знаю, что там у вас во FreeBSD, но наши люди для поиска по конкретному значению используют сбалансированные деревья.

для поиска по конкретного значения - лучше хеша трудно чтото представить

сбалансированное дерево - это и есть своеобразный хеш :)

сбалансированное дерево - это и есть своеобразный хеш :)

Ну-ну. Только вот находит дерево за O(log n) в противовес O(n)

4000 — это не так уж и мало.

находиться дерево ? вообщето в хеще - нахождения дерева независит от колва деревьев
O(1) иль как там

и незабываем про занесение данных - балансировки дерева и так далее

как чувствовал, что про FreeBSD не надо было упоминать

наши люди это кернел-девелоперы? вы так толсто намекаете посмотреть в nf_nat\nf_conntrack мм?

дак :) уж название сайт то какое


кстати интересно - чтото более сложное чем хеш и очереди - используються ли в ядрах ?
балансированные деревья и так далее

(reiserfs там то на деревьях вся она) а еще ?

в линуксе, например для таблиц маршрутизации можно выбирать структуру хранения маршрутов, это я на nag.ru как-то прочитал

но не думаю что в моем случае возможно менять уже работающую и отлаженную структуру данных

Про FreeBSD была шутка :)

Я не кернел девелопер, просто действительно линейный поиск при немалом объёме данных режет глаза. Если я чего-то не понимаю, объясни, зачем в ядре неоптимальный медленный код?

и незабываем про занесение данных - балансировки дерева и так далее

Занесение данных — да, log n в противовес единицы. Зато поиск и удаление быстрее. На порядок.

какой линейный список, хм, может я слишком многословен
данные хранятся в хэше и хэш функция распределяет на ~4k элементов
где линейная структура?
вы как теоретик или практик спрашиваете? а то, теоретики придя на конкретную программную платформу встречаются с суровой реальностью, знаете ли

Предлагаю начать всё же с теории.

Хэш-функция ставит объекту в соответствие целое число, так? Далее: оно хранится в списке. Это линейный список или хэш-таблица?

>Хэш-функция ставит объекту в соответствие целое число, так? Далее: оно хранится в списке. Это линейный список или хэш-таблица?

да, это линейный список
теория меня сейчас мало волнует, хотя если вы предложите относительно простой способ улучшить эту структуру, я не против 8-)

Если интересно, можно посмотреть в сторону красно-чёрных, например, деревьев.

хеш функция - дает значение от 0 до 3999
есть массив обьемом 4 тонны указателей - указатели ведут на заголовок линейной очереди(списка)

хеш + список - самое простое и эффективное решение

Гм, читал вопрос и комментарии, но так и не понял задачу.
Может, приведешь псевдокод? Что сейчас есть и чего хочешь добиться?

указатели ведут на заголовок линейной очереди(списка)

4000 указателей, ведущих на один и тот же элемент. Их вполне можно было заменить одним.

>4000 указателей, ведущих на один и тот же элемент. Их вполне можно было заменить одним.

откуда это :-(
что-то я видимо совсем объяснять не умею

зайдем с другой стороны, есть хэш-таблица(я таки посмотрел как оно зовется в википедии) и вам надо с нее брать в любой момент времени линейную список чтобы вывести скажем на экран и при этом, чтобы уже работающий код который добавляет\удаляет\ищет не сломался и вот вы ходите вокруг как кот у сметаны и мыслите, не очень оно пострадает если вы тупо будете перебирать все элементы или стоит паралельно завести струкутру которая будет содержать ту же информацию, но только для чтения всех данных или части их

> и вам надо с нее брать в любой момент времени линейную список

Это уже не смешно.

Анто́н Па́влович? Вы!? В чем проблема?

каждый указатель ведет на свой список - если для этого хеша нет элементов - то указатель показывает в нуль
стандартная схема

а тут вопрос - в структуре базы этой - иль в правильной работе с lock-ами
?

вопрос отошел на один шаг назад в цепочке моих рассуждений
что предпочтительней использовать лочить основную структуру или как то извернутся и не лочить :-)
так как операция «вывода на экран» значительно менее приоритетная чем поиск\добавление\удаление

а ответ все тотже - лочить тока удаление :)

Как только хэш-таблицу с цепочками коллизий не обзывают.
Может лучше использовать открытую адресацию или вообще отказаться от хэш в пользу других структур данных?

страшно, продукт рабочий, просто сверху прилаживаю нашлепку
там есть mutex но они сразу на всю хэш-таблицу, что мне кажется не очень ок, при чтении не будет основной и более приоритетный процесс :-(

думаю завести массив мутексов, вся-ко полегче будет :-)
или может есть близкая по духу структура легкая в синхронизации, когда есть более приоритетные писатели и менее приоритетные читатели для которых не особенно важна полнота информации, ну и поиск\добавление\удаление, чтобы ок