1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

Структура данных для хеш-таблицы

Тема в разделе "WASM.A&O", создана пользователем KeSqueer, 20 янв 2011.

  1. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Таблица будет содержать несколько десятков тысяч элементов и, фактически, будет статична (т.е. после чтения из файла добавление элементов будет происходить довольно редко). А вот обращение к таблице - часто. Какая структура данных лучше подойдёт в данном случае?
     
  2. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    KeSqueer
    Обычный массив (конструктор хеш-таблицы принимает предполагаемое максимальное число элементов). Проблемой при реализации хеш-таблицы будет скорее удаление элементов. Надо предусмотреть параллельный массив целых значений, хранящий для каждого поля исходного массива число коллизий.
     
  3. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    l_inc
    У массива есть недостатки.
    1) Если массив упорядочен (удобно для бинарного поиска), будет медленным добавление/удаление элемента.
    2) Если массив неупорядочен, для поиска его нужно будет отсортировать (быстрой сортировкой или ещё какой). Удаление элемента остаётся сложной задачей, добавление происходит ещё дольше (т.к. перед добавлением надо удостовериться, что элемента с таким хешем ещё нет, т.е. сделать поиск).
    Если учесть, что удаление элементов мне, в принципе, не нужно, и коллизий точно не будет (64-битный ключ, 100 000 эл-тов, но не по этой причине), то сложность вставки элемента в центр массива в первом случае наводит на мысли об исползьовании двусвязного списка. Но в таком случае возникает две сложности:
    1) нужно будет писать свой менеджер памяти, ибо фрагментация последней будет довольно большой;
    2) непонятно, как осуществить быстрый поиск в данном случае.
    Как вариант можно попробовать такой вариант: разбить все хеши, скажем, по первому байту. Таким образом, получим 256 таблиц, примерно по 400 элементов в каждом (при 100 000 элеметнов в целом). В этом случае в разы сокращается время сортировки, время поиска остаётся примерно таким же. Будет ли это достойным вариантом?
     
  4. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    кнут описывает 2 конструкции
    1) таблица, где хэш является адресом в ней, а значение - ссылка на цепочку (вектор, массив, другой хэш) значений у которых хэш совпадает (коллизий). и добавляется и ищется и удаляется элементарно.
    2) таблица, где адрес является продуктом хэша и спец функции для разрешения коллизий

    во всех кругом используется вариант 1.
    используйте и вы и ничего мудрить не надо
     
  5. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    qqwe
    Это само собой, но вот с элементарностью Вы переборщили. Алгоритм, безусловно, прост, но вот как быть со временем?
     
  6. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    KeSqueer
    с каким временем? алгоритм он 1, описан кругом, используется кругом. разница только в деталях (функция расчета хэша. способ разрешения коллизий, точнее контейнеры для их хранения)
     
  7. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    например, для функции хэширования строки

    int hash = 0;
    for(char *pstr = str; *pstr; pstr++){
    hash += *pstr;
    }
    hash %= 13;

    хэши для строк "aab", "aba", "baa" совпадут. как разрешать будете?
    поэтому и используются доп структуры. обычно простые, тк цепочки коллизий редко длинные. но можете и деревья прицепить
     
  8. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    qqwe
    У меня такое ощущение, что вы не читали сообщений темы. Я писал как про то, что коллизий нет, так и про недостатки списка. Повторюсь:
    1) хеш 64-битный, это 18,5E18 комбинаций. В таблице будет содержаться число элементов порядка 1E6. Теоретическая возможность существования коллизий, я не отрицаю, есть, но в моём случае их точно не будет.
    2) в линейный список сложно добавлять элемент
    а) если массив держится отсортированным, вставка элемента в центр списка является трудоёмкой задачей (нужно сдвигать часть массива после позиции вставки).
    б) если массив неотсортирован, перед вставкой нужно проверить, нет ли уже элемента с таким хешем (т.е. провести сортировку и поиск, поскольку для неотсортированного массива придётся перебирать все элементы), что ещё дольше.
    Однако, если разбить всю таблицу на 256 подтаблиц по первому байту хеша, работа значительно упрощается.
    Идеальным вариантом вижу использовать avl-деревья. Но стоит ли овчинка выделки? Может быть достаточно вышеприведённого варианта?
     
  9. СFF

    СFF PP

    Публикаций:
    0
    Регистрация:
    16 янв 2009
    Сообщения:
    233
    Я когда писал хеш таблицу, скажу одно хеш брал crc32,так как именно он обеспечивал равномерное распределение по ячейкам. В других хешах колизий было очень много.

    Возми сорсы Sphinx Search Engine тм же се ест
     
  10. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    СFF
    Вопрос не в выборе хеш-функции, а в выборе структуры данных для хранения пар ключ-значение. Выбранная хеш-функция обеспечивает хорошее распределение, низкую вероятность коллизий.
     
  11. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    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;
    }
    снова повторю, почитайте теорию. все это уже решено и все куда проще и не так. заодно и разберетесь что такое хэши и с чем их едят.
     
  12. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    qqwe
    Почему Вы не можете принять тот факт, что коллизий нет? Это так, и не потому что
    , а просто так есть и всё.
    нет проверки, что элемент уже не содержится в списке.
    Хеш-функцию я тоже не выбираю, она задана и даёт 64 бита на выходе.
     
  13. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    +1. Похоже, автор не понимает, что есть хеш-карта, и для чего она нужна. Возможно, путает с более общим понятием отображения.
    Но я бы всё-таки использовал (точнее таки использовал) вариант с функцией зондирования для разрешения коллизий. Во-первых, это чуть меньше памяти требует, во-вторых, не надо городить дополнительно никаких связных списков (обойтись только массивом) и, в-третьих, при удачно выбранной функции зондирования коллизия обойдётся дешевле.
     
  14. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Да сколько раз повторять? КОЛЛИЗИЙ НЕТ! Хеш-функция даёт 64 бита, другую брать НЕЛЬЗЯ!
     
  15. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    KeSqueer
    1) Хеш-функция не может давать 64 бита. Она даёт значения в диапазоне от нуля до числа элементов в таблице. Иначе это какая-то Вами выдуманная структура данных, не имеющая отношения к хеш-таблицам. Готовы выделить табличку размером в 2^64 элементов? Если да, то подыщите себе 128-битную машину.
    2) Либо диапазон хешей, возвращаемых хеш-функцией должен искусственно сокращаться до числа элементов в таблице. Но тогда хеш-функцией называется функция, возвращающая уже сокращённый диапазон хешей, что возвращает нас к пункту 1.
    3) Нет в хеш-таблицах никаких сортированных массивов!
     
  16. Pavia

    Pavia Well-Known Member

    Публикаций:
    0
    Регистрация:
    17 июн 2003
    Сообщения:
    2.398
    Адрес:
    Fryazino
    KeSqueer
    Чего тут не понятного. Возьми не 64 бита, а 23бита да так чтобы коллизии были.
    Не нравятся хэши используй деревья к примеру AVL.
     
  17. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Попробую изложиться ещё яснее. Есть взаимно-однозначное соответствие между некоторыми данными и 64-хбитным числом. Это можно описать как std::set<uint64_t, data_t>, причем число вычисляется из данных с помощью некоторой хеш(?)-функции. Какая внутренняя реализация std::set при своей простоте будет давать приемлемые результаты для случая большого количества элементов (порядка 1е6)?
     
  18. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    KeSqueer
    В общем случае это будет называться хеш-функцией. В контексте хеш-таблицы, содержащей элементы, от которых она находит хеши, уже нет (тогда исходный 64-битный хеш называется ключом).
    То, что Вы хотите, — отображение (тогда пост Pavia как раз в тему). Реализуется оно многими способами. Теперь важно разобраться, что для Вас является приемлемым результатом.
    1) Если важна скорость, но приемлемо выделить табличку под 2^21 — 2^23 указателей (удачный выбор для порядка 10^6 элементов полезной нагрузки), то хеш-таблица — самое оно (21-23 бита для хеша хеш-таблицы находятся хешированием исходного 64-битного хеша). Поиск будет моментальным. 64-битный хеш используется для проверки "попадания".
    2)Если желательно с памятью обращаться по-экономнее, но можно слегка поступиться скоростью, то берите самобалансирующееся дерево (в среднем 20 сравнений для поиска элемента понадобится).

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

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Спасибо, l_inc
    Pavia
     
  20. r90

    r90 New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2005
    Сообщения:
    898
    qqwe
    В ком кругом? Я заглядывал в несколько реализаций хеш-таблиц, в glibc, gawk и ruby. Везде использовался вариант 2). Или glibc, gawk и ruby являют собою редкое исключение? Я один раз видел реализованный вариант 1), и это была хеш-таблица написанная мною в глубокой юности, по мотивам где-то услышанного описания принципа работы хеш-таблицы. Впоследствии, после прочтения Кнута, я тоже предпочитаю вариант 2).