На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Хеш-таблица, открытая адресация
    Всем хай! Сходу к делу!
    Дана хеш-таблица, состоящая из 10 элементов. Она должна хранить натуральные неповторяющиеся числа.
    Стартовая инициализация такая (пусть С++ - индекс от нуля):
    0 0 0 0 0 0 0 0 0 0 - хранимое число
    ---------------------
    0 1 2 3 4 5 6 7 8 9 - индекс элемента

    Абсолютно не важно, какой является хеш-функция, но известно, что она не является совершенной, т е возможны коллизии! Ключом выступает само значение числа.
    Допустим, на вход подаются числа: 12, 16, 8, 27, 13

    Я пытаюсь использовать линейное пробирование, у которого интервал шага = 1.
    Для числа 12 хеш-функция вернула хеш-значение равное 4 (т е 4 - индекс в хеш-таблице, куда попадет число 12).
    Для 16 индекс 9. Для 8 индекс 2. Для 27 индекс 5.
    Вот что представляет из себя хеш-таблица после добавления 4-рех чисел:
    0 0 8 0 12 27 0 0 0 16 - хранимое число
    ---------------------
    0 1 2 3 4 5 6 7 8 9 - индекс элемента

    Для 13 индекс получился = 4! Коллизия! Карман этот занят. Поэтому я тупо начинаю искать свободное место, добавляя +1 к индексу. Перехожу на индекс 5. Он тоже занят. Иду дальше и попадаю в позицию 6 - свободно! Значит, туда поставлю число 13 и получу:
    0 0 8 0 12 27 13 0 0 16 - хранимое число
    ---------------------
    0 1 2 3 4 5 6 7 8 9 - индекс элемента

    Как работает вставка вроде все понятно. Также есть булевый флаг, показывающий свободна/занята ячейка, если свободно - вставляю, если просмотрел каждый карман и все заняты - вставка невозможна, т к ХТ заполнена (либо расширять таблицу).

    Мне до конца непонятно, как будет работать удаление из этой ХТ!
    Допустим, хочу удалить число 12. Хеш-функция вернула индекс 4. Обращаюсь к этой ячейке, она занята и там стоит именно 4. Ставлю флаг - свободно (типа удалил число).
    0 0 8 0 12 27 13 0 0 16 - хранимое число
    ---------------------
    0 1 2 3 4 5 6 7 8 9 - индекс элемента

    И потом хочу удалить число 13. Хеш функция вернула индекс = 4. Смотрю этот карман, а там СВОБОДНО (предыдущей операцией оттуда было удалено число 12).
    Что делать в этом случае? Шагать дальше в поиске числа 13? А, если этого числа изначально не было бы в хеш-таблице, тогда придется впустую просмотреть всю таблицу?
      Удалённые помечаются флагом удалённых, а не флагом пустых.


      При поиске элемента если мы наткнулись на флаг "удалённый" то продолжаем поиск. Если наткнулись на флаг "пустой", то останавливаем поиск и сообщаем о отсутствие искомого элемента.
      При поиске свободного места ищем тот флаг который попадётся первым "удалённый" или "пустой".

      Как и 7 лет назад рекомендую:
      http://www.cs.cmu.edu/afs/cs.cmu.edu/user/...ear-hashing.PDF
      Сообщение отредактировано: Pavia -
        Так, если я правильно понял, то каждый элемент имеет ТРИ состояния, да:
        - пустой
        - занятый
        - удаленный
        ----------------------------
        Во всех статейках, которые посматривал, говорилось про булевый флаг (а это лишь 2 значения), а не тернарную переменную. Лишь это меня смущает, что не до конца уловил что-то!

        Добавлено
        А, я понял кажется, нужно иметь две флаговые переменные:
        struct TElem
        {
        int value;
        bool isDeleted;
        bool isEmpty
        };
        ----------------
        И, если isDeleted == false и isEmpty == false -----> занятый

        спс за помощь!
        Сообщение отредактировано: FasterHarder -
          Цитата FasterHarder @
          Во всех статейках, которые посматривал, говорилось про булевый флаг
          Скорее всего там говорилось о хэш-таблицах без удаления. Или писавший сам никогда с таблицами дела не имел.

          Вместо двух булевых переменных всё-же лучше иметь одну, на три состояния. Будет занимать меньше места, меньше проверок, меньше присваиваний.
            FasterHarder
            0 - не относится к натуральным числам.
            Поэтому он заменяет флаг isEmpty. Отсюда и минус 1 флаг.
            Но я бы оставил 2 флага для наглядности. Да и натуральный ряд удобно расширить до 0 и иметь в value весь набор чисел желательно.
            Сообщение отредактировано: Pavia -
              В общем полностью разобрался с открытой адресацией и закодировал уже на С++ с применением статического одномерного массива на натуральных числах - все достаточно легко оказалось!
                Цитата Pavia @
                натуральный ряд удобно расширить до 0
                Это называется неотрицательные целые.

                Для наглядности можно было ввести несколько inline-функций, проверяющих значение небинарного флага.
                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                0 пользователей:


                Рейтинг@Mail.ru
                [ Script execution time: 0,0237 ]   [ 16 queries used ]   [ Generated: 28.03.24, 18:02 GMT ]