Deleted и empty в закрытом хэшировании

@Dimsssss · Регистрация: 13.06.2013

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

Уважаемые участники форума, хотелось бы получить ответ на следующий вопрос.
Реализую закрытое хэширование, завожу массив указателей на строки. Для каждой строки считается ключ причем следующим образом; сначала находится сумма символов в строке, затем получаем остаток от деления этой суммы на количество этих строк в хэше. Элемент хэша назовем hashTable[i].

Столкнулся с такой проблемой: и для вставки и для удаления элемента требуется проверить, является ли строка пустой или удаленной. Это делается для того чтобы вставка и удаление проводилось с приоритетом сначала на удаленный, а затем на пустой элемент. И, насколько я понимаю, пустая строка == строка из нулевого символа '\0'.
Как же тогда идентифицировать удаленную строку? Какую проверку нужно провести для того, чтобы функция deleted возвращала либо 0, либо 1? Я вроде как понимаю, что если строка удалена, то она пустая, но память под нее остается выделенной, однако получить адрес можно как удаленной так и пустой строки. Помогите пожалуйста, я уже в конец запутался.

lss · 07.05.2015, 05:01

Что есть удалённая строка? Где и каким образом она удаляется?

@Dimsssss · 07.05.2015, 05:10 **[ТС]**

C++
1
2
3
4
5
6
7
8
9
10
void CloseHash::deleteName(char* str)
{
    int key = member(str);
    
    if(key != -1)
    {
        delete hashTable[key]; 
        hashTable[key] = '\0';
    }
}

как-то так

Добавлено через 4 минуты

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int CloseHash::member(char* str)
{
    int sum = sumCharacters(str);
    int key = hash(sum);
    const int start = key;
    
    do {
        if(!hashTable[key])
            return -1;
        else 
            if(!strcmp(hashTable[key], str))
                return key;
                
        key = hash(++sum);
    }while(key != start);
    
    return -1;
}

это member

@gazlan · 07.05.2015, 05:11

Закрытое хеширование

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

@Dimsssss · 07.05.2015, 05:14 **[ТС]**

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

@gazlan · 07.05.2015, 05:42

Тогда остается битовая карта (a la FAT).

Новые блоги и статьи Все статьи Все блоги /
Что нового в C# 14 UnmanagedCoder 10.03.2025 Предстоящая версия C# 14 обещает принести изменения, которые сделают разработку еще более приятной и эффективной. Что стоит отметить, так это влияние сообщества разработчиков на формирование новых. . .	Формулы поворота Igor3D 10.03.2025 Добрый день Тема Эти формулы приводятся во множестве тьюториалов, часто под видом "матрица вращения на плоскости". x' = x * cos(a) - y * sin(a) y' = y * cos(a) + x * sin(a) Как бы Вы их. . .	Что нового в .NET 10 UnmanagedCoder 10.03.2025 . NET 10 выходит как релиз с длительной поддержкой (LTS), включающей три года обновлений. В этом обновлении Microsoft сфокусировались на нескольких направлениях: производительность, оптимизация. . .	Отложенное высвобождение, RCU и Hazard Pointer в C++26 NullReferenced 09.03.2025 Многопоточное программирование стало важной частью современной разработки. Когда несколько потоков одновременно работают с общими данными, возникает целый ряд проблем, связанных с синхронизацией и. . .	Неблокирующийся стек на C++26 NullReferenced 09.03.2025 Традиционные способы синхронизации в многопоточном программировании — мьютексы, семафоры, условные переменные — часто превращаются в узкое место в плане производительности. При этом неблокирующиеся. . .
Обработка строк в C++26: Новые возможности string и string_view NullReferenced 09.03.2025 Новый стандарт C++26 предлагает много улучшений для работы с привычными string и относительно новыми string_view. string_view - это невладеющая ссылка на последовательность символов, появившаяся в. . .	Мой первый аддон для Blender 3D, с помощью нейронки (не зная даже азов пайтона, но это не значит что так и с остальным). Hrethgir 09.03.2025 Потратил весь день. Пол-дня мне хватило, чтобы понять что с версией с 14B мне не одолеть написание функционального кода, на языке с которым я вообще никак не знаком - пайтон. Версия 22B от другого. . .	Einstein@Home сегодня исполняется двадцать лет! Programma_Boinc 09.03.2025 Einstein@Home сегодня исполняется двадцать лет! Отправлено 19 февраля 2025 года в 17:20:21 UTC Я хочу поздравить всех наших волонтеров, разработчиков и ученых из Einstein@Home. Мы официально. . .	Заполнители и расширенный набор символов в C++26 NullReferenced 09.03.2025 C++26 представляет два важных обновления: заполнители и расширенный набор символов. Заполнители (placeholders) решают давнюю проблему лаконичности кода в шаблонных выражениях и лямбда-функциях. Они. . .	Контракты в C++26 NullReferenced 09.03.2025 Контракты – это механизм, позволяющий указывать предусловия, постусловия и инварианты для функций в коде. Эта функциональность должна была стать частью C++20, но была исключена на встрече комитета. . .

@Dimsssss 0 / 0 / 0 Регистрация: 13.06.2013 Сообщений: 20
		1
	Deleted и empty в закрытом хэшировании 07.05.2015, 04:52. Показов 712. Ответов 5 Метки нет (Все метки) Уважаемые участники форума, хотелось бы получить ответ на следующий вопрос. Реализую закрытое хэширование, завожу массив указателей на строки. Для каждой строки считается ключ причем следующим образом; сначала находится сумма символов в строке, затем получаем остаток от деления этой суммы на количество этих строк в хэше. Элемент хэша назовем hashTable[i]. Столкнулся с такой проблемой: и для вставки и для удаления элемента требуется проверить, является ли строка пустой или удаленной. Это делается для того чтобы вставка и удаление проводилось с приоритетом сначала на удаленный, а затем на пустой элемент. И, насколько я понимаю, пустая строка == строка из нулевого символа '\0'. Как же тогда идентифицировать удаленную строку? Какую проверку нужно провести для того, чтобы функция deleted возвращала либо 0, либо 1? Я вроде как понимаю, что если строка удалена, то она пустая, но память под нее остается выделенной, однако получить адрес можно как удаленной так и пустой строки. Помогите пожалуйста, я уже в конец запутался. 0

lss 941 / 869 / 355 Регистрация: 10.10.2012 Сообщений: 2,706
	07.05.2015, 05:01	2
	Что есть удалённая строка? Где и каким образом она удаляется? 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	07.05.2015, 05:11	4
	Закрытое хеширование Но если в хеш-таблице допускается удаление элементов, то при достижении пустого сегмента, не найдя элемента х, нельзя быть уверенным в том, что его вообще нет в таблице, так как сегмент может стать пустым уже после вставки элемента х. Поэтому, чтобы увеличить эффективность данной реализации, необходимо в сегмент, который освободился после операции удаления элемента, поместить специальную константу, которую назовем, например, DEL. В качестве альтернативы специальной константе можно использовать дополнительное поле таблицы, которое показывает состояние элемента. Важно различать константы DEL и NULL – последняя находится в сегментах, которые никогда не содержали элементов. При таком подходе выполнение поиска элемента не требует просмотра всей хеш-таблицы. Кроме того, при вставке элементов сегменты, помеченные константой DEL, можно трактовать как свободные, таким образом, пространство, освобожденное после удаления элементов, можно рано или поздно использовать повторно. 0

@Dimsssss 0 / 0 / 0 Регистрация: 13.06.2013 Сообщений: 20
	07.05.2015, 05:14 [ТС]	5
	Да, поначалу все и было сделано через символьную константу, но мне сказали, что для ключа должны вызываться функции, которые могли бы определить является ли строка удаленной или пустой. Короче сказали делать без симв. констант. Иначе все было бы слишком радужно и весело 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	07.05.2015, 05:42	6
	Тогда остается битовая карта (a la FAT). 0