Описание функций работы с hash-массивами

Hash-массив - это структура, позволяющая хранить произвольные данные с доступом по ключу. Обычный массив можно рассматривать как частный случай hash-массива, ключами которого являются последовательные целые числа. Современные версии Лиспа (в частности, Common Lisp) имеют в своем составе средства работы с hash-массивами. Поэтому разработчик принял решение реализовать hash-массивы и в составе HomeLisp.

Работа с hash-массивами в HomeLisp отличается от схемы работы с hash-массивами в Common Lisp двумя моментами.

В HomeLisp манипулирование данными, хранящимися в hash-массивах, полностью инкапсулировано в соответствующих функциях (в отличие от Common Lisp, где для помещения даных в hash-массив используется функция SETF).

В HomeLisp функции занесения и извлечения элементов по ключу возвращают списки из двух элементов, в которых второй элемент есть T (признак успеха) или Nil (признак неудачи). В Common Lisp эти функции возвращают два значения (возврат множества значений в HomeLisp не поддерживается).

Реализация hash-массивов, описанная ниже, есть просто лисповская обертка для свойств и методов известного объекта DICTIONARY, входящего в состав библиотеки SCRRUN.DLL.

Все описываемые ниже функции реализованы только в 13-й редакции ядра HomeLisp и принадлежат к типу SUBR.

Имя функции К-во аргументов Тип аргументов Выполняемое действие
HASHCLEAR   1 HASH Очищает hash-массив
HASHCOUNT   1 HASH Возвращает число элементов hash-массива
HASHCREATE   1 ATOM Создает hash-массив
HASHDESTROY   1 HASH Уничтожает hash-массив
HASHERASE   2 1 - HASH; 2 - ANY Удаляет элемент hash-массива c заданным ключом
HASHGET   2 1 - HASH; 2 - ANY Возвращает элемент hash-массива с заданным ключом
HASHKEYEXIST   2 1 - HASH; 2 - ANY Проверяет существование в hash-массиве элемента с заданным ключом
HASHMAP   2 1 - HASH; 2 - FUNCT Применяет функцию, заданную вторым аргументом к каждому элементу hash-массива
HASHPUT   3 1 - HASH; 2,3 - ANY Заносит элемент с заданным ключом в hash-массив
HASHCLEAR  

Функция HASHCLEAR принимает один параметр - идентификатор hash-массива (атом). Hash-массив очищается, но не уничтожается. Вот развернутый пример:


(hashCreate 'h)

==> h

(hashPut 'h 'k-1 'v-1)

==> (v-1 T)

(proplist 'h)

==> (HASH COUNTER 1 HASHHANDLE 1)

(hashClear 'h)

==> h

(proplist 'h)

==> (HASH COUNTER 0 HASHHANDLE 1)

Создается hash-массив. В него заносится атом v-1 с ключом k-1. Список свойств атома h показывает, что hash-массив содержит один элемент. Далее hash-массив очищается. Повторный запрос списка свойств показывает, что хотя счетчик элементов (индикатор COUNTER) обнулился, но сам hash-массив не уничтожился.

HASHCOUNT  

Функция HASHCOUNT принимает один параметр - идентификатор hash-массива и возвращает количество элементов, содержащихся в hash-массиве. В принципе, количество элементов hash-массива можно получить из списка свойств идентификатора массива, использование HASHCOUNT несколько проще. Рассмотрим пример:


(hashcount 'h)

Символ h - не HASH-таблица
==> ERRSTATE

(hashCreate 'h)

==> h

(hashcount 'h)

==> 0

(hashput 'h 'k 'v)

==> (v T)

(hashcount 'h)

==> 1

(hashput 'h 'kk 'vv)

==> (vv T)

(hashcount 'h)

==> 2

(proplist 'h)

==> (HASH COUNTER 2 HASHHANDLE 1)

Сначала делается попытка применить функция HASHCOUNT к "чистому" атому (не являющемуся идентификаторм hash-массива). Эта попытка, естественно, завершается ошибкой.

Далее создается hash-массив. Запрос количества элементов показывает, что массив пуст. Далее в массив заносится значение v с ключом k. Теперь вызов HASHCOUNT показывает, что в массиве содержится один элемент. Добавление еще одного элемента vv с ключом kk и последующий вызов HASHCOUNT показывает, что элементов стало два. В этом можно убедиться, запросив список свойств идентификаторов hash-массива.

HASHCREATE  

Функция HASHCREATE создает hash-массив. Она ожидает один параметр-атом. Желательно, чтобы этот атом был "чистым" (имел пустой список свойств). Если же атом-параметр содержит в списке свойств какие-либо стандартные индикаторы (APVAL,FIXED, STRING и т.д.), то возбуждается состояние ошибки. В случае, когда атом-параметр содержит список свойств без стандартных индикаторов, то этот список уничтожается (заменяется на другой); при этом выдается соответствующее сообщение. И, наконец, если атом-параметр уже является идентификаторм hash-массива, то возбуждается состояние ошибки.

Если вызов HASHCREATE завершается успешно, то атом-параметр становится идентификатором hash-массива и у атома-параметра создается защищенный список свойств.В этом списке свойств содержится стандартный флаг HASH и два индикатора - COUNTER и HASHHANDLE. Под индикатором COUNTER хранится текущее количество элементов hash-массива, а под индикатором HASHHANDLE - внутренний номер hash-массива.

Попытка прямой модификации списка свойств (посредством PUTPROP или SPROPL) вызовет ошибку защиты.

Все это выглядит следующим образом:


(hashCreate T)

hashCreate: недопустимый флаг у первого аргумента
==> ERRSTATE

(hashCreate "a")

hashCreate: недопустимый флаг у первого аргумента
==> ERRSTATE

(putprop 'h 'ff 'zz)

==> h

(proplist 'h)

==> (ff zz)

(hashCreate 'h)

==> h
hashCreate: список свойств атома h будет очищен

(proplist 'h)

==> (HASH COUNTER 0 HASHHANDLE 1)

(hashCreate 'h)

HASH h уже существует
==> ERRSTATE

(putprop 'h 'counter 8)

SPROPL: Недопустимая модификация списка свойств
==> ERRSTATE

(spropl 'h '(1 2 3))

SPROPL: Недопустимая модификация списка свойств
==> ERRSTATE

Попытка превратить в hash-массив встроенную константу T или строку завершается ошибкой. Далее у атома h создается список свойств (ff zz), а затем делается попытка превратить этот атом в идентификатор hash-массива. Попытка оказывается успешной, но выдается предупреждающее сообщение об очистке списка свойств атома h. А вот повторный вызов HASHCREATE завершается ошибкой.

Попытка любой "ручной" модификации списка свойств идентификатора hash-массива завершается ошибкой.

HASHDESTROY  

Функция HASHDESTROY ожидает на входе атом-идентификатор hash-массива. Функция уничтожает заданный hash-массив, при этом список свойств атома-идентификатора очищается. При успешном завершении функция возвращает T.


(hashCreate 'h)

==> h

(HashPut 'h '(1 2 3) (sumlist '(1 2 3)))

==> (6 T)

(HashPut 'h '(4 5 6) (sumlist '(4 5 6)))

==> (15 T)

(hashCount 'h)

==> 2

(hashDestroy 'h)

==> T

(hashCount 'h)

Символ h - не HASH-таблица
==> ERRSTATE

(proplist 'h)

==> NIL

Здесь создается hash-массив h и в него заносятся два значения. Запрос количества элементов показывает наличие двух элементов. Далее массив уничтожается. Попытка получить количество элементов теперь вызывает ошибку. И это неудивительно - после вызова HASDESTROY атом h уже не представляет hash-массив (и его список свойств пуст).

HASHERASE  

Функция HASHERASE уничтожает элемент hash-массива. На вход функции требуется подать два параметра: идентификатор has-массива и ключ удаляемого элемента. Если элемент с заданным ключом существует, то он удаляется из hash-массива, а функция HASHERASE возвращает T. Если же элемента с заданным ключом в hash-массиве нет, то функция вернет Nil.

Вот пример работы HASHERASE:


(hashcreate 'h)

==> h

(hashput 'h 'k-1 '(1 2 3 4))

==> ((1 2 3 4) T)

(hashput 'h 'k-2 '(5 6 7 8))

==> ((5 6 7 8) T)

(hasherase 'h 'k-1)

==> T

(hashCount 'h)

==> 1

(hasherase 'h 'k-1)

==> NIL

Создается hash-массив и в него заносятся два элемента с ключами k-1 и k-2. После этого удаляется элемент с ключом k-1. Количество элементов в hash-массиве становится равным 1. Попытка повторного удаления элемента с тем же ключом завершается неудачно (функция возвращает Nil).

HASHGET  

Функция HASHGET позволяет получить значение элемента hash-массива по ключу. Функция ожидает два параметра: идентификатор hash-массива и ключ. При успехе функция возвращает список из двух элементов, первым из которых будет значение элемента , а вторым - атом T. Если ключ не найден в hash-массиве, функция вернет список (Nil Nil).

Ниже приведен пример использования функции HASHGET:


(hashCreate 'h)

==> h

(hashPut 'h 'k_1 111)

==> (111 T)

(hashPut 'h 'k_2 222)

==> (111 T)

(hashPut 'h 'k_3 333)

==> (333 T)

(hashGet 'h 'k_2)

==> (222 T)

(hashGet 'h 'k_7)

==> (NIL NIL)

Создается hash-массив h. В него записываются значения 111, 222 и 333 с ключами k_1,k_2 и k_3 соответственно. Затем из hash-массива извлекается значение, ассоциированное с ключом k_2. Результат - список (222 T). Поскольку его второй элемент есть T, то первый элемент результата есть искомое значение. А вот попытка извлечь значение, ассоциированное с ключом h_7 оканчивается неудачно - второй элемент результата есть Nil (элемент с ключом h_7 не существует).

HASHKEYEXIST  

Функция HASHKEYEXIST проверяет наличие в hash-массиве значения, ассоциированного с заданным ключом. Функция принимает два параметра - идентификатор hash-массива и ключ (произвольная форма). Если в hash-массиве, заданным первым параметром имеется элемент с ключом, заданным вторым параметром, то функция HASHKEYEXIST вернет T, если же элемента нет - функция вернет Nil.

Вот иллюстрация сказанного выше:


(hashCreate 'h)

==> h

(hashPut 'h 'k-1 '(1 2 3 4))

==> ((1 2 3 4) T)

(hashPut 'h 'k-2 '(1 2 3 4))

==> ((1 2 3 4) T)

(hashKeyExist 'h 'k-1)

==> T

(hashKeyExist 'h 'k-2)

==> T

(hashKeyExist 'h 'k-3)

==> NIL

(hashKeyExist 'g 'k-3)

Символ g - не HASH-таблица
==> ERRSTATE

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

HASHMAP  

Функция HASHMAP принимает два параметра - идентификатор hash-массива (атом) и функциональное выражение, задающее функцию с двумя параметрами. HASMAP применяет эту функцию последовательно ко всем элементам hash-массива, заданного первым параметром. Первым параметром вызова подставляется ключ очередного элемента, а вторым - его значение. После "пробега" всего hash-массива функция HASHMAP возвращает число элементов исходного hash-массива.

Вот как это выглядит:


(hashCreate 'h)

==> h

(hashPut 'h 'a1 '(1 2 3))

==> ((1 2 3) T)

(hashPut 'h 'a2 '(4 5 6))

==> ((4 5 6) T)

(hashPut 'h 'a3 '(7 8 9))

==> ((7 8 9) T)

(hashPut 'h 'a4 '(10 11 12))

==> ((10 11 12) T)

(hashPut 'h 'a5 '(13 14 15))

==> ((13 14 15) T)

(hashPut 'h 'a6 '(16 17 18))

==> ((16 17 18) T)

(hashMap 'h '(lambda (k v) (printline (list k v))))
(a1 (1 2 3))
(a2 (4 5 6))
(a3 (7 8 9))
(a4 (10 11 12))
(a5 (13 14 15))
(a6 (16 17 18))

==> 6

(hashMap 'h '(lambda (k v) (printline (list k (sumlist v)))))
(a1 6)
(a2 15)
(a3 24)
(a4 33)
(a5 42)
(a6 51)

==> 6

(hashClear 'h)

==> h

(hashMap 'h '(lambda (k v) (printline (list k v))))

==> 0

Здесь создается hash-массив и в него заносятся трехэлементые числовые списки с ключами a1 - a6. Первый вызов HASHMAP просто распечатывает пары "ключ - значение". Второй вызов распечатывает пары "ключ - сумма элементов значения". Далее hash-массив очищается. Попытка мапировать функцию на пустой hash-массив завершается без ошибки, просто число обработанных элементов оказывается равным нулю.

HASHPUT  

Функция HASHPUT обеспечивает занесение элементов в hash-массив. Функция принимает три параметра: идентификатор hash-массива (атом), ключ (произвольная форма) и значение (произвольная форма). Функция возвращает список из двух элементов. Первый элемент списка-результата есть значение заносимого элемента. Второй элемент может быть атомом T (занесение успешно) или Nil (занесение неуспешно).

Вот как выглядит работа HASHPUT:

(hashCreate 'h)

==> h

(hashPut 'h 'a1 'v1)

==> (v1 T)

(hashPut 'h 'a2 'v2)

==> (v2 T)

(hashPut 'h 'a1 'v3)

==> (v3 NIL)

Видно, что попытка повторно занести элемент с ключом v1 завершается неудачно.

Работа с hash-массивами имеет одну тонкость, проявляющуюся в том случае, когда ключ элемента не есть атом. Рассмотрим следущий пример:

(hashCreate 'h)

==> h

(hashPut 'h '(1 2 3) '(x y z))

==> ((x y z) T)

(hashPut 'h '(4 5 6) '(a b c))

==> ((a b c) T)

(hashCount 'h)

==> 2

(hashMap 'h '(lambda (k v) (printline (list k v))))

((1 2 3) (x y z))
((4 5 6) (a b c))

==> 2

(hashGet 'h '(1 2 3))

==> (NIL NIL)

(hashKeyExist 'h '(1 2 3))

==> NIL
Сначала ничего не предвещает неприятностей - создается hash-массив и в него заносятся два значения с ключами, представляющими собой трехэлементные списки. Вызов HASHCOUNT показывает, что в hash-массиве находятся два элемента. Вызов HASHMAP позволяет убедиться, что элементы "живы". А попытка получить элемент по ключу (1 2 3) завершается неудачно. Вызов HASHKEYEXIST тоже показывает, что элемента с ключом (1 2 3) не существует. В чем же дело?

Дело в механизме сравнения ключей при поиске в hash-массиве. Можно считать, что при сравнении ключей используется функция EQL. Когда происходит запрос существования с ключом (1 2 3), список (1 2 3) из вызова HASHGET/HASHKEYEXIST не есть тот же самый список, что и список из вызова HASHPUT.

Если использовать в качестве ключей атомы, то проблема не возникает. И понятно, почему: ведь атомы уникальны. Любая ссылка на атом a ссылвется на один и тот же атом.

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

(hashCreate 'h)

==> h

(setq k-1 '(1 2 3))

==> (1 2 3)
Создана глобальная переменная k-1

(setq k-2 '(4 5 6))

==> (4 5 6)
Создана глобальная переменная k-2

(hashPut 'h k-1 '(x y z))

==> ((x y z) T)

(hashPut 'h k-2 '(a b c))

==> ((a b c) T)

(hashMap 'h '(lambda (k v) (printline (list k v))))

((1 2 3) (x y z))
((4 5 6) (a b c))

==> 2

(hashGet 'h k-1)

==> ((x y z) T)

(hashKeyExist 'h k-1) 

==> T

Можно убедиться, что теперь поведение всех функций стало предсказуемым. Важно подчеркнуть, что в вышеприведенном примере ключи есть именно списки, а не атомы k-1 и k-2. Поскольку все функции манипулирования hash-массивами принадлежат классу SUBR, то при их вычислении значения символов-аргументов k-1 и k-2 будут заменены их значениями (списками (1 2 3) и (4 5 6)). Причем, при вызовах всех функций с аргументом k-1 этот символ будет заменен одним и тем же списком.

В Common Lisp дело обстоит сходным образом, но там есть возможность управлять механизмом сравнения ключей, который можно задать при создании hash-массива. В HomeLisp эта возможность пока не реализована...