Библиотека knigago >> Компьютеры: Разработка ПО >> Алгоритмы и структуры данных >> Хеш-таблицы


СЛУЧАЙНЫЙ КОММЕНТАРИЙ

# 1262, книга: Портрет призрака
автор: Сара Тодд Тейлор

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

СЛУЧАЙНАЯ КНИГА

Приглашение на порку. Паул Путниньш
- Приглашение на порку

Жанр: Драма

Иван Кисляков (Программист) - Хеш-таблицы

Хеш-таблицы
Книга - Хеш-таблицы. Иван Кисляков (Программист) - прочитать полностью в библиотеке КнигаГо
Название:
Хеш-таблицы
 Иван Кисляков (Программист)

Жанр:

 Статьи и рефераты, Самиздат, сетевая литература, Литература ХXI века (эпоха Глобализации экономики), Алгоритмы и структуры данных, C, C++, C#

Изадано в серии:

неизвестно

Издательство:

Интернет-издательство «Stribog»

Год издания:

ISBN:

неизвестно

Отзывы:

Комментировать

Рейтинг:

Поделись книгой с друзьями!

Помощь сайту: донат на оплату сервера

Краткое содержание книги "Хеш-таблицы"

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

Читаем онлайн "Хеш-таблицы". [Страница - 4]

стр.
Node * [buffer_size];

        for (int i = 0; i < buffer_size; ++i)

            arr2[i] = nullptr;

        std::swap(arr, arr2);

        for (int i = 0; i < past_buffer_size; ++i)

        {

            if (arr2[i] && arr2[i]->state)

                Add(arr2[i]->value);

        }

        for (int i = 0; i < past_buffer_size; ++i)

            if (arr2[i])

                delete arr2[i];

        delete[] arr2;

    }


    void Rehash()

    {

        size_all_non_nullptr = 0;

        size = 0;

        Node** arr2 = new Node * [buffer_size];

        for (int i = 0; i < buffer_size; ++i)

            arr2[i] = nullptr;

        std::swap(arr, arr2);

        for (int i = 0; i < buffer_size; ++i)

        {

            if (arr2[i] && arr2[i]->state)

                Add(arr2[i]->value);

        }

        for (int i = 0; i < buffer_size; ++i)

            if (arr2[i])

                delete arr2[i];

        delete[] arr2;

    }


public:

    HashTable()

    {

        buffer_size = default_size;

        size = 0;

        size_all_non_nullptr = 0;

        arr = new Node*[buffer_size];

        for (int i = 0; i < buffer_size; ++i)

            arr[i] = nullptr;

    }

    ~HashTable()

    {

        for (int i = 0; i < buffer_size; ++i)

            if (arr[i])

                delete arr[i];

        delete[] arr;

    }


    bool Add(const T& value, const THash1& hash1 = THash1(),const THash2& hash2 = THash2())

    {

        if (size + 1 > int(rehash_size * buffer_size))

            Resize();

        else if (size_all_non_nullptr > 2 * size)

            Rehash();

        int h1 = hash1(value, buffer_size);

        int h2 = hash2(value, buffer_size);

        int i = 0;

        int first_deleted = -1;

        while (arr[h1] != nullptr && i < buffer_size)

        {

            if (arr[h1]->value == value && arr[h1]->state)

                return false;

            if (!arr[h1]->state && first_deleted == -1)

                first_deleted = h1;

            h1 = (h1 + h2) % buffer_size;

            ++i;

        }

        if (first_deleted == -1)

        {

            arr[h1] = new Node(value);

            ++size_all_non_nullptr;

        }

        else

        {

            arr[first_deleted]->value = value;

            arr[first_deleted]->state = true;

        }

        ++size;

        return true;

    }


    bool Remove(const T& value, const THash1& hash1 = THash1(), const THash2& hash2 = THash2())

    {

        int h1 = hash1(value, buffer_size);

        int h2 = hash2(value, buffer_size);

        int i = 0;

        while (arr[h1] != nullptr && i < buffer_size)

        {

            if (arr[h1]->value == value && arr[h1]->state)

            {

                arr[h1]->state = false;

                --size;

                return true;

            }

            h1 = (h1 + h2) % buffer_size;

            ++i;

        }

        return false;

    }


    bool Find(const T& value, const THash1& hash1 = THash1(), const THash2& hash2 = THash2())

    {

        int h1 = hash1(value, buffer_size);

        int h2 = hash2(value, buffer_size);

        int i = 0;

        while (arr[h1] != nullptr && i < buffer_size)

        {

            if (arr[h1]->value == value && arr[h1]->state)

                return true;

            h1 = (h1 + h2) % buffer_size;

            ++i;

        }

        return false;

    }

};


--">
стр.

Оставить комментарий:


Ваш e-mail является приватным и не будет опубликован в комментарии.