Создать хеш-таблицу c

Обновлено: 04.07.2024

Хотите улучшить этот вопрос? Обновите вопрос, чтобы он был сосредоточен только на одной проблеме, отредактировав этот пост.

Закрыт 6 лет назад.

У меня есть несколько вопросов о структуре данных, называемой хеш-таблицей (также известной как ассоциативный массив), и о том, как она реализована в C.

Как создать хэш-таблицу в C? Что такое хеш-таблица и как ее реализовать? Зачем мне использовать хеш-таблицу, а не массив?

ПРИМЕЧАНИЕ. Я знаю, что это очень широкий вопрос, который потребует развернутого ответа, но я сделал это, потому что некоторые люди спрашивали меня, что это такое. поэтому я разместил его здесь, чтобы полностью объяснить и помочь кому-либо еще.

@doublesharp У меня было несколько друзей, которые хотели знать, что это такое, и я хотел опубликовать это здесь, чтобы оно могло помочь кому-то еще в будущем

да, извините за действительно общий вопрос. Это началось как вопрос о том, как реализовать хеш-таблицу для хранения имен в C, но когда я начал писать ответ, я хотел объяснить его более подробно, и он как бы превратился в это

1 Ответ 1

Предпосылки

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

Также, если вы не знаете. Говоря о скорости алгоритмов и структур данных, вы должны знать термины:

O() = (произносится как "Big-oh") Big-oh или O() относится к среде выполнения "наихудшего сценария". Точно так же в математике это большая нотация O, описывающая ограничивающее поведение функции. Если что-то O (1), это постоянное время «действительно хорошо». Если что-то O (n), это означает, что список имеет длину в миллион. В худшем случае это будет работать миллион раз. O() обычно используется для определения того, насколько быстро что-то работает, потому что именно так быстро оно будет работать в худшем случае.

Ω = (греческая буква омега) относится к лучшему сценарию. Он используется не так часто, как O(), поэтому я не буду вдаваться в подробности. Но просто знайте, что если что-то Ω(1), в лучшем случае это займет всего один раз.

Θ = (греческая буква тета) уникальна тем, что используется только тогда, когда среды выполнения O() и Ω() совпадают. Так же, как и в случае рекурсивного алгоритма сортировки слиянием. Время выполнения равно Θ(n(log(n))). Это означает, что это O(n(log(n))) и это Ω(n(log(n))).

Что такое хэш-таблица?

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

Зачем использовать хэш-таблицу, а не массив?

Массив очень удобен в использовании и прост в создании, но у него есть и свои недостатки. В этом примере предположим, что у нас есть программа, в которой мы хотим сохранить всех пользователей в массиве.

Это довольно просто. Скажем так, мы планируем, что в этой программе будет не более 100 пользователей, и заполним этот массив нашими пользователями

Так что все работает хорошо, хорошо и очень быстро. Это O (1) прямо здесь. Мы можем получить доступ к любому пользователю в постоянное время.

Но давайте теперь предположим, что наша программа становится действительно популярной. Сейчас у него более 80 пользователей. О-о! Нам лучше увеличить размер этого массива, иначе мы получим переполнение буфера.

Как же нам это сделать? Что ж, нам придется создать новый массив большего размера и скопировать содержимое старого массива в новый массив.

Это очень дорого, и мы не хотим этого делать. Мы хотим мыслить умно и не использовать что-то фиксированного размера. Ну, мы уже знаем, как использовать указатели в наших интересах, и мы можем объединить информацию в структуру, если захотим.

Таким образом, мы могли бы создать структуру для хранения имени пользователя, а затем указать (через указатель) на новую структуру. Вуаля! Теперь у нас есть расширяемая структура данных. Это список связанной информации, связанной указателями. Таким образом, связанный список имен.

Связанные списки

Давайте создадим связанный список. Сначала нам понадобится структура

Хорошо, у нас есть имя строки и a. Подожди секунду. Я никогда не слышал о типе данных, называемом структурным узлом. Что ж, для нашего удобства я набрал новый «тип данных» с именем node, который также является нашей структурой с именем node.

Итак, теперь, когда у нас есть узел для нашего списка, что нам нужно дальше? Что ж, нам нужно создать «корень» для нашего списка, чтобы мы могли пройти по нему (позже я объясню, что я имею в виду под обходом). Итак, давайте назначим корень. (помните, что тип данных узла я набрал ранее)

Итак, теперь, когда у нас есть корень, все, что нам нужно сделать, это создать функцию для вставки новых имен пользователей в наш список.

Итак, вот.У нас есть базовый связанный список, и теперь мы можем добавлять пользователей сколько угодно, и нам не нужно беспокоиться о нехватке места. Но у этого есть и обратная сторона. Большая проблема заключается в том, что каждый узел или «пользователь» в нашем списке является «анонимным». Мы не знаем, где они находятся, или даже сколько у нас пользователей с этим. (конечно, есть способы сделать это намного лучше — я просто хочу показать очень простой связанный список). Нам нужно пройти весь список, чтобы добавить пользователя, потому что мы не можем получить прямой доступ к концу.

Как будто мы попали в огромную пыльную бурю, и ничего не видно, а нам нужно добраться до нашего амбара. Мы не можем видеть, где наш сарай, но у нас есть решение. Там стоят люди (наши узлы), и все они держат две веревки (наши указатели). У каждого человека есть только одна веревка, но за другой конец этой веревки держится кто-то другой. Как и наша структура, веревка действует как указатель на то, где они находятся. Так как же нам добраться до нашего амбара? (для этого примера сарай является последним «человеком» в списке). Ну, мы понятия не имеем, насколько велика наша очередь людей или куда они идут. На самом деле все, что мы видим, это столб забора с привязанной к нему веревкой. (Наш корень!) Этот столб забора никогда не изменится, поэтому мы можем схватиться за столб и начать двигаться, пока не увидим нашего первого человека. Этот человек держит две веревки (указатель столба и его указатель).

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

Короче говоря, это связанный список. Его преимущества заключаются в том, что он может расширяться настолько, насколько вы хотите, но время его выполнения зависит от того, насколько велик список, а именно O (n). Таким образом, если есть 1 миллион пользователей, ему придется запустить 1 миллион раз, чтобы вставить новое имя! Ух ты, как расточительно вставлять только 1 имя.

К счастью, мы умны и можем предложить лучшее решение. Почему бы нам вместо одного связанного списка не создать несколько связанных списков. Массив связанных списков, если хотите. Почему бы нам не сделать массив размером 26. Таким образом, у нас может быть уникальный связанный список для каждой буквы алфавита. Теперь вместо времени выполнения n. Мы можем разумно сказать, что наше новое время выполнения будет n/26. Теперь это не будет иметь большого значения, если у вас есть список размером в 1 миллион. Но в этом примере мы просто упростим его.

Итак, у нас есть массив связанных списков, но как мы собираемся сортировать наших пользователей в массиве. Хорошо. почему бы нам не сделать функцию, которая решает, какой пользователь должен куда идти. Эта функция будет "хешировать" пользователей, если вы будете в массив или "таблицу". Итак, давайте создадим этот «хешированный» связанный список. Таким образом, имя хеш-таблицы

Хэш-таблица

Как я только что сказал, наша хеш-таблица будет представлять собой массив связанных списков и будет хэшироваться по первой букве их имени пользователя. A переместится на позицию 0, B на 1 и т. д.

Структура этой хеш-таблицы будет такой же, как и структура нашего предыдущего связанного списка

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

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

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

Итак, вот наша хэш-функция. Это довольно просто. Все, что нам нужно сделать, это посмотреть на первую букву в слове и дать значение от 0 до 25 в зависимости от того, какая это буква

Итак, теперь все, что нам нужно, это создать нашу функцию вставки. Это будет выглядеть точно так же, как наша функция вставки раньше, за исключением того, что каждый раз, когда мы ссылаемся на наш корень, мы будем ссылаться на него как на массив.

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

В этом руководстве вы узнаете, что такое хэш-таблица. Кроме того, вы найдете рабочие примеры операций с хеш-таблицами в C, C++, Java и Python.

Структура данных хеш-таблицы хранит элементы в парах ключ-значение, где

Хеширование (хэш-функция)

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

Пусть k — ключ, а h(x) — хеш-функция.

Здесь h(k) даст нам новый индекс для хранения элемента, связанного с k .

Представление хеш-таблицы

Чтобы узнать больше, посетите страницу Хэширование.

Конфликт хэшей

Когда хеш-функция создает один и тот же индекс для нескольких ключей, возникает конфликт (какое значение должно храниться в этом индексе). Это называется коллизией хэшей.

Мы можем разрешить конфликт хэшей, используя один из следующих методов.

• Разрешение конфликтов с помощью цепочки
• Открытая адресация: линейное/квадратичное зондирование и двойное хэширование

1. Разрешение конфликтов с помощью цепочки

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

Если j является слотом для нескольких элементов, он содержит указатель на начало списка элементов. Если элемент отсутствует, j содержит NIL .

Разрешение конфликтов с помощью цепочки

Псевдокод операций

2. Открытая адресация

В отличие от цепочки, открытая адресация не сохраняет несколько элементов в одном и том же слоте. Здесь каждый слот либо заполнен одним ключом, либо оставлен NIL .

я. Линейное зондирование

При линейном зондировании конфликт разрешается путем проверки следующего слота.

h(k, i) = (h′(k) + i) по модулю m

Если столкновение происходит в точке h(k, 0), то проверяется h(k, 1). Таким образом, значение i увеличивается линейно.

Проблема с линейным зондированием заключается в том, что кластер соседних слотов заполнен. При вставке нового элемента необходимо пройти весь кластер. Это увеличивает время, необходимое для выполнения операций с хеш-таблицей.

ii. Квадратичное зондирование

Он работает аналогично линейному зондированию, но расстояние между слотами увеличивается (больше одного) с помощью следующего соотношения.

h(k, i) = (h′(k) + c ₁ i + c ₂ i 2 ) mod m

• c ₁ и c ₂ — положительные вспомогательные константы,
• я =

iii. Двойное хеширование

Если после применения хеш-функции h(k) возникает коллизия, то для поиска следующего слота вычисляется другая хэш-функция.

Хорошие хеш-функции

Хорошая хэш-функция не может полностью предотвратить коллизии, однако может уменьшить их количество.

Здесь мы рассмотрим различные методы поиска хорошей хеш-функции

1. Метод деления

Если k — ключ, а m — размер хеш-таблицы, хеш-функция h() вычисляется следующим образом:

Например, если размер хеш-таблицы равен 10 и k = 112, то h(k) = 112 mod 10 = 2 . Значение m не должно быть степенью числа 2. Это потому, что степени числа 2 в двоичном формате равны 10, 100, 1000, … . Когда мы найдем k mod m , мы всегда будем получать p-биты младшего порядка.

2. Метод умножения

• kA mod 1 дает дробную часть kA ,
• ⌊ ⌋ дает минимальное значение
• A — любая константа. Значение A лежит между 0 и 1. Но оптимальным выбором будет ≈ (√5-1)/2, предложенный Кнутом.

3. Универсальное хеширование

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

Хеш-таблица в C/C++ (Ассоциативный массив) — это структура данных, которая сопоставляет ключи со значениями. При этом используется хеш-функция для вычисления индексов для ключа.

На основе индекса хеш-таблицы мы можем сохранить значение в соответствующем месте.

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

Хэш-таблица — статья в Википедии

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

Итак, в среднем временная сложность представляет собой постоянное время доступа O(1). Это называется амортизированной временной сложностью.

С++ STL (стандартная библиотека шаблонов) имеет структуру данных std::unordered_map(), которая реализует все эти функции хеш-таблиц.

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

Позвольте нам узнать больше о деталях реализации.

Любая реализация хеш-таблицы состоит из следующих трех компонентов:

• Хорошая хеш-функция для сопоставления ключей со значениями.
• Структура данных хеш-таблицы, поддерживающая операции вставки, поиска и удаления.
• Структура данных для учета конфликтов ключей

Выберите хеш-функцию

Первый шаг – выбор достаточно хорошей хеш-функции с низкой вероятностью коллизий. Но, так как это для иллюстрации, я буду делать наоборот!Обратная психология, а?

В этой статье мы будем работать только со строками (или массивами символов в C).

Я буду использовать очень простую хэш-функцию, которая просто суммирует значения ASCII строки. Я использую это, чтобы показать вам, как мы будем обрабатывать случаи коллизий.

Вы можете протестировать это для разных строк и проверить, конфликтуют ли они или нет. Например, строки «Hel» и «Cau» будут конфликтовать, поскольку они имеют одно и то же значение ASCII.

ПРИМЕЧАНИЕ. Мы должны вернуть число в пределах емкости хеш-таблицы. В противном случае мы можем получить доступ к несвязанной области памяти, что приведет к ошибке.

Определить структуры данных хеш-таблицы

Хеш-таблица — это массив элементов, которые сами по себе являются парой ключ: значение>.

Давайте сначала определим структуру нашего элемента.

Теперь хеш-таблица имеет массив указателей, которые сами указывают на Ht_item , так что это двойной указатель.

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

Создайте хэш-таблицу и ее элементы

Нам нужны функции для создания новой хеш-таблицы в памяти, а также создания ее элементов.

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

Теперь давайте напишем код для создания таблицы. Это выделяет память для структуры-оболочки HashTable и устанавливает для всех ее элементов значение NULL (поскольку они не используются).

Теперь мы почти закончили с этой частью. Как программист C/C++, вы обязаны освобождать память, выделенную в куче с помощью malloc() , calloc() .

Давайте напишем функции, которые освобождают не только элемент таблицы, но и всю таблицу.

Теперь мы завершили работу над созданием функциональной хеш-таблицы. Давайте теперь начнем писать наши методы insert(), search() и delete().

Вставить в хеш-таблицу

Мы создадим функцию ht_insert(), которая выполнит эту задачу за нас.

В качестве параметров принимает указатель HashTable, ключ и значение.

Теперь есть определенные шаги, связанные с функцией вставки.

• Создать элемент на основе пары ключ : значение>
• Вычислить индекс на основе хеш-функции
• Проверьте, занят ли уже индекс, сравнив ключ.
  • Если он не занят. мы можем напрямую вставить его в индекс
  • В противном случае это коллизия, и нам нужно ее обработать.

  Я объясню, как мы будем обрабатывать коллизии, после того, как создадим исходную модель, так что давайте немного подождем.

  Первый шаг прост. Мы напрямую вызываем create_item(key, value) .

  Второй и третий шаги используют hash_function(key) для получения индекса. Если мы вставляем ключ в первый раз, элемент должен быть NULL. В противном случае точная пара ключ: значение уже существует или это коллизия.

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

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

  Хорошо, теперь наша функция вставки (без коллизий) выглядит примерно так:

  Поиск элементов в хеш-таблице

  Если мы хотим проверить правильность вставки, нам также нужно определить функцию поиска, которая проверяет, существует ли ключ, и возвращает соответствующее значение, если это так.

  Логика очень проста. Он просто переходит к элементам, отличным от NULL, и сравнивает ключ. В противном случае мы вернем NULL

  Тестирование нашей базовой модели

  Давайте проверим правильность того, что мы написали, написав программу драйвера main().

  Для иллюстрации мы добавим еще одну функцию print_table(), которая печатает хеш-таблицу.

  Вывод

  Отлично! Кажется, это работает так, как ожидалось, так что теперь давайте перейдем к обработке коллизий.

  Обработка конфликтов

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

  Мы создадим эти цепочки с помощью связанных списков.

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

  Из-за того, что связанные списки имеют временную сложность O(n) для вставки, поиска и удаления, в случае коллизии у нас также будет время доступа в наихудшем случае O(n). Преимущество этого метода в том, что это хороший выбор, если ваша хеш-таблица имеет небольшую емкость.

  Разделение цепочки с помощью связанных списков — Википедия

  После этого давайте приступим к реализации нашего старого доброго связанного списка!

  Теперь нам нужно добавить эти списки «Overflow Bucket» в нашу хеш-таблицу. Мы хотим, чтобы у каждого элемента была одна такая цепочка, поэтому для всей таблицы это массив указателей LinkedList.

  Теперь, когда мы определили наши overflow_buckets, мы добавим функции для их создания и удаления. Нам также необходимо учитывать их в наших старых функциях create_table() и free_table().

  Фу! У нас еще есть работа. Теперь перейдем к функции handle_collision().

  Здесь есть два сценария. Если список переполнения для элемента не существует, нам нужно создать один такой список и добавить в него элемент.

  В противном случае мы можем просто вставить элемент в список

  Итак, мы закончили со вставкой, но теперь нам нужно также обновить нашу функцию поиска, так как нам, возможно, потребуется также просмотреть сегменты переполнения.

  Наконец-то мы учли коллизии в функциях insert() и search()!

  Чтобы напомнить вам о текущем статусе кода, я опубликую полную программу до сих пор.

  Удалить из хеш-таблицы

  Давайте наконец рассмотрим функцию удаления:

  Опять же, метод аналогичен вставке.

  1. Вычислить хэш-индекс и получить элемент
  2. Если это NULL, нам не нужно ничего делать
  3. В противном случае, если после сравнения ключей для этого индекса не будет цепочки коллизий, просто удалите элемент из таблицы
  4. Если существует цепочка коллизий, мы должны удалить этот элемент и соответствующим образом изменить ссылки

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

  Я предоставлю вам рабочую версию для сравнения.

  Собираем все вместе

  Теперь, наконец, я покажу всю программу для хеш-таблицы.

  Вывод

  Заключение

  Надеюсь, вы поняли, как можно реализовать хеш-таблицу с нуля на C/C++, и, возможно, реализовали ее самостоятельно!

  Я бы также посоветовал вам попробовать другие алгоритмы обработки коллизий и другие хэш-функции в этой хэш-таблице и проверить их производительность.

  Скачать код

  Вы можете получить код через Github Gist, который я загрузил. Не стесняйтесь задавать любые вопросы или вносить предложения в разделе комментариев ниже!

  Спецификаторы формата в C

  Приоритетная очередь в C++

  Комментарии

  Создайте таблицу как избыточный цикл. Вы выделили память с помощью malloc, что сделало все внутренние ячейки NULL.

  Спасибо за подборку этой статьи. Концептуально я могу следить и ценить вашу работу. Я думаю, что это какая-то проблема с функциями ht_insert и linkedlist_insert. На момент написания я не могу точно определить проблему.

  Возможно, вы исправили это. Если это так, я предлагаю пересмотреть статью.

  Несмотря на это, спасибо, что поделились.

  С уважением
  Махендра Гунавардена

  Ht_item* it = NULL;
  memcpy(temp->item, it, sizeof(Ht_item));

  Разве ваш компилятор не предупреждает об этом? вы копируете NULL в temp- > item.
  не должно ли быть так:
  memcpy( it, temp->item, sizeof(Ht_item));
  Поскольку в текущей реализации вы освобождаете NULL, это должно вызвать ошибку и привести к утечке памяти.

  Не могли бы вы опубликовать, как изменить тот же код для приложения телефонной книги, которое компилируется в dev C++

  Поскольку связанный список не упорядочен, вы можете упростить функцию linkedlist_insert, вставив в начало, а не в конец. Это упрощает функцию и делает время вставки O(1).

  В функции ht_insert() мы не должны вызывать strcpy напрямую для значения, сначала нам нужно освободить существующее значение и выделить новую память для нового значения или мы должны вызвать realloc. поэтому приведенный ниже код приведет к переполнению.
  // Сценарий 1: Нам нужно только обновить значение
  if (strcmp(current_item->key, key) == 0) strcpy(table->items[index]->value, value);
  возврат;
  >

  Привет, я хотел бы добавить еще одну вещь, которую я нашел.

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

  Это лучший учебник по реализации хэш-таблицы! Большое спасибо !
  Немножко удвоить функцию удаления таблицы.
  if (strcmp(curr->item->key, key) == 0) if (prev == NULL) // Первый элемент цепочки. Удалить цепочку
  free_linkedlist(head);
  table->overflow_buckets[index] = NULL;
  возврат;
  >
  Возможно, если соответствующий элемент находится в первом элементе цепочки,
  table->overflow_buckets[index] = NULL;
  Мы не должны устанавливать его равным нулю, так как в цепочке есть и другие узлы.
  нам просто нужно убрать узел внимания из цепочки, а затем вернуть цепочку в таблицу?

  else if (head != NULL) // Цепочка столкновений существует
  if (strcmp(item->key, key) == 0) // Удалить этот элемент и установить заголовок списка
  // как новый элемент

  бесплатный_элемент(предмет);
  LinkedList* node = head;
  head = head->следующий;
  узел->следующий = NULL;
  таблица->элементы[индекс] = create_item(узел->элемент->ключ, узел->элемент->значение);
  free_linkedlist(узел);
  table->overflow_buckets[index] = head;
  возврат;
  >

  LinkedList* curr = head;
  LinkedList* предыдущая = NULL;

  while (curr) if (strcmp(curr->item->key, key) == 0) if (prev == NULL) // Первый элемент цепочки. Удалить цепочку
  free_linkedlist(head);
  table->overflow_buckets[index] = NULL;
  возврат;
  >
  else // Это где-то в цепочке
  prev->next = curr->next;
  тек->следующий = NULL;
  free_linkedlist(curr);
  table->overflow_buckets[index] = head;
  возврат;
  >
  >
  curr = curr->следующий;
  пред = текущий;
  >

  Привет, я совершенно не уверен, что понимаю логическую часть удаления элемента из таблицы здесь.
  Если я правильно понимаю,
  есть 2 возможности, если существует цепочка коллизий. Элемент находится в индексе таблицы, или он есть в цепочке,
  если он есть в таблице, мы удалим его в таблице, затем переместим первый узел цепочки в таблицу, а остальные исходная цепочка станет новой цепочкой, присоединенной к ней.

  Что меня смущает, так это второй случай; если он находится в цепочке, я видел, как ваш код проверял, находится ли он на головном узле или где-то еще в цепочке. Почему вы удаляете всю цепочку, если в цепочке совпадает один элемент.
  Разве мы не должны просто удалить соответствующий узел и вернуть к нему остальную часть цепочки? Мы удаляем совпавшую строку, а не совпадающий индекс хэш-функции.

  если я хочу, чтобы пользователь ввел ключ и значение, как это сделать? не могли бы вы мне помочь?

  
  

  C имеет структуру данных, называемую хеш-таблицей, которая сопоставляет ключи со значениями. Эта структура данных также присутствует в C++. Хэш-функции используются этой структурой данных для вычисления индексов ключа. Значения могут храниться в определенных местах с помощью индекса хеш-таблицы. Если в случае, если есть два разных ключа с одинаковым индексом и другими структурами данных, основные сегменты используются для учета коллизий. Эта статья посвящена хеш-таблице в C. Она будет состоять из способов создания хеш-таблицы с примерами для демонстрации, а также правил и норм, которых следует придерживаться при ее создании.

  Как создать хэш-таблицу в C?

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

  Веб-разработка, языки программирования, тестирование программного обеспечения и другое

  Работа с хеш-таблицей в C

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

  Примеры создания хэш-таблицы в C

  Ниже приведен упомянутый пример:

  Код:

  Вывод:

  
  

  
  

  Правила для хэш-таблицы в C

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

  Для анализа алгоритма хеширования и оценки его производительности. Можно принять следующее предположение.
  Предположение J (предположение о равномерном хешировании).

  Нам придется предположить, что используемая хэш-функция равномерно распределяет ключи среди целых значений в диапазоне от 0 до M-1.

  Хеширование с отдельной цепочкой.

  Ключи преобразуются в индексы массивов с помощью хэш-функции. Вторым важным компонентом алгоритма хеширования является его способность разрешать коллизии. Основным способом разрешения коллизий является создание связанного списка пар ключ-значение для индексов массива M, в котором ключи хэшируются в свой индекс. Главное — выбрать M, достаточно большой, чтобы список был достаточно коротким для эффективного поиска.

  Заключение

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

  Рекомендуемые статьи

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

  Читайте также:

    
  • Какая компьютерная модель является формальной, полученной в результате формализации
    
  • Слово абсолютно точно можно хранить в файле с размером байтов, кавычки при расчетах не учитываются
    
  • Как уменьшить количество пикселей на фотографиях на телефоне
    
  • Как играть в Starcraft 2 по локальной сети
    
  • Где в карантине касперского