деревья

смотри в сторону glib

* dev-libs/glib
Available versions: 1.2.10-r5 2.6.5 2.8.4 2.8.5
Installed: 1.2.10-r5 2.8.5
Homepage: http://www.gtk.org/
Description: The GLib library of C routines
License: LGPL-2

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

> ...а как при хешировании, если стуктура данных - деревья - решать проблему коллизей ?

Странный вопрос...

1. Зачем тебе хеш, если у тебя дерево? Что ты собрался хэшировать?

2. Вообще говоря, один из способов решения коллизий и есть деревья -- они позволяют приблизить worst case хэша к логарифму.

По теме:

http://www.stanford.edu/~blp/avl/

Еще всякая туфта встречалась, например,

http://softwaresensation.com/memsl/bintree.html

RB деревья:

http://libredblack.sourceforge.net/

Вообще, много есть. Я, помнится, с десяток сходу наковырял, но потом, как всегда, самописное оказалось лучше ;)

Спасибо за ссылки.

На счет коллизий. Я в этом деле новичек. В дереве предполагая хранить текстовые данные (т.е. структуры, ключом для котрых является текстовая строка, длиной не больше 20-30 символов латиницы), от нескольких тфсяч до миллиона (точно сам не знаю сколько получится). Т.к. поиск по текстовым строкам медленне, чем по цифровым, решил использовать хеш функцию для перевода строки в число....хм, по-моему я понял ошибку. Если использовать ту же конкатенацию битовых образов - т.е. просто перервд строки в число, без хеширования - то коллизий же не возникнет вообще?

anonymous (*) (19.01.2006 14:58:18):

> Т.к. поиск по текстовым строкам медленне, чем по цифровым, решил использовать хеш функцию для перевода строки в число...

При вычислении хеша ты пройдешь ВСЮ строку. Для сравнения двух строк ты должен обе их пройти ЦЕЛИКОМ. И потом все равно их сравнивать (если хэши совпадают).

При сравнении двух строк ты пройдешь их только до первого несовпадающего элемента. Так что дерево _в_этом_смысле_ ЗАВЕДОМО оптимальнее.

> Если использовать ту же конкатенацию битовых образов - т.е. просто перервд строки в число, без хеширования

Неверно.

То, что ты описАл (если я правильно понял) и есть один из классических алгоритмов хэширования. Коллизии там, ессно, возникают.

Ок, спасибо за ответ.

А того что есть в стандартной STL (std::set и std::map) не достаточно? Правда это C++ а не C...

> > Если использовать ту же конкатенацию битовых образов - т.е. просто перервд строки в число, без хеширования

> Неверно.

> То, что ты описАл (если я правильно понял) и есть один из классических алгоритмов хэширования. Коллизии там, ессно, возникают.

Если я правильно понял, под конкатенацией здесь понимается представление строки в виде длинного целого (то есть, практически без преобразования). В этом случае, коллизий (IMHO) быть не должно, другой вопрос, что потребутся инструмент для работы с такими числами и неизвестно, насколько это будет эффективнее работы со строками.

Автору вопроса: кто-нибудь из нас понял правильно, что имелось в виду? :)

#define _GNU_SOURCE
#include <search.h>

void *tsearch(const void *key, void **rootp,
     int(*compar)(const void *, const void *));
void *tfind(const void *key, const void **rootp,
     int(*compar)(const void *, const void *));
void *tdelete(const void *key, void **rootp,
     int(*compar)(const void *, const void *));
void twalk(const void *root, void(*action)(const void *nodep,
                                          const VISIT which,
                                          const int depth));
void tdestroy (void *root, void (*free_node)(void *nodep));

DKorolkov:

> ...потребутся инструмент для работы с такими числами и неизвестно, насколько это будет эффективнее работы со строками.

С точки зрения компьютера строка и есть длинное число, так что ничего никуда переводить не надо, все и так уже "сконкатенировано".

Хэш-функция однозначно отображает это число на поддиапазон аппаратно представимых целых. Один из классических алгоритмов -- "конкатенация" байтов с XOR'ом и циклическим сдвигом.

> > ...потребутся инструмент для работы с такими числами и неизвестно, насколько это будет эффективнее работы со строками.

> С точки зрения компьютера строка и есть длинное число, так что ничего никуда переводить не надо, все и так уже "сконкатенировано".

Под "длинным целым" я имел в виду число, которое длиннее машинного слова, и которое нельзя обработать одной командой. То есть, я предположил, что автор вопроса собирается работать со строкой как с длинным целым числом.

> Хэш-функция однозначно отображает это число на поддиапазон аппаратно представимых целых. Один из классических алгоритмов -- "конкатенация" байтов с XOR'ом и циклическим сдвигом.

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

В общем Die-Hard меня понял правильно. Единственное, для чего мне нужно было хеширование - перевести строку в целое чилсо чтобы ускорить поиск. Т.к. перевести строку любой длины (в моем случае длина лишь ориентировояная) в дипазон представления хотя бы long нереально, то буду использовать поиск по строкам. Наверное это не внесет критической задержки поиска

2DKorolkov:

Это все слова.

Я имел в виду такой алгоритм:

uint bits_in_int,bits_in_int_1,j;

for(bits_in_int=0,j=1;j;j<<=1,bits_in_int++);
bits_in_int_1=bits_in_int-1;

uint strhash(char *str, uint tsize)
{
uint h=0;
   while(*str){
     h=(h<<1)|(h>>bits_in_int_1);
     h^=*str++;
   }
   return h % tsize;
}