хеш-функция для ключей 2х таблиц (вопрос по теории БД)

[Лысый]

хеш-функция для ключей 2х таблиц (вопрос по теории БД)

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

т.е. функция которая ставила в однозначное (односторонее) соответвие кажому ключу из одной таблицы - ключ из другой таблицы

реализовывать это предстоит так - функция имеющая на входе ИД1 таблицы 1 и выдающая ИД2 таблицы 2, причём алгоримтм желательно такой, что если со временем запись с ИД2 исчерзнет из таблицы 2, то функция выдаст некий ИД3

сразу скажу, что однозначное соответствие не обязательно, то есть может быть такое, что Ф(х)=К и Ф(у)=К, но очень желательно чтоб плотность покрытия множества ключей 2ой таблицы была максимальной

есть идеи?

спасибо.

 

[alexhemp]

Опиши реальную задачу. А это уже постановка решения типа "возьмем хеш ф-цию такую, что".

К теории БД хэш-фции отношения никакого не имеют.

 

[zerkms]

а может не придумывать всякое и просто сделать таблицу связей этих 2х таблиц??

 

[neko]

alexhemp
рекомендую посетить библиотеку.

Лысый
налицо непонимание.
написать такую функцию в общем случае невозможно.

рекомендую посетить библиотеку.

 

[idler]

zerkms полностью прав

Лысый
RTFM!!!!

 

[Лысый]

2 alexhemp
да ты что? а как по твоему поиски и прочие индексы реализованы?
почитай
http://citforum.ru/database/osbd/glava_39.shtml#_4_1_2_2

2 zerkms
не совсем удобно, это решение в лоб
дело в том, что таблицы не в одной БД
будет требоваться переодическая синхронизация с самими таблицами, а писанины тоже будет не мало
конечно придётся мучаться именно так, если ничего не придумаю

2 neko
непонимание чего? в общем случае конечно невозможно
но варинты возможны , самый убогий - ИД1=N сопоставляем ИД2 = N если такого нет - то ближайший по модулю из существующих, но такое перемешивание крайне не равномерное

вот и я ищю примеры хеш функций, которые давали бы большее перемешивание

2 idler

и какой Мануал на эту тему ты предлагаешь мне почитать?


Описываю задачи точнее
есть 2е таблицы записей,
надо огранизавать привязку записей из одной таблицы к записям из другой, произвольным образом
но поскольку задача решается под веб и таблицы храняться отдельно друг от друга- то
1) надо чтоб каждый раз при запросе можно было такую связь установить снова
2) случается что записи уничтожаются - значит надо установить новую связь с какой нить другой записью

-~{}~ 20.04.06 22:23:

З.Ы.
я понимаю, что чисто СКЛем эта задача не решаема
мне интересна именно сама идея алгоритма, а как его реализовать - это воторой вопрос

 

[neko]

Лысый

вот и я ищю примеры хеш функций, которые давали бы большее перемешивание

ты их не в том месте ищеш.
тут многие вообще незнают, что такое хеш-функция.

варинты возможны , самый убогий - ИД1=N сопоставляем ИД2 = N если такого нет - то ближайший по модулю из существующих, но такое перемешивание крайне не равномерное

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

вообще я даже незнаю с какого конца начать.

во-первых какая собственно проблема написать функцию?
классическое: f(k) = k mod m
или f(k) = m(kA mod 1) ты уже пробовал и оно не подошло?

во-вторых как ты собираешся разрешать коллизии?

 

[vadim]

Автор оригинала: Лысый
надо огранизавать привязку записей из одной таблицы к записям из другой, произвольным образом

Я честно говоря не могу понять, зачем между таблицами нужна случайная ("произвольным образом") связь??

 

[Лысый]

2 neko
классические в первую очередь пришли в голову, но не совсем подходят, так как f(k) = k mod m очень часто попадает на пустой номер... как раз вопрос какую функцию применять в таком случаее

2 vadim
ну я могу и рассказать, но это к самой задаче отношения не имеет

надо установить такое соответствие и точка
вопрос в функции

 

[!diss]

Самый простой ответ, который пришел в голову это преобразовать в int часть hex от MD5()

 

[Лысый]

не совсем понял
поясни плз

 

[Wicked]

Лысый
он сам не понял

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

 

[Лысый]

ну если говорить прямо, мне надо создать видимость случайных односторонних связей, ну из серии "Вася любит Машу" или "Москва находится в России"
поскольку мы с вами живём в Вебе, то читают эту связь через запросы к различным УРЛ
если мы 10 раз обратились по некому УРЛ ВАСЯ то нам надо 10 раз получить одну и ту же ссылку на МАШУ
какие сложности?
1) надо перемешать случайно
2) мужики на одном сервере - женщины на другом, синхронизации нет
3) надо чтоб если Маша вдруг умерла - функция предложила бы следующую женщину
4) ещё раз напомню, что при одном и том же входящем параметре ВАСЯ функция ВСЕГДА должна выдавать МАШУ, если она не умерла


я это вижу только некой хешфункцией ИДентификаторов ВАСЬ и МАШ, которая более менее равномерно покрывает одно множество другим, при этом вычисляется до победного и даже при изменении множества при одном и том же параметре даёт один и тот же ответ

мне кажется, это какой-то математический алгоритм зависящий исключительно от одной переменнной (ИД ВАСИ) и циклично вычисляющий ИД разных МАШ, пока не попадёт в живую.
я сначала думал что это невозможно, так как после изменения таблицы с МАШАМИ повторное вычисление ИД МАШИ может закончится раньше чем первое, но потом вспомнил, что это не возможно в автоинкрементных таблицах.

вот такой бред.

 

[Andreika]

вообще если б во 2ую базу ничего не дописывалось, то можно было бы использовать
[sql]SELECT * FROM table ORDER BY /*ABS(*/RAND(id-IVAN_ID)/*-RAND(IVAN_ID))*/ LIMIT 1[/sql]
равномерное покрытие, независимость от удаления строки, но.. при добавлении очередной маши нехилый шанс, что она займет чужое место.. впринципе равномерность и различное кол-во строк по времени - вещи несовместимые

 

[dr-sm]

Лысый

я это вижу только некой хешфункцией ИДентификаторов ВАСЬ и МАШ, которая более менее равномерно покрывает одно множество другим, при этом вычисляется до победного и даже при изменении множества при одном и том же параметре даёт один и тот же ответ

математически у тебя отображение y = X(m, F)
целого числа m - "ID Васи",
на упорядоченное множество целых чисел F - "Маши".

0) если F != [], то для любого m существует у из F,
такое что y = X(m, F).
т.е. для каждого Васи, есть Маша.

1) для любого множества N каждый элемент которого > max(F),
(N может равняцо []) выполняецо: X(m, F) = X(m, [F + N]).
если мы добавили новых Маш, то на Вась это не влияет - забавно да.
вроде пришли к бессмыслице, а Маши еще не умирали ?
решить можно добавлением 2го параметра hint'a h = max(F);

вот такой вот бред...