Hashtable - работаем с хеш-таблицей

Добавлен , опубликован
Раздел:
Триггеры и объекты
Хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Не будем вдаваться в подробности принципа её работы, об этом вы можете прочитать здесь.
В статье мы рассмотрим самую распространённую область её применения в wc3: прикрепление данных к объекту, на простейшем примере. Статья предполагает, что читатель знаком с основами работы таймеров. Пример будет только на обычном Jass, для совместимости (да и не все умеют работать c v/cJass).
Если вы знакомы с кэшем в wc3, то принцип работы с ним схож, с принципом работы с хеш-таблицей. Только вместо строковых ключей, хеш-таблица использует целочисленные значения (integer).
Допустим, мы хотим создать спелл, в котором врагу на протяжении некоторого времени с малым периодом постоянно наносится урон (для которого wait не подходит).
Мы создали триггер (в редакторе триггеров, для простоты объяснения) с событием каста, дали ему условия и действия:
function Spell takes nothing returns nothing
    local unit caster = GetSpellAbilityUnit()  //Кастер
    local unit target = GetSpellTargetUnit()   //Цель
endfunction

//Проверка спелла
function SpellCond takes nothing returns boolean
    return GetSpellAbilityId()=='A000'
endfunction

//===========================================================================
function InitTrig_Spell takes nothing returns nothing
    set gg_trg_Spell = CreateTrigger()
    call TriggerRegisterPlayerUnitEvent(gg_trg_Spell,Player(0),EVENT_PLAYER_UNIT_SPELL_CAST,null)
    call TriggerAddCondition(gg_trg_Spell,Condition(function SpellCond))
    call TriggerAddAction(gg_trg_Spell,function Spell)
endfunction
Далее, нам нужен таймер, который будет периодически вызывать функцию, внутри которой наносится урон:
function SpellDamage takes nothing returns nothing
    call UnitDamageTarget(...)
endfunction

function Spell takes nothing returns nothing
    local unit caster = GetSpellAbilityUnit()  //Кастер
    local unit target = GetSpellTargetUnit()   //Цель
    local timer t = CreateTimer()              //Создаём таймер
    
    call TimerStart(t,0.04,true,function SpellDamage) //Стартуем таймер
endfunction
Но как передать в функцию, кто кому должен наносить урон, и сколько раз? Тут нам на помощь и приходит хеш-таблица. Перед работой нужно создать и инициализировать глобальную хеш-таблицу, желательно при инициализации карты.
*1
Хеш-таблица - очень массивный объект и занимает много места в памяти, поэтому рекомендуется создавать только одну на все действия в карте. В противном случае, игра просто может слететь с фаталом или зависнуть от переполнения.
Делать это нужно только один раз, например в этом триггере:
function InitTrig_Spell takes nothing returns nothing
    set gg_trg_Spell = CreateTrigger()
    call TriggerRegisterPlayerUnitEvent(gg_trg_Spell,Player(0),EVENT_PLAYER_UNIT_SPELL_CAST,null)
    call TriggerAddCondition(gg_trg_Spell,Condition(function SpellCond))
    call TriggerAddAction(gg_trg_Spell,function Spell)
    
    set udg_hash = InitHashtable() //Инициализируем хеш-таблицу
endfunction
*2
Если в карте имеется несколько спеллов, то рекомендуется инициализировать хеш-таблицу в отдельном действии/триггере при инициализации, чтобы избежать накладок во время редактирования или переноса.
Работает хеш-таблица так: [ключ|значение]. Только как ключ мы используем уникальный id объекта, а точнее - id нашего таймера.
На него и будем сохранять нужные нам данные:
function Spell takes nothing returns nothing
    local unit caster = GetSpellAbilityUnit()  //Кастер
    local unit target = GetSpellTargetUnit()   //Цель
    local timer t = CreateTimer()              //Создаём таймер
    local integer h = GetHandleId(t)           //Узнаём id таймера
    
    //Сохраняем объекты с ключом - id таймера
    call SaveUnitHandle(udg_hash,h,1,caster)   //Сохраняем кастера со значением 1
    call SaveUnitHandle(udg_hash,h,2,target)   //Сохраняем цель со значением 2
    call SaveInteger(udg_hash,h,3,125)         //Сохраняем количество ударов, из расчёта, что урон наносится в течение 5 секунд (5/0.04=125).
    
    call TimerStart(t,0.04,true,function SpellDamage) //Стартуем таймер
    
    //Не забываем устранять утечки
    set caster = null
    set target = null
    set t = null
endfunction
*3
Также можно делать без создания переменной h:
call SaveUnitHandle(udg_hash,GetHandleId(t),1,caster)
Утечек это не вызовет, но немного снизит производительность.
*4
Аналогичными действиями сохраняются и другие объекты, например группа:
call SaveGroupHandle(udg_hash,h,1,some_group)
Думаю, нет смысла перечислять все функции, так как на это существуют function-листы.
*5
Некоторые утверждают, что сохранение объектов под ключами 1,2,3... неудобно и неуниверсально, и предлагают сохранять через уникальное значение строки:
call SaveUnitHandle(udg_hash,h,StringHash("caster"),caster)
С ними можно согласиться, вам не придётся давать и запоминать цифры для значений. Вы можете использовать такой способ для удобства.
Готово, данные сохранены, теперь их можно будет достать в функции нанесения урона, на которую запущен таймер.
Доставать данные мы будем тоже по id таймера:
function SpellDamage takes nothing returns nothing
    local timer t = GetExpiredTimer()                  //Наш таймер - истёкший
    local integer h = GetHandleId(t)                   //Узнаём id таймера
    local unit caster = LoadUnitHandle(udg_hash,h,1)   //Достаём кастера из значения 1
    local unit target = LoadUnitHandle(udg_hash,h,2)   //Достаём цель из значения 2
    local integer counter = LoadInteger(udg_hash,h,3)  //Достаём количество ударов
    
    if counter>0 then //Если количество ударов больше 0
        call UnitDamageTarget(caster,target,1.0,true,true,ATTACK_TYPE_NORMAL,DAMAGE_TYPE_NORMAL,null) //Наносим урон цели
        call SaveInteger(udg_hash,h,3,counter-1) //Сохраняем количество ударов, убавленное на 1
    else //Иначе 
        call DestroyTimer(t) //Уничтожаем таймер
        //Очищаем хеш-таблицу, чтобы избежать утечек и наложений
        call FlushChildHashtable(udg_hash,h) //Очищаем ключ по id
    endif
    
    //Не забываем устранять утечки
    set caster = null
    set target = null
    set t = null
endfunction
*6
Очень часто встречается неправильная конструкция очистки, приводящая к утечкам:
call DestroyTimer(t)
call FlushChildHashtable(udg_hash,GetHandleId(t))
В данном случае, очистка произведена не будет, так как таймер уничтожается раньше получения его id, поэтому в функцию очистки будет подано неправильное значение (0).
Если вы используете конструкцию без переменной с id, то делать нужно так:
call FlushChildHashtable(udg_hash,GetHandleId(t))
call DestroyTimer(t)
То есть сначала очищать, а потом удалять таймер.
В случае с переменной, порядок этих действий значения не имеет.
Спелл готов, данные записываются, достаются и удаляются из хеш-таблицы.
Вот что у нас получилось в итоге:
function SpellDamage takes nothing returns nothing
    local timer t = GetExpiredTimer()
    local integer h = GetHandleId(t)
    local unit caster = LoadUnitHandle(udg_hash,h,1)
    local unit target = LoadUnitHandle(udg_hash,h,2)
    local integer counter = LoadInteger(udg_hash,h,3)
    
    if counter>0 then
        call UnitDamageTarget(caster,target,1.0,true,true,ATTACK_TYPE_NORMAL,DAMAGE_TYPE_NORMAL,null)
        call SaveInteger(udg_hash,h,3,counter-1)
    else
        call DestroyTimer(t)
        call FlushChildHashtable(udg_hash,h)
    endif
    
    set caster = null
    set target = null
    set t = null
endfunction

function Spell takes nothing returns nothing
    local unit caster = GetSpellAbilityUnit()
    local unit target = GetSpellTargetUnit()
    local timer t = CreateTimer()
    local integer h = GetHandleId(t)
    
    call SaveUnitHandle(udg_hash,h,1,caster)
    call SaveUnitHandle(udg_hash,h,2,target)
    call SaveInteger(udg_hash,h,3,125)
    
    call TimerStart(t,0.04,true,function SpellDamage)
    
    set caster = null
    set target = null
    set t = null
endfunction

function SpellCond takes nothing returns boolean
    return GetSpellAbilityId()=='A000'
endfunction

//===========================================================================
function InitTrig_Spell takes nothing returns nothing
    set gg_trg_Spell = CreateTrigger()
    call TriggerRegisterPlayerUnitEvent(gg_trg_Spell,Player(0),EVENT_PLAYER_UNIT_SPELL_CAST,null)
    call TriggerAddCondition(gg_trg_Spell,Condition(function SpellCond))
    call TriggerAddAction(gg_trg_Spell,function Spell)
    
    set udg_hash = InitHashtable()
endfunction
К статье прикрепляю карту-пример со спеллом.
`
ОЖИДАНИЕ РЕКЛАМЫ...
2
15
2 года назад
2
Поскольку эта статья входит в список статей XGM по Варкрафту, думаю стоит доработать её, а именно информацию о ресурсоёмкости хэш-таблиц, миф о которых развеивается Анрайзом: xgm.guru/p/wc3/Jass-MythBusters-9RA
0
17
2 года назад
0
думаю стоит доработать её, а именно информацию о ресурсоёмкости хэш-таблиц
Что за ресурсоёмкость
4
20
2 года назад
Отредактирован Unryze
4
думаю стоит доработать её, а именно информацию о ресурсоёмкости хэш-таблиц
Что за ресурсоёмкость
Речь об этом высказывании:
Что не является правдой, ибо память выделятся динамически для каждой ячейки. Есть изначальный размер CGameHashTableManager (который существует по факту всегда), ну и каждая ХТ - имеет свой вес:
Размер Хештаблицы:
То бишь 0x34 байта выделены всегда, каждая ХТ по стандарту - это 0x28 байт опять, и каждая новая ячейка - 4 байта (исключение boolean (1 байт) и string (каждый символ = 1 байт)).
0x34 = 52 байта.
0x28 = 40 байт.
Загруженные файлы
0
26
2 года назад
0
Спустя 10 лет еще кому-то не пофиг? Вообще я в комментах отвечал, что имелось в виду.
У нас нет действия типа DestroyHashtable, то есть таблицы нельзя удалять. Поэтому если в каком-то действии постоянно создаются таблицы, память будет течь.
То бишь 0x34 байта выделены всегда, каждая ХТ по стандарту - это 0x28 байт опять, и каждая новая ячейка - 4 байта (исключение boolean (1 байт) и string (каждый символ = 1 байт)).
Здесь главный вопрос деаллокается ли память обратно при удалении элементов. Если да, то утечку памяти хотя бы можно минимизировать очисткой. Если нет, то это вообще жопа и мое утверждение верно на 100%.
2
20
2 года назад
Отредактирован Unryze
2
Спустя 10 лет еще кому-то не пофиг? Вообще я в комментах отвечал, что имелось в виду.
У нас нет действия типа DestroyHashtable, то есть таблицы нельзя удалять. Поэтому если в каком-то действии постоянно создаются таблицы, память будет течь.
40 байт единожды потерять, не знаю даже. Если оно очень надо, то я могу написать код для мемхака для удаления хештаблицы и очистки индекса. Но это даст ровно 40 байт и всё, что банально не скажется ни на чём.
То бишь 0x34 байта выделены всегда, каждая ХТ по стандарту - это 0x28 байт опять, и каждая новая ячейка - 4 байта (исключение boolean (1 байт) и string (каждый символ = 1 байт)).
Здесь главный вопрос деаллокается ли память обратно при удалении элементов. Если да, то утечку памяти хотя бы можно минимизировать очисткой. Если нет, то это вообще жопа и мое утверждение верно на 100%.
Да, она очищается при очистке ячейки, то бишь именно Flush/RemoveSaved. И нет, ни первое ни второе утверждения не верны. Это как сказать "ну ты же используешь глобалку, вот 4 байта всегда заняты". Что конечно частично верно, но на деле не даст разницы никакой, а почти во всех картах есть туча неиспользуемых глобалок, что явно превысит 40 жалких байт, которые хештаблица занимает единожды.
Если же реально эти 40 байт на столько прямо необходимы, то тогда уже проблема не в отсутствии удаления хештаблицы, а в самой карте. (:
П.С. поправка моего предыдущего коммента, каждая ячейка это всё-таки 4 байт. (и да, я попутал ячейку и тип переменной), То бишь сообщение про вес - это про сам тип переменных, а не ячейки.
Загруженные файлы
0
26
2 года назад
0
40 байт единожды потерять, не знаю даже.
Почему единожды? Я говорю, если локальные таблицы постоянно создавать. В цикле например или на каких-то событиях.
Непонятно какая речь про жалкость 40 байт, если люди умудряются память даже точками засрать, которые казалось бы имеют размер еще меньше.
Суть в том, что если есть объект, который можно создать, но нельзя удалить, это утечка. В варе такого дофига.
3
20
2 года назад
3
40 байт единожды потерять, не знаю даже.
Почему единожды? Я говорю, если локальные таблицы постоянно создавать. В цикле например или на каких-то событиях.
Создавать хештаблицу локально? Что? Зачем? Это глупость полнейшая.
Hanabishi:
Непонятно какая речь про жалкость 40 байт, если люди умудряются память даже точками засрать, которые казалось бы имеют размер еще меньше.
Это засирается утечками и косячностью локальных хендлов, да и ровняться извини на рукожопов - не думаю что имеет смысла.
Hanabishi:
Суть в том, что если есть объект, который можно создать, но нельзя удалить, это утечка. В варе такого дофига.
Который адекватные люди создают единожды, собственно никакой утечки нет. И повторюсь, если очень надо, тот мемхаком можно очистить занятую ХТ. Просто я не вижу в этом смысла, пытаться делать систему под тех, кто не понимают как использовать Хештаблицу (аля БД) и твой юзкейс ну вообще не встречается нигде (я лично такого никогда не видел).
0
17
2 года назад
0
Так ханабиши и написал - создавать только одну
2
20
2 года назад
2
Так ханабиши и написал - создавать только одну
Я отвечал на это, "Я говорю, если локальные таблицы постоянно создавать" и "В цикле например или на каких-то событиях." В сообщении же вроде видны цитаты. :(
Загруженные файлы
1
26
2 года назад
Отредактирован Hanabishi
1
Unryze, ты видимо как-то криво отвечаешь. Вот с твоей же цитаты.
Ты сам придумал про единожды, а я изначально сразу указал кейс.
Весь поинт сообщения как раз в том, что лучше создавать только ограниченное количество таблиц на карту. Потому что могут найтись уникумы, которые на каждый каст будут новую таблицу заводить. Так что я не знаю что там придумать пытаетесь.
Загруженные файлы
2
20
2 года назад
2
Unryze, ты видимо как-то криво отвечаешь. Вот с твоей же цитаты.
Ты сам придумал про единожды, а я изначально сразу указал кейс.
Весь поинт сообщения как раз в том, что лучше создавать только ограниченное количество таблиц на карту. Потому что могут найтись уникумы, которые на каждый каст будут новую таблицу заводить. Так что я не знаю что там придумать пытаетесь.
Я не заметил если честно вот этого "Поэтому если в каком-то действии постоянно создаются таблицы, память будет течь.", но я опять же расписал дальше, что такие юзкейсы - не показатель и не встречаютяс нигде, хватит уже муслоить ересь, пожалуйста. Да и ссылаясь на твоё: "если люди умудряются память даже точками засрать", то твоя позиция имеет ещё меньше смысла, ибо невозможно вылечить тех, кто не умеют кодить или кодят на уровне "работает и пофиг".
Повторяю последний раз, то, что у нас нет возможности удалить Хештаблицу не меняет ровным счётом ничего, ибо нет адекватного юзкейса, где кто-то бы ударился даже в лимит хештаблиц или банально создавал бы их локально (хрен пойми зачем). Говоря проще, твой юзкейс - это полноценный бред, который не встречается нигде.
0
26
2 года назад
Отредактирован Hanabishi
0
Говоря проще, твой юзкейс - это полноценный бред, который не встречается нигде.
Так статья на то и нужна, что предупреждает людей так не делать. Ты ведь не думаешь, что зашедшие читать эту статью знают правильные юзкейсы?
Может там конечно не совсем ясно донесена мысль, но суть такая: не создавайте таблицы в больших количествах. Все остальное вы уже начинаете додумывать.
0
20
2 года назад
0
Говоря проще, твой юзкейс - это полноценный бред, который не встречается нигде.
Так статья на то и нужна, что предупреждает людей так не делать. Ты ведь не думаешь, что зашедшие читать эту статью знают правильные юзкейсы?
Может там конечно не совсем ясно донесена мысль, но суть такая: не создавайте таблицы в больших количествах. Все остальное вы уже начинаете додумывать.
Ну, это уже другой юзкейс, я повторюсь "Я говорю, если локальные таблицы постоянно создавать." если ты имеешь ввиду local hashtable, то таких юзкейсов нет вообще. Если же ты просто про "каждая система - своя хештаблица", то даже так добраться до 256 надо очень и очень постараться. Но я тебя понял, ты делаешь акцент на совсем далёких от джасса, которые ещё и умудрились до хеша добраться. :D
Закончим тем, что фактической необходимости в удалении хештаблицы - нет, ибо за всё это время ещё никто не жаловался на лимит хештаблиц.
0
26
2 года назад
0
Закончим тем, что фактической необходимости в удалении хештаблицы - нет
Да. Если не создаешь, то и удалять не надо. А глобальные в любом случае существуют всю игру.
ибо за всё это время ещё никто не жаловался на лимит хештаблиц.
Не совсем так xgm.guru/p/wc3/hashtable8000
0
20
2 года назад
0
Закончим тем, что фактической необходимости в удалении хештаблицы - нет
Да. Если не создаешь, то и удалять не надо. А глобальные в любом случае существуют всю игру.
... )0
ибо за всё это время ещё никто не жаловался на лимит хештаблиц.
Не совсем так xgm.guru/p/wc3/hashtable8000
И где это в итоге применялось? Нигде? О чём и речь.
0
17
2 года назад
0
И где это в итоге применялось? Нигде? О чём и речь.
Если вы были бы автор этой работы, то имели бы представление о том где это используется. Так что призываю использовать те аргументы, за которые можете нести ответственность
0
20
2 года назад
0
И где это в итоге применялось? Нигде? О чём и речь.
Если вы были бы автор этой работы, то имели бы представление о том где это используется. Так что призываю использовать те аргументы, за которые можете нести ответственность
Влод, не воспринимай в штыки, но кроме тебя это кто-то использует? Если да, то покажи мне пожалуйста карту или что-нибудь где это чудо-юдо имеет место быть. Утомляете вы оба "если что-то есть, значит оно нужно". Речь о распространении тех или иных систем и в целом их применении. Если же ты один сам и используешь свою систему - это не значит, что она "о том где это используется", если случай единичный. Я разобрал предостаточно карт и что-то нигде этой системы не увидел, хватит уже пытаться оправдать глупости.
0
17
2 года назад
0
Конечно я могу рассказать о том кто это использовал и где, но это не изменит тот факт, что вы сочли возможным оценить "применяемость" работы без объективных на то предпосылок, из чего следует:
  1. Что на самом деле объективные предпосылки вам не нужны, иначе вы бы изначально поинтересовались у меня или у других компетентных людей по вопросу "применяемости".
  2. Что упор был сделан на сугубо на личное мнение.
Потому предлагаю сначала изучить примеры в работе, которые были сделаны как раз для ознакомления начинающих, и только после этого мы сможем начать конструктивное обсуждение в соответствующей теме
0
20
2 года назад
0
Конечно я могу рассказать о том кто это использовал и где, но это не изменит тот факт, что вы сочли возможным оценить "применяемость" работы без объективных на то предпосылок, из чего следует:
  1. Что на самом деле объективные предпосылки вам не нужны, иначе вы бы изначально поинтересовались у меня или у других компетентных людей по вопросу "применяемости".
  2. Что упор был сделан на сугубо на личное мнение.
Потому предлагаю сначала изучить примеры в работе, которые были сделаны как раз для ознакомления начинающих, и только после этого мы сможем начать конструктивное обсуждение в соответствующей теме
Стрелка поворачивается и обратно, ну, скинь эти примеры, я посмотрю и я более чем уверен, что прямо необходимости превышать лимит хештаблиц в 256 имеет смысл (что я и писал выше). Если же тебя так задевает, что я не считаю твою наработку полезной, то уж извини, моё мнение в этом плане не измениться, ибо просто на просто захломлять карту псевдо API ещё и через cjass - ну нонсенс.
0
27
2 года назад
0
ибо просто на просто захломлять карту псевдо API
так ты ж делал псевдо-группы для эффектов, предметов и прочего, вместо массива
0
20
2 года назад
0
ибо просто на просто захломлять карту псевдо API
так ты ж делал псевдо-группы для эффектов, предметов и прочего, вместо массива
Верно, но я не считаю её нужной-необходимой. Она даёт удобство работы с группировкой тех хендлов на которых нет стандартного API, но даже так оно имеет больше смысла, нежели расширение количества хештаблиц и всяких надстроек базированных на этом - имеют очень мало смысла, ибо достигнуть коллизии стрингхеша не так уж и легко, разве что только специально стараться это сделать.
По большей части, при особом желании, на всю карту хватит даже 1 хештаблицы, чёрт с ним пусть будет 10. Но куда больше 256? Молчу уже о 8000. В самой игре внутренних хеш таблиц всего 259 (по моей памяти, может и меньше). Потому я не пойму, что такого нужно сделать, чтобы код карты требовал больше хештаблиц, чем вся полноценная игра.
Ну и закончу тем, что моё псевдоАПИ в корне отличается по своему смыслу, потому их сравнивать немного неправильно, однако что моя, что та наработка - не являются де-факто обязательными.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.