Что такое хэш таблица
Перейти к содержимому

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

  • автор:

Все, что вы хотели знать о хэш-таблицах

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

Оригинал этой статьи впервые был опубликован в блоге автора @KevinMarquette. Группа разработчиков PowerShell благодарит Кевина за то, что он поделился с нами этими материалами. Ознакомьтесь с его блогом на веб-сайте PowerShellExplained.com.

Хэш-таблица как коллекция объектов

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

Что такое массив?

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

$array = @(1,2,3,5,7,11) 

После передачи элементов в массив можно использовать foreach для выполнения итерации по списку или индекс для доступа к отдельным элементам в массиве.

foreach($item in $array) < Write-Output $item >Write-Output $array[3] 

Точно так же можно обновлять значения с помощью индекса.

$array[2] = 13 

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

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

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

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

$ageList = @<> 

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

$key = 'Kevin' $value = 36 $ageList.add( $key, $value ) $ageList.add( 'Alex', 9 ) 

Имя пользователя — ключ, а его возраст — это значение, которое я хочу сохранить.

Использование квадратных скобок для доступа

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

$ageList['Kevin'] $ageList['Alex'] 

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

$ageList = @<> $key = 'Kevin' $value = 36 $ageList[$key] = $value $ageList['Alex'] = 9 

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

Создание хэш-таблиц со значениями

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

$ageList = @

В качестве таблицы подстановки

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

$environments = @ < Prod = 'SrvProd05' QA = 'SrvQA02' Dev = 'SrvDev12' >$server = $environments[$env] 

В этом примере мы указываем среду для переменной $env и выбираем правильный сервер. Можно использовать switch($env) <. >для такого выбора, однако хэш-таблица является не менее удобным способом.

Она становится еще удобнее, если выполняется динамическое построение таблицы подстановки для последующего использования. То есть такой подход рекомендуется выбирать, если требуется создать перекрестную ссылку. Я думаю, это было бы даже более очевидным, если бы PowerShell не обеспечивал настолько эффективную фильтрацию в канале за счет Where-Object . Этот подход стоит рассматривать, если для вас имеет значение производительность.

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

Множественный выбор

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

$environments[@('QA','DEV')] $environments[('QA','DEV')] $environments['QA','DEV'] 

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

Итерация хэш-таблиц

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

Первое, что следует заметить, — при передаче хэш-таблицы по каналу он обрабатывает ее как один объект,

PS> $ageList | Measure-Object count : 1 

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

PS> $ageList.count 2 

Эту ошибку можно устранить с помощью свойства .values , если вам нужны только значения.

PS> $ageList.values | Measure-Object -Average Count : 2 Average : 22.5 

Зачастую удобнее перечислить ключи и использовать их для доступа к значениям.

PS> $ageList.keys | ForEach-Object < $message = 'is years old!' -f $_, $ageList[$_] Write-Output $message > Kevin is 36 years old Alex is 9 years old 

Далее приведен тот же пример, в котором используется цикл foreach() <. >.

foreach($key in $ageList.keys) < $message = 'is years old' -f $key, $ageList[$key] Write-Output $message > 

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

GetEnumerator()

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

$ageList.GetEnumerator() | ForEach-Object < $message = 'is years old!' -f $_.key, $_.value Write-Output $message > 

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

BadEnumeration

Важный момент: вы можете изменить хэш-таблицу в ходе ее перечисления. Если начать с нашего основного примера $environments :

$environments = @

Попытка задать для каждого ключа одно и то же значение сервера завершится ошибкой.

$environments.Keys | ForEach-Object < $environments[$_] = 'SrvDev03' >An error occurred while enumerating through a collection: Collection was modified; enumeration operation may not execute. + CategoryInfo : InvalidOperation: tableEnumerator:HashtableEnumerator) [], RuntimeException + FullyQualifiedErrorId : BadEnumeration 

Это также приведет к сбою, даже если на первый взгляд все выглядит корректно:

foreach($key in $environments.keys) < $environments[$key] = 'SrvDev03' >Collection was modified; enumeration operation may not execute. + CategoryInfo : OperationStopped: (:) [], InvalidOperationException + FullyQualifiedErrorId : System.InvalidOperationException 

в этой ситуации хитрость заключается в клонировании ключей до выполнения перечисления.

$environments.Keys.Clone() | ForEach-Object

Хэш-таблица как коллекция свойств

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

Доступ на основе свойств

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

$ageList = @<> $ageList.Kevin = 35 $ageList.Alex = 9 

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

$person = @

Кроме того, мы можем добавлять атрибуты в $person и обращаться к ним следующим образом.

$person.city = 'Austin' $person.state = 'TX' 

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

Проверка ключей и значений

В большинстве случаев можно протестировать значение примерно таким способом:

if( $person.age )

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

if( $person.age -ne $null )

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

if( $person.ContainsKey('age') )

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

Удаление и очистка ключей

Ключи можно удалить с помощью функции .Remove() .

$person.remove('age') 

Если присвоить им значение $null , просто получится ключ со значением $null .

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

$person = @<> 

Хотя это вполне рабочий способ, все же рекомендуется вместо него попробовать функцию clear() .

$person.clear() 

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

Все занятные вещи

Упорядоченные хэш-таблицы

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

$person = [ordered]@

Теперь при перечислении ключи и значения сохраняют этот порядок.

Строковые хэш-таблицы

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

$person = @

Это удобно, если вы создаете их в канале.

Настраиваемые выражения в общих командах конвейера

Существует несколько командлетов, которые поддерживают использование хэш-таблиц для создания настраиваемых или вычисляемых свойств. Как правило, они используются в Select-Object и Format-Table . Хэш-таблицы используют специальный синтаксис, который в развернутом виде выглядит следующим образом.

$property = @ < name = 'totalSpaceGB' expression = < ($_.used + $_.free) / 1GB >> 

Командлет помечает этот столбец как name . expression — это блок выполняемого сценария, где $_ представляет значение объекта в канале. Далее рассматривается действие сценария.

$drives = Get-PSDrive | Where Used $drives | Select-Object -Property name, $property Name totalSpaceGB ---- ------------ C 238.472652435303 

Я поместил его в переменную, однако его можно определить как строковый и сократить name до n и expression до e в процессе работы над ним.

$drives | Select-Object -property name, @> 

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

Настраиваемое выражение сортировки

Можно легко отсортировать коллекцию, если объекты содержат данные, которые вы хотите использовать как критерий сортировки. Можно либо добавить данные в объект перед сортировкой, либо создать настраиваемое выражение для Sort-Object .

Get-ADUser | Sort-Object -Property @ < e=< Get-TotalSales $_.Name >> 

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

Сортировка списка хэш-таблиц

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

$data = @( @ @ @ @ @ @ ) $data | Sort-Object -Property @> 

Сплаттинг хэш-таблиц в командлетах

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

Add-DhcpServerV4Scope -Name 'TestNetwork' -StartRange '10.0.0.2' -EndRange '10.0.0.254' -SubnetMask '255.255.255.0' -Description 'Network for testlab A' -LeaseDuration (New-TimeSpan -Days 8) -Type "Both" 

Если сплаттинг не используется, все это необходимо определять в одной строке. При этом либо приходится прокручивать экран, либо строка разворачивается в произвольном месте. А теперь сравним это с командой, которая использует сплаттинг.

$DHCPScope = @ < Name = 'TestNetwork' StartRange = '10.0.0.2' EndRange = '10.0.0.254' SubnetMask = '255.255.255.0' Description = 'Network for testlab A' LeaseDuration = (New-TimeSpan -Days 8) Type = "Both" >Add-DhcpServerV4Scope @DHCPScope 

При использовании символа @ вместо $ вызывается операция сплаттинга.

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

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

Сплаттинг для дополнительных параметров

Чаще всего я использую сплаттинг для работы с дополнительными параметрами, которые добавляю в свой сценарий из других источников. Предположим, у меня есть функция, которая переносит вызов Get-CIMInstance , содержащий дополнительный аргумент $Credential .

$CIMParams = @ < ClassName = 'Win32_Bios' ComputerName = $ComputerName >if($Credential) < $CIMParams.Credential = $Credential >Get-CIMInstance @CIMParams 

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

Правда, можно просто написать команды так, чтобы разрешить значения $null для параметров. На самом деле вы просто не всегда контролируете остальные вызываемые команды.

Несколько операций сплаттинга

Можно выполнить сплаттинг нескольких хэш-таблиц в один командлет. Если вернуться к первоначальному примеру сплаттинга:

$Common = @ < SubnetMask = '255.255.255.0' LeaseDuration = (New-TimeSpan -Days 8) Type = "Both" >$DHCPScope = @ < Name = 'TestNetwork' StartRange = '10.0.0.2' EndRange = '10.0.0.254' Description = 'Network for testlab A' >Add-DhcpServerv4Scope @DHCPScope @Common 

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

Сплаттинг для чистого кода

В сплаттинге одного параметра нет ничего плохого, если это помогает очистить код.

$log = @ Add-Content "logging this command" @log 

Сплаттинг исполняемых файлов

Сплаттинг также эффективен для некоторых исполняемых файлов, использующих синтаксис /param:value . Robocopy.exe , например, содержит отдельные такие параметры.

$robo = @ robocopy source destination @robo 

Не знаю, действительно ли все это имеет практическую пользу, но, по-моему, это очень интересно.

Добавление хэш-таблиц

Хэш-таблицы поддерживают оператор сложения для объединения двух хэш-таблиц.

$person += @

Это эффективно только в том случае, если две хэш-таблицы не имеют общего ключа.

Вложенные хэш-таблицы

Хэш-таблицы можно использовать в качестве значений в хэш-таблице.

$person = @ < name = 'Kevin' age = 36 >$person.location = @<> $person.location.city = 'Austin' $person.location.state = 'TX' 

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

$person = @ < name = 'Kevin' age = 36 location = @< city = 'Austin' state = 'TX' >> 

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

$person.location.city Austin 

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

$people = @ < Kevin = @< age = 36 city = 'Austin' >Alex = @ < age = 9 city = 'Austin' >> 

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

PS> $people.kevin.age 36 PS> $people.kevin['city'] Austin PS> $people['Alex'].age 9 PS> $people['Alex']['City'] Austin 

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

foreach($name in $people.keys) < $person = $people[$name] ', age , is in ' -f $name, $person.age, $person.city > 

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

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

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

PS> $people Name Value ---- ----- Kevin Alex

Для поиска этих элементов я использую команду ConvertTo-JSON , так как она очень прозрачная, и я часто использую JSON для других задач.

PS> $people | ConvertTo-Json < "Kevin": < "age": 36, "city": "Austin" >, "Alex": < "age": 9, "city": "Austin" >> 

Даже если вы не знакомы с JSON, вы сможете просмотреть то, что искали. Существует команда Format-Custom для таких структурированных данных, но мне все-таки больше нравится просмотр в JSON.

Создание объектов

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

$person = [pscustomobject]@ < name = 'Kevin' age = 36 >$person name age ---- --- Kevin 36 

Даже если вы изначально не создаете его как pscustomobject , вы всегда можете выполнить его приведение позже при необходимости.

$person = @ < name = 'Kevin' age = 36 >[pscustomobject]$person name age ---- --- Kevin 36 

У меня уже есть подробная статья о PCSCustomObject, которую я рекомендую прочесть после этого. Она основана на большом объеме данных, которые мы получили отсюда.

Чтение и запись хэш-таблиц в файл

Сохранение в CSV-файл

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

$person | ForEach-Object < [pscustomobject]$_ >| Export-CSV -Path $path 

Опять же, рекомендую ознакомиться с моей публикацией по использованию PCSCustomObject.

Сохранение вложенной хэш-таблицы в файл

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

$people | ConvertTo-JSON | Set-Content -Path $path $people = Get-Content -Path $path -Raw | ConvertFrom-JSON 

В отношении этого метода можно отметить следующие два момента. Сначала JSON записывается в многострочном формате, поэтому мне нужно использовать параметр -Raw , чтобы считать его обратно в одну строку. Второй способ заключается в том, что импортированный объект больше не является [hashtable] . Теперь он является [pscustomobject] , и это может стать проблемой, если вы этого не ожидали.

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

@< a = @< b = @< c = @< d = "e" >>>> | ConvertTo-Json < "a": < "b": < "c": "System.Collections.Hashtable" >> > 

Используйте параметр Depth, чтобы обеспечить развертывание всех вложенных хэш-таблиц.

@< a = @< b = @< c = @< d = "e" >>>> | ConvertTo-Json -Depth 3 < "a": < "b": < "c": < "d": "e" >> > > 

Если вы хотите, чтобы при импорте это был [hashtable] , в этом случае вам придется использовать команды Export-CliXml и Import-CliXml .

Преобразование JSON в хэш-таблицу

Если необходимо преобразовать JSON в [hashtable] , это можно сделать с помощью JavaScriptSerializer в .NET.

[Reflection.Assembly]::LoadWithPartialName("System.Web.Script.Serialization") $JSSerializer = [System.Web.Script.Serialization.JavaScriptSerializer]::new() $JSSerializer.Deserialize($json,'Hashtable') 

Начиная с PowerShell версии 6, для поддержки JSON используется NewtonSoft JSON.NET, а также добавлена поддержка хэш-таблиц.

'< "a": "b" >' | ConvertFrom-Json -AsHashtable Name Value ---- ----- a b 

В PowerShell 6.2 добавлен параметр Depth для ConvertFrom-Json . Значение по умолчанию для параметра Depth — 1024.

Чтение непосредственно из файла

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

$content = Get-Content -Path $Path -Raw -ErrorAction Stop $scriptBlock = [scriptblock]::Create( $content ) $scriptBlock.CheckRestrictedLanguage( $allowedCommands, $allowedVariables, $true ) $hashtable = ( & $scriptBlock ) 

Он импортирует содержимое файла в scriptblock , а затем проверяет, чтобы перед его выполнением в нем не было других команд PowerShell.

Знаете ли вы, что манифест модуля (файл PSD1) является просто хэш-таблицей?

Ключом может быть любой объект.

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

$person = @ < 'full name' = 'Kevin Marquette' '#' = 3978 >$person['full name'] 

Вы можете выполнить практически любые задачи, даже если раньше не знали, что это вообще возможно.

$person.'full name' $key = 'full name' $person.$key 

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

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

$ht = @ < @(1,2,3) = "a" >$ht Name Value ---- ----- a 

Доступ к значению в хэш-таблице по ключу не всегда работает. Пример:

$key = $ht.keys[0] $ht.$($key) a $ht[$key] a 

Если ключ является массивом, необходимо заключить переменную $key в часть выражения, чтобы ее можно было использовать с нотацией доступа к членам ( . ). Или можно использовать нотацию индекса массива ( [] ).

Использование в автоматических переменных

$PSBoundParameters

$PSBoundParameters — это автоматическая переменная, которая существует только в контексте функции. Она содержит все параметры, с которыми вызывалась функция. Это не совсем хэш-таблица, но достаточно близка к тому, чтобы ее можно было обрабатывать как хэш-таблицу.

Это предполагает удаление ключей и ее сплаттинг в другие функции. Если вы намерены писать функции прокси-сервера, ознакомьтесь со следующими сведениями.

Дополнительные сведения см. в разделе about_Automatic_Variables.

Проблема с PSBoundParameters

Важно помнить, что он включает только значения, передаваемые в качестве параметров. Если у вас также есть параметры со значениями по умолчанию, но они не передаются вызывающей стороной, $PSBoundParameters не содержит этих значений. Обычно этот момент упускается из вида.

$PSDefaultParameterValues

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

$PSDefaultParameterValues["Out-File:Encoding"] = "UTF8" 

При этом в хэш-таблицу $PSDefaultParameterValues добавляется запись, которая задает UTF8 в качестве значения по умолчанию для параметра Out-File -Encoding . Это зависит от сеанса, поэтому его следует поместить в $profile .

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

$PSDefaultParameterValues[ "Connect-VIServer:Server" ] = 'VCENTER01.contoso.local' 

Это также позволяет использовать подстановочные знаки для группового указания значений. Далее описывается несколько способов использования этой операции:

$PSDefaultParameterValues[ "Get-*:Verbose" ] = $true $PSDefaultParameterValues[ "*:Credential" ] = Get-Credential 

Более подробно это рассматривается в отличной статье об Автоматические значения по умолчанию, написанной Майкл Соренс.

Регулярное выражение $Matches

При использовании оператора -match создается автоматическая переменная с именем $matches , которая содержит результаты сопоставления. Если в регулярном выражении есть какие-либо подвыражения, то в список также включаются соответствующие части совпадений.

$message = 'My SSN is 123-45-6789.' $message -match 'My SSN is (.+)\.' $Matches[0] $Matches[1] 

Именованные совпадения

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

$message = 'My Name is Kevin and my SSN is 123-45-6789.' if($message -match 'My Name is (?.+) and my SSN is (?.+)\.')

В приведенном выше примере (?.*) является именованной частью выражения. Это значение затем помещается в свойство $Matches.Name .

Group-Object -AsHashtable

Одна из малоизвестных возможностей в Group-Object — возможность преобразовать некоторые наборы данных в хэш-таблицу.

Import-CSV $Path | Group-Object -AsHashtable -Property email 

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

Копирование хэш-таблиц

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

Присвоение ссылочных типов

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

PS> $orig = @ PS> $copy = $orig PS> $copy.name = 'copy' PS> 'Copy: []' -f $copy.name PS> 'Orig: []' -f $orig.name Copy: [copy] Orig: [copy] 

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

Неполные копии, одноуровневые

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

PS> $orig = @ PS> $copy = $orig.Clone() PS> $copy.name = 'copy' PS> 'Copy: []' -f $copy.name PS> 'Orig: []' -f $orig.name Copy: [copy] Orig: [orig] 

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

Неполные копии, вложенные

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

PS> $orig = @ < person=@< name='orig' >> PS> $copy = $orig.Clone() PS> $copy.person.name = 'copy' PS> 'Copy: []' -f $copy.person.name PS> 'Orig: []' -f $orig.person.name Copy: [copy] Orig: [copy] 

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

Полные копии

Есть несколько способов создать полную копию хэш-таблицы (оставив ее хэш-таблицей). Следующая функция использует PowerShell для рекурсивного создания полной копии:

function Get-DeepClone < [CmdletBinding()] param( $InputObject ) process < if($InputObject -is [hashtable]) < $clone = @<>foreach($key in $InputObject.keys) < $clone[$key] = Get-DeepClone $InputObject[$key] >return $clone > else < return $InputObject >> > 

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

Другой способ — использовать .NET для десериализации таблицы с помощью CliXml, как в следующей функции:

function Get-DeepClone

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

Что-нибудь еще?

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

Совместная работа с нами на GitHub

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

Хеш-таблица

Существует два основных вида хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив [math]H[/math] , элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).

Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Хеш-код [math]i = h(key)[/math] играет роль индекса в массиве [math]H[/math] , а зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).

Количество коллизий зависит от хеш-функции; чем лучше используемая хеш-функция, тем меньше вероятность их возникновения.

Вероятность коллизий при вставке в хеш-таблицу превышает 50%

Пусть хеш-таблица имеет размер [math]len[/math] и в нее добавляют [math]n[/math] элементов. Рассмотрим [math]

‘(n)[/math] — вероятность того, что не возникнет ни одной коллизии. Добавим два любых элемента в нашу хеш-таблицу. Вероятность того, что они не попадут в одну и ту же ячейку таблицы равна [math]1 — \dfrac[/math] . Возьмем еще один элемент. Тогда вероятность того, что третий элемент не попадет в одну из уже занятых ячеек равна [math]1 — \dfrac[/math] . Рассуждая аналогичным образом, получим формулу: [math]

‘(n) = \left( 1 — \dfrac\right )\cdot \left( 1 — \dfrac\right )\dots\left( 1 — \dfrac\right ) = \dfrac> = \dfrac \cdot \left (len — n \right)!>[/math]

Тогда [math]

(n)[/math] — вероятность возникновения коллизии равна: [math]p(n) = 1 —

‘(n)[/math] ,

Способ разрешения коллизий — важная составляющая любой хеш-таблицы.

Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с прямой адресацией; в них все операции, такие как: поиск, вставка и удаление работают за [math]O(1)[/math] .

Если мы поделим число хранимых элементов на размер массива [math]H[/math] (число возможных значений хеш-функции), то узнаем коэффициент заполнения хеш-таблицы (англ. load factor). От этого параметра зависит среднее время выполнения операций.

Хеширование

Хеширование (англ. hashing) — класс методов поиска, идея которого состоит в вычислении хеш-кода, однозначно определяемого элементом с помощью хеш-функции, и использовании его, как основы для поиска (индексирование в памяти по хеш-коду выполняется за [math]O(1)[/math] ). В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций. Для того чтобы коллизии не замедляли работу с таблицей существуют методы для борьбы с ними.

Определение:
[math]U [/math] — множество объектов (универсум).
[math]h : U \rightarrow S = \mathcal 0 \dots m — 1 \mathcal [/math] — называется хеш-функцией, где множество [math]S[/math] хранит ключи из множества [math]U[/math] .
Если [math]x \in U[/math] значит [math]h(x) \in S[/math]
Коллизия (англ. collision): [math]\exists x \neq y : h(x) = h(y)[/math]
Виды хеширования
  • По способу хранения:

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

Динамическое — добавляем, удаляем и смотрим на наличие нужных элементов.

  • По виду хеш-функции:

Свойства хеш-таблицы

На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в списке, а именно [math]\Theta(n)[/math] , но на практике хеширование более эффективно. При некоторых разумных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет [math]O(1)[/math] . А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время [math]O(1)[/math] . При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо перехешировать таблицу: увеличить размер массива [math]H[/math] и заново добавить в новую хеш-таблицу все пары.

Хеширование в современных языках программирования

Почти во всех современных языках присутствуют классы, реализующие хеширование. Рассмотрим некоторые из них.

  • Java
    • HashMap [1] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
    • HashSet [2] — реализация интерфейса множества с использованием хеш-таблицы,
    • LinkedHashMap [3] — потомок класса HashMap. Позволяет просматривать значения в том порядке, в котором они были добавлены.
    • unordered_map [4] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
    • unordered_set [5] — реализация интерфейса множества с использованием хеш-таблицы.
    • dict [6] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
    • set [7] — реализация интерфейса множества с использованием хеш-таблицы.

    Примечания

    1. ↑HashMap — Java Platform SE 7
    2. ↑HashSet — Java Platform SE 7
    3. ↑LinkedHashMap — Java Platform SE 7
    4. ↑unordered_map — cplusplus.com
    5. ↑unordered_set — cplusplus.com
    6. ↑dictobject.c — https://github.com/python/cpython
    7. ↑setobject.c — https://hg.python.org

    Источники информации

    • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» — «Вильямс», 2011 г. — 1296 стр. — ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
    • Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» — «Вильямс», 2007 г. — 824 стр. — ISBN 0-201-89685-0
    • Википедия — Хеш-таблица
    • Дискретная математика и алгоритмы
    • Хеширование
    • Структуры данных

    Хеш-таблицы

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

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

    image

    Мотивация использовать хеш-таблицы

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

    Контейнер \ операция insert remove find
    Array O(N) O(N) O(N)
    List O(1) O(1) O(N)
    Sorted array O(N) O(N) O(logN)
    Бинарное дерево поиска O(logN) O(logN) O(logN)
    Хеш-таблица O(1) O(1) O(1)

    Все данные при условии хорошо выполненных контейнерах, хорошо подобранных хеш-функциях

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

    Понятие хеш-таблицы

    Хеш-таблица — это контейнер, который используют, если хотят быстро выполнять операции вставки/удаления/нахождения. В языке C++ хеш-таблицы скрываются под флагом unoredered_set и unordered_map. В Python вы можете использовать стандартную коллекцию set — это тоже хеш-таблица.
    Реализация у нее, возможно, и не очевидная, но довольно простая, а главное — как же круто использовать хеш-таблицы, а для этого лучше научиться, как они устроены.

    Для начала объяснение в нескольких словах. Мы определяем функцию хеширования, которая по каждому входящему элементу будет определять натуральное число. А уже дальше по этому натуральному числу мы будем класть элемент в (допустим) массив. Тогда имея такую функцию мы можем за O(1) обработать элемент.

    Теперь стало понятно, почему же это именно хеш-таблица.

    Проблема коллизии

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

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

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

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

    Одна хеш-функция (при входе g) будет возвращать натуральное число s, которое будет для нас начальным. То есть первое, что мы сделаем, попробуем поставить элемент g на позицию s в нашем массиве. Но что, если это место уже занято? Именно здесь нам пригодится вторая хеш-функция, которая будет возвращать t — шаг, с которым мы будем в дальнейшем искать место, куда бы поставить элемент g.

    Мы будем рассматривать сначала элемент s, потом s + t, затем s + 2*t и т.д. Естественно, чтобы не выйти за границы массива, мы обязаны смотреть на номер элемента по модулю (остатку от деления на размер массива).

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

    Реализация хеш-таблицы

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

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

    int HashFunctionHorner(const std::string& s, int table_size, const int key) < int hash_result = 0; for (int i = 0; s[i] != s.size(); ++i) hash_result = (key * hash_result + s[i]) % table_size; hash_result = (hash_result * 2 + 1) % table_size; return hash_result; >struct HashFunction1 < int operator()(const std::string& s, int table_size) const < return HashFunctionHorner(s, table_size, table_size - 1); // ключи должны быть взаимопросты, используем числа плюс и минус один. > >; struct HashFunction2 < int operator()(const std::string& s, int table_size) const < return HashFunctionHorner(s, table_size, table_size + 1); >>;

    Чтобы идти дальше, нам необходимо разобраться с проблемой: что же будет, если мы удалим элемент из таблицы? Так вот, его нужно пометить флагом deleted, но просто удалять его безвозвратно нельзя. Ведь если мы так сделаем, то при попытке найти элемент (значение хеш-функции которого совпадет с ее значением у нашего удаленного элемента) мы сразу наткнемся на пустую ячейку. А это значит, что такого элемента и не было никогда, хотя, он лежит, просто где-то дальше в массиве. Это основная сложность использования данного метода решения коллизий.

    Помня о данной проблеме построим наш класс.

    template class HashTable < static const int default_size = 8; // начальный размер нашей таблицы constexpr static const double rehash_size = 0.75; // коэффициент, при котором произойдет увеличение таблицы struct Node < T value; bool state; // если значение флага state = false, значит элемент массива был удален (deleted) Node(const T& value_) : value(value_), state(true) <>>; Node** arr; // соответственно в массиве будут хранится структуры Node* int size; // сколько элементов у нас сейчас в массиве (без учета deleted) int buffer_size; // размер самого массива, сколько памяти выделено под хранение нашей таблицы int size_all_non_nullptr; // сколько элементов у нас сейчас в массиве (с учетом deleted) >;

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

    . 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; // заполняем nullptr - то есть если значение отсутствует, и никто раньше по этому адресу не обращался >~HashTable()

    Из необходимых методов осталось еще реализовать динамическое увеличение, расширение массива — метод Resize.

    Увеличиваем размер мы стандартно вдвое.

    void Resize() < int past_buffer_size = buffer_size; buffer_size *= 2; 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 < past_buffer_size; ++i) < if (arr2[i] && arr2[i]->state) Add(arr2[i]->value); // добавляем элементы в новый массив > // удаление предыдущего массива for (int i = 0; i

    Немаловажным является поддержание асимптотики O(1) стандартных операций. Но что же может повлиять на скорость работы? Наши удаленные элементы (deleted). Ведь, как мы помним, мы ничего не можем с ними сделать, но и окончательно обнулить их не можем. Так что они тянутся за нами огромным балластом. Для ускорения работы нашей хеш-таблицы воспользуемся рехешом (как мы помним, мы уже выделяли под это очень странные переменные).

    Теперь воспользуемся ими, если процент реальных элементов массива стал меньше 50, мы производим Rehash, а именно делаем то же самое, что и при увеличении таблицы (resize), но не увеличиваем. Возможно, это звучит глуповато, но попробую сейчас объяснить. Мы вызовем наши хеш-функции от всех элементов, переместим их в новых массив. Но с deleted-элементами это не произойдет, мы не будем их перемещать, и они удалятся вместе со старой таблицей.

    Но к чему слова, код все разъяснит:

    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

    Ну теперь мы уже точно на финальной, хоть и длинной, и полной колючих кустарников, прямой. Нам необходимо реализовать вставку (Add), удаление (Remove) и поиск (Find) элемента.

    Начнем с самого простого — метод Find элемент по значению.

    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; // если у нас i >= buffer_size, значит мы уже обошли абсолютно все ячейки, именно для этого мы считаем i, иначе мы могли бы зациклиться. > return false; >

    Далее мы реализуем удаление элемента — Remove. Как мы это делаем? Находим элемент (как в методе Find), а затем удаляем, то есть просто меняем значение state на false, но сам Node мы не удаляем.

    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; >

    Ну и последним мы реализуем метод Add. В нем есть несколько очень важных нюансов. Именно здесь мы будем проверять на необходимость рехеша.

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

    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(); // происходит рехеш, так как слишком много deleted-элементов 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) // если не нашлось подходящего места, создаем новый Node < arr[h1] = new Node(value); ++size_all_non_nullptr; // так как мы заполнили один пробел, не забываем записать, что это место теперь занято >else < arr[first_deleted]->value = value; arr[first_deleted]->state = true; > ++size; // и в любом случае мы увеличили количество элементов return true; >

    В заключение приведу полную реализацию хеш-таблицы.

    int HashFunctionHorner(const std::string& s, int table_size, const int key) < int hash_result = 0; for (int i = 0; s[i] != s.size(); ++i) < hash_result = (key * hash_result + s[i]) % table_size; >hash_result = (hash_result * 2 + 1) % table_size; return hash_result; > struct HashFunction1 < int operator()(const std::string& s, int table_size) const < return HashFunctionHorner(s, table_size, table_size - 1); >>; struct HashFunction2 < int operator()(const std::string& s, int table_size) const < return HashFunctionHorner(s, table_size, table_size + 1); >>; template class HashTable < static const int default_size = 8; constexpr static const double rehash_size = 0.75; struct Node < T value; bool state; Node(const T& value_) : value(value_), state(true) <>>; Node** arr; int size; int buffer_size; int size_all_non_nullptr; void Resize() < int past_buffer_size = buffer_size; buffer_size *= 2; 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 < 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; > >;

    Хеш-таблицы — Python: Cловари и множества

    Ассоциативный массив — абстрактный тип данных, с помощью которого хранятся пары «ключ-значение». В разных языках ему соответствуют разные типы данных. В Python — это Dictionary, в других языках:

    • Ruby — Hash
    • Lua — Table
    • JavaScript — Object
    • Elixir/Java — Map

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

    В обычном индексированном массиве значения расположены по индексам, а значит его можно положить в память «как есть». С ассоциативными массивами все работает по-другому. У них нет индексов, которые бы могли определить порядок — значит, и нет простого способа добраться до значений.

    Для реализации ассоциативных массивов часто используют специальную структуру данных — хеш-таблицу.

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

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

    data = <> data['key'] = 'value' 

    Что такое хеширование

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

    • Найти хеш, то есть хешировать ключ
    • Привести ключ к индексу — например, через остаток от деления

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

    Наиболее известны CRC32, MD5, SHA и много других типов хеширования:

    # В Python есть библиотека zlib, содержащая алгоритм хеширования crc32 # Этот алгоритм удобен для наглядности import zlib # Любые данные, которые мы хотим хешировать, представляются в виде байтовой строки data = b'Hello, world!' hash = zlib.crc32(data) # Хеш всегда одинаковый для одних и тех же данных print(hash) # => 3957769958 

    С хешированием мы встречаемся в разработке часто. Например, идентификатор коммита в git 0481e0692e2501192d67d7da506c6e70ba41e913 — это хеш, полученный в результате хеширования данных коммита.

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

    # Это делается для того, чтобы индексы не были слишком большими # Чем больше размер массива, тем больше памяти он занимает index = abs(hash) % 1000 # по модулю print(index) # => 958 

    Как хеширование работает изнутри

    Рассмотрим, как работает добавление нового значения в ассоциативный массив. Напомним, в Python он представлен типом данных Dictionary. Напишем такой код:

    data = <> data['key'] = 'value' 

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

      Мы создаем ассоциативный массив. Внутри интерпретатора происходит инициализация индексированного массива:

    internal = [] 
    data['key'] = 'value' 
    hash = zlib.crc32(b'key') 
    index = abs(hash) % 1000 
    internal[index] = ['key', 'value'] 

    Теперь посмотрим, как работает чтение данных:

    data = <> data['key'] = 'value' print(data['key']) # => "value" 

    Разберем, как этот код работает изнутри.

      Интерпретатор хеширует ключ. Результатом хеширования становится число:

    hash = zlib.crc32(b'key') 
    index = abs(hash % 1000) 
    return internal[index] # ['key', 'value'] 

    Коллизии

    Ключом в ассоциативном массиве может быть абсолютно любая строка, любой длины и содержания. Но здесь есть одно противоречие:

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

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

    Такую ситуацию принято называть коллизией. Есть несколько способов разрешения коллизий . Каждому способу соответствует свой тип хеш-таблицы:

    # Пример коллизии # Хеш-функция возвращает одинаковый хеш для разных строчных данных zlib.crc32(b'aaaaa0.462031558722291') # 1938556049 zlib.crc32(b'aaaaa0.0585754039730588') # 1938556049 

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

    Открыть доступ

    Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

    • 130 курсов, 2000+ часов теории
    • 1000 практических заданий в браузере
    • 360 000 студентов

    Наши выпускники работают в компаниях:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *