1740

Приложение

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

Функция принимает три параметра.

Строку, которую необходимо хешировать.

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

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

Чтобы продемонстрировать использование функции GET HASH VALUE, я реализую новый тип, HASHTABLETYPE, для поддержки хешей в языке PL/SQL. Он очень похож на PL/SQL-таблицу, проиндексированную не числами, а строками типа VARCHAR2. Обычно элементы PL/SQL-таблицы индексируются целыми числами. Новый же тип PL/SQL-таблицы позволяет индексировать элементы строками. Можно объявлять переменные типа HASHTABLETYPE, помещать (GET) и выбирать (PUT) из них данные. Такого рода таблиц можно создать сколько угодно. Вот спецификация соответствующих типов:

tkyte@TKYTE816>create or replace type myScalarType

2 as object

3 (key varchar2(4000) ,

4 val varchar2(4000)

5 ) ;

Type created.

tkyte@TKYTE816> create or replace type myArrayType

2 as varray(10000) of myScalarType;

Type created.

tkyte@TKYTE816> create or replace type hashTableType

2 as object

4 g hash size number,

5 g hash table myArrayType,

6 g collision cnt number, 7

8 static function new(p hash size in number)

9 return hashTableType,

11 member procedure put(p key in varchar2,

12 p val in varchar2),

14 member function get(p key in varchar2)

15 return varchar2, 16

17 member procedure print stats

Пакет DBMS UTILITY 1741

18 );

19 /

Type created.

Интересная особенность реализации состоит в добавлении статической функции-члена NEW. Это позволит создать собственный конструктор. Специального значения имя NEW не имеет. Это не ключевое слово. Функция NEW просто позволяет объявлять данные типа HASHTABLETYPE следующим образом:

declare

l hashTable hashTableType := hashTableType.new(1024) ;

a не как обычно:

declare

l hashTable hashTableType : =hashTableType(1024 , myArrayType(), 0) ;

Я уверен, что первый вариант надежнее и понятнее второго. Второй вариант вызова раскрывает многие детали реализации (например, то, что используется тип массива, имеется переменная G COLLISION CNT, которой надо задавать значение 0, и т.п.). Пользователям знать об этом не обязательно.

Теперь рассмотрим тело объектного типа:

scott@TKYTE816> create or replace type body hashTableType 2 as

4 - Наш более дружественный конструктор.

6 static function new(p hash size in number)

7 return hashTableType

8 is

9 begin

10 return hashTableType(p hash size, myArrayType(), 0) ;

11 end;

13 member procedure put(p key in varchar2, p val in varchar2)

14 is

15 l hash number :=

16 dbms utility.get hash value(p key, 1, g hash size);

17 begin 18

19 if (p key is null)

20 then

21 raise application error(-20001, Пустой ключ не допускается);

22 end if;

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

27 if (l hash > nvl( g hash table.count, 0))

28 then

1742 Приложение

g hash table.extend(l hash-nvl(g hash table.count,0) + l); end if;

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

35 for i in 0 .. 1000

36 loop

3 7 - Если мы собираемся выйти за еделы таблицы,

3 8 - сначала надо добавить новый слот.

3 9 if (g hash table.count <= l hash+i)

40 then

41 g hash table.extend;

42 end if;

Следующий фрагмент реализует действие: если слот не используется или ключ уже находится в этом слоте, использовать и вернуть его. Странной кажется проверка того, пуст ли элемент G HASH TABLE или значение G HASH TABLE(L HASH+I).KEY.

Это показывает, что элемент набора может быть пустым (Null) или может содержать объект с пустыми атрибутами:

if (g hash table(l hash+i) is null OR

nvl(g hash table(l hash+i).key,p key) = p key)

then

g hash table(l hash+i) := myScalarType(p key,p val); return; end if;

46 47 48 49

52 53 54 55

56 5 7

58 59

- Иначе увеличить счетчик количества конфликтов - и перейти к слеющему слоту. g collision cnt := g collision cnt+l; end loop;

Если оказались здесь. Увеличьте ее . raise application error(-2 0 0 01.

значит, таблица слишком мала.

слком много хеш-значений в

-> таблице);

63 64 65

67 68

end;

member function get(p key in varchar2) return varchar2 is

l hash

begin

number := dbms utility.get hash value(p key,

1, g hash size) ;

Если необходимо получить значение, мы обращаемся к элементу индекса, в котором это значение хранится, а в случае возникновения конфликта, просматриваем до 1000