Lua: есть ли необходимость использовать хэш строки в качестве ключа в таблицах Lua

Хэш-наборы в Lua

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

Метод - конфликты имен данных

Однако это:

function dict.contains(self, word) do
    return self[word]
end

это плохая идея, потому что внезапно dict:contains("contains") станет правдивым (это будет функция contains).

Точно так же dict.word внезапно тоже станет правдивым, хотя вы, вероятно, хотите, чтобы все доступы проходили через contains.

Я бы рекомендовал просто сделать что-то вроде if words[word] then, а не излишне усложнять это, принудительно переводя это в ООП-стиль, когда это не нужно или полезно. Если вы этого хотите, инкапсулируйте внутренний «набор» слов, поэтому сохраните его в поле типа dict._words, чтобы методы не конфликтовали с фактическими данными, которые вы храните.

Проблемы преждевременной оптимизации

Этот вариант достаточно хорош?

Скорее всего так и есть – попробуйте и увидите. «20 тысяч» — это очень небольшое количество слов, с которыми может справиться Lua. Я не вижу причин, по которым первое решение не могло бы быть полностью удовлетворительным.

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

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

Или, может быть, этот вариант был бы лучше: [...] Я склоняюсь к голосованию за 2-й вариант.

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

• Это более сложно. Эта сложность должна быть оправдана.
• Это добавляет накладные расходы. Вам нужно собственное хеширование строк; вы будете дублировать работу, которую Lua уже выполняет, когда сам интернирует строки.
• Алгоритм хеширования, написанный на Lua, вряд ли превзойдет оптимизированный алгоритм хеширования, присутствующий в вашей реализации Lua, особенно если вы используете хорошо оптимизированный алгоритм, такой как LuaJIT.

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

Да, в Lua 5.2 и более ранних версиях все строки интернированы, и отключить это невозможно. На практике это означает, что разные строки имеют разные адреса, одни и те же строки повторно используют одну и ту же память. Сравнение строк — это простое сравнение адресов и, следовательно, постоянного времени. Это то, что позволяет доступу к таблице всегда иметь значение O (1) вместо O (длина строки).

Так что действительно, в Lua 5.2 и более ранних версиях первый вариант определенно лучше, и намного.

В Lua 5.3 и более поздних версиях все становится немного сложнее: очень «длинные» строки (например, тысячи символов) больше не интернируются, а вместо этого хэшируются по требованию, что означает, что сравнение этих длинных строк осуществляется за O(n), поскольку это доступ к таблице.

Есть два «исключительных обстоятельства», при которых пользовательское хеширование может быть оправдано, но я считаю маловероятным, что вы окажетесь в любом из них:

1. Вы используете более старую реализацию Lua/LuaJIT, которая не защищает от атак коллизий хэшей и нуждается в защите от таких атак, которые могут сделать доступ к таблице O(n) и, таким образом, привести к отказу в обслуживании. В этом случае может помочь пользовательское хеширование — как и просто «засолка» ключей неизвестной злоумышленнику солью.
2. С очень эффективным пользовательским хешированием (подумайте о реализации очень хорошего алгоритма хеширования на C, который каким-то образом превосходит универсальное хеширование строк Lua для вашего варианта использования), вы потенциально можете превзойти встроенное хеширование Lua. Но на этом этапе вам, вероятно, следует с самого начала писать этот критичный к производительности код на C или другом языке, подходящем для максимизации производительности.

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

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

Пока буду загружать ключи, может 2-й вариант все же лучше?

Нет.

TL;DR: Не оптимизируйте преждевременно; скорее всего, вы получите более сложный и менее эффективный код. Просто используйте таблицу со строковыми ключами.

(На самом деле вы можете пропустить хеш-функцию и установить значение ключа как хэш-значение ключа)

Код:

function createHashChecker(hashFunction)
    local hashTable = {}
    return function(value)
        local hashedValue = hashFunction(value)
        if hashTable[hashedValue] then
            return true -- hahsed value is already in hashTable
        else
            hashTable[hashedValue] = true
            return false -- hahsed value was not in hashTable
        end
    end
end

Пример:

local function hashFunction (str)
    return str
end

local checkHash = createHashChecker(hashFunction)

print (checkHash('foo')) -- false
print (checkHash('bar')) -- false
print (checkHash('foo')) -- true

@Луатик

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

И мои препятствия были в основном следующими:

• Если мне действительно не нужно значение/содержимое строки, следует ли мне его сохранить? Чтобы сохранить хеш (4/8 байт хэш-значения в памяти выглядят лучше, чем, скажем, 5-15 символов на слово).

• Если я загружаю эти слова динамически, зачем их «интернировать»? а еще правильнее - как его можно интернировать?

  local data = load()   
  if data then
      for word in data:gmatch("[^\r\n]+") do
          self._words[word] = true
      end 
  end
  

Я полностью согласен с вашей точкой зрения о преждевременной оптимизации. Просто хотел понять - хранит ли lua в памяти три объекта для каждой записи таблицы: hash_key, value и «origin_key» (назовем это отображаемым значением)? Мой подход заключался в том, чтобы избавиться от избыточного визуального представления «довольно длинного» ключа. Теперь я вижу, что во втором варианте у меня все еще есть «отображаемое значение» — это просто отображаемое значение хеша строки.

И да, чистые строки в качестве ключей для таблиц из 20 тысяч слов работают отлично. Остаюсь с ними)