Хэширование с использованием линейного зондирования

@Max_Mac · Регистрация: 04.02.2014

Студворк — интернет-сервис помощи студентам

Вот задание:

Реализовать алгоритм хеширования с использованием линейного зондирования для разрешения коллизий.

Может у кого-нить есть какие-нибудь коды,а то я вообще не понимаю что надо сделать

@BRcr · 15.11.2014, 17:51

Сообщение от Max_Mac

я вообще не понимаю что надо сделать

Ну, это поправимо.

Разрешение конфликтов посредством линейного зондирования

--> Источник <--

Разрешение конфликтов посредством линейного зондирования

Если количество элементов, которые, скорее всего, должна содержать хеш-таблица, известно, можно выделить место для хеш-таблицы, содержащей это количество элементов и небольшое число свободных ячеек "на всякий случай". Было разработано несколько алгоритмов, которые позволяют хранить элементы в таблице, используя пустые ячейки таблицы для хранения элементов, которые конфликтуют с уже имеющимися. Этот класс алгоритмов называют схемами с открытой адресацией (open-addressing schemes). Простейшая схема с открытой адресацией - это линейное зондирование (linear probing).

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

Для начала вставим в пустую хеш-таблицу фамилию "Smith" (т.е. вставим элемент, ключом которого является "Smith"). Выполним хеширование ключа Smith с помощью функции хеширования и получим значение индекса, равное 42. Установим значение 42-го элемента хеш-таблицы равным Smith. Теперь записи хеш-таблицы вблизи этого элемента выглядят следующим образом:

Элемент 41: <пусто>

Элемент 42: Smith

Элемент 43: <пусто>

Это было достаточно просто. Теперь вставим фамилию "Jones". Необходимо выполнить те же действия, что и в предыдущем случае: следует вычислить хеш-значение ключа Jones, а затем вставить значение Jones по результирующему индексу. К сожалению, используемая функция хеширования имеет неизвестное происхождение и для фамилии Jones генерирует хеш-значение, которое также равно 42. Если теперь обратиться к хеш-таблице, выясняется, что имеет место конфликт: ячейка 42 уже занята фамилией Smith. Что же делать? Используя линейное зондирование, мы проверяем следующую ячейку, чтобы выяснить, пуста ли она. Если да, то мы устанавливаем значение 43-го элемента хеш-таблицы равным Jones. (Если бы 43-я ячейка оказалась занятой, пришлось бы проверить следующую ячейку и т.д., возвращаясь к началу хеш-таблицы по достижении ее конца. Со временем мы нашли бы пустую ячейку либо вернулись бы к исходному состоянию, выяснив, что таблица заполнена.) Действие по проверке ячейки в хеш-таблице называется зондированием (probing), отсюда и название самого алгоритма - линейное зондирование.

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

Элемент 41: <пусто>

Элемент 42: Smith

Элемент 43: Jones

Элемент 44: <пусто>

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

А как насчет поиска элемента, который отсутствует в таблице? Выполним поиск элемента "Brown". Реализуем хеширование, в результате чего будет получено значение индекса, равное 43. При обращении к 43-му элементу выясняется, что он соответствует элементу Jones. При переходе к следующему, 44-му, элементу выясняется, что он пуст. Теперь можно сделать вывод, что элемент Brown в хеш-таблице отсутствует.

Пример хэширования

--> Источник <--

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

В примере хэширования используется массив структур под названием primary:

C++
1
2
3
4
5
6
7
8
#define MAX 260
 
struct htype {
  int index;   /* логический индекс */
  int val;     /* собственно значение элемента данных */
  struct htype *next; /* указатель на следующий элемент с таким же
                         хэш-адресом */
} primary[MAX];

Перед использованием этого массива необходимо его инициализировать. Следующая функция присваивает полю index значение -1 (значение, которое по определению никогда не будет сгенерировано в качестве индекса); это значение обозначает пустой элемент. Значение NULL в поле next соответствует пустой цепочке хэширования[3].

C++
1
2
3
4
5
6
7
8
9
10
11
/* Инициализация хэш-массива. */
void init(void)
{
  register int i;
 
  for (i=0; i<MAX; i++) {
    primary[i].index = -1;
    primary[i].next = NULL;  /* пустая цепочка */
    primary[i].val = 0;
  }
}

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/* Вычисление хэш-адреса и сохранение значения. */
void store(char *cell_name, int v)
{
  int h, loc;
  struct htype *p;
 
  /* Получение хэш-адреса */
  loc = *cell_name - 'A'; /* столбец */
  loc += (atoi(&cell_name[1])-1) * 26; /* строка * ширина + столбец */
  h = loc/10; /* hash */
 
  /* Сохранить в полученной позиции, если она не занята
     либо если логические индексы совпадают - то есть, при обновлении.
  */
  if(primary[h].index==-1 || primary[h].index==loc) {
    primary[h].index = loc;
    primary[h].val = v;
    return;
  }
 
  /* в противном случае, создать список коллизий
     либо добавить в енго элемент */
  p = (struct htype *) malloc(sizeof(struct htype));
  if(!p) {
    printf("Не хватает памяти\n");
    return;
  }
  p->index = loc;
  p->val = v;
  slstore(p, &primary[h]);
}
 
/* Добавление элементов в список коллизий. */
void slstore(struct htype *i,
             struct htype *start)
{
  struct htype *old, *p;
 
  old = start;
  /* найти конец списка */
  while(start) {
    old = start;
    start = start->next;
  }
  /* связать с новой записью */
  old->next = i;
  i->next = NULL;
}

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Вычисление хэш-адреса и получение значения. */
int find(char *cell_name)
{
  int h, loc;
  struct htype *p;
 
  /* получение значения хэш-адреса */
  loc = *cell_name - 'A'; /* столбец */
  loc += (atoi(&cell_name[1])-1) * 26; /* строка * ширина + столбец */
  h = loc/10;
 
  /* вернуть значение, если ячейка найдена */
  if(primary[h].index == loc) return(primary[h].val);
  else { /* в противном случае просмотреть список коллизий */
    p = primary[h].next;
    while(p) {
      if(p->index == loc) return p->val;
      p = p->next;
    }
    printf("Ячейки нет в массиве\n");
    return -1;
  }
}

Создание функции удаления оставлено читателю в качестве упражнения. (Подсказка: Просто обратите процесс вставки.)

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

Новые блоги и статьи Все статьи Все блоги /
Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	1С: Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git
1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .

@Max_Mac 2 / 2 / 0 Регистрация: 04.02.2014 Сообщений: 68

	Хэширование с использованием линейного зондирования 15.11.2014, 16:51. Показов 5912. Ответов 1 Метки нет (Все метки) Вот задание: Реализовать алгоритм хеширования с использованием линейного зондирования для разрешения коллизий. Может у кого-нить есть какие-нибудь коды,а то я вообще не понимаю что надо сделать 0

Хэширование с использованием линейного зондирования

Решение