Реализация хэш-таблицы на C.

думаю, тут проще использовать плюсовый map из stl и написать для него сишную обертку под свои нужды, если хочется уйти от плюсов

Плюсы юзать нельзя:-)

В libc есть.

Проблема не в выборе хэш таблицы, дело уже в хэш-функции, и том, что gpl юзать нельзя.

Плюсы юзать нельзя:-)

религия не позволяет?

Начальника

Проблема не в выборе хэш таблицы, дело уже в хэш-функции, и том, что gpl юзать нельзя.

Так вопрос в реализации хэш-таблицы или в выборе хэш-функции?

хэш функции.

murmur

Можно посмотреть тут: http://burtleburtle.net/bob/. Для массива целых подойдет lookup3 (http://burtleburtle.net/bob/c/lookup3.c).

В каком интервале x и y?

Да вообще неясно, целые они или нет. А так, ну до миллиона.

Если ничего нельзя - реализовать свою, со своей хэш-функцией.

А, то есть они ещё и дробные. Тогда тебе kd-tree надо вообще.

Почему ничего нельзя? uthash можно. Вообще, замучу сейчас свой поиск со скоростью O(N), и всё)))

Зачем??? У меня же не точки в качестве ключей, а массив !

А, извиняюсь, недоглядел.

интересен хэш для массива вещественных числе

аналогичен хэшу для массива байт, итого можно брать crc32, md5 etc.

Вообще, замучу сейчас свой поиск со скоростью O(N), и всё)))

Хэш-таблица с линейным поиском - это сильно. :)

2 wota:

Плюcую md5!

А в случае, если будет массив целых, что делать?

Почему md5?

А в случае, если будет массив целых, что делать?

тоже самое

Умеет хэш от любой строки, очень низвкая вероятность коллизий. Формируешь строку из массива, берешь от нее md5-хэш.

А какая вероятность коллизий будет после md5 % tableSize ?

Скастовать массив в char* и скормить хэш функции, работающей с массивом байт (как собственно wota написал).

А какая вероятность коллизий будет после md5 % tableSize ?

Для MD5 скорее всего будет 1 / tableSize. Просто посмотри на своих данных. Некоторые хеш-функции дают равномерное распределение вероятности коллизий только если tableSize простое число. Вообще покури третий том Кнута.

map не является хеш-таблицей

в glib есть

в GLib есть

здесь, если что она LGPL.

ок.спс.

А если библиотека под GPL, то даже динамически линковать с проприетарным кодом ее нельзя?

lgpl можно.

union number {
      double value;
      long long hash;
}

скорость вычисления хеша - 0.0 наносекунд. коллизий нет.

В libc уже есть готовое: hcreate, hsearch, hdestroy.

натрави на него местных анонов

коллизий нет.

только в случае если таблица имеет 2^64 слота.

это и дураку ясно. я всего лишь предложил концепцию для решения задачи.

Map вообще-то не хэш-таблица.

Ну хеш-дерево, один хрен.

rb-tree, хеши - это unordered_map и unordered_set

Это шо за зверь такой «хеш-дерево»? lol

Не армия же.

Ну путает человек ассоциативные массивы и хэш-таблицы.

Это все Перл виноват

Ну путает человек ассоциативные массивы и хэш-таблицы.

Разве это не одно и тоже ?

#Perl любитель.

Так... ща... map использует сравнение ключей прямиком, чтобы запихивать их в дерево, а не прогоняя их сначала через хеш-функцию?