
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[34.238.189.240] |
![]() |
|
Сообщ.
#1
,
|
|
|
Допустим у нас есть некоторый словарь:
![]() ![]() aaasdf dfgbv sdfdsf ghghhj sdfgf asdser Нам необходимо проверить входит ли слово: asdser в этот словарь. Способ №1. Просматриваем ВЕСЬ словарь и сравниваем это слово со всеми словами. На все это у нас уйдет 6 проверок. Способ №2. Будем хранить эти слова в специальной таблице (хеш-таблице). Каждому столбику сопоставим букву. И получим следующую таблицу (некоторые буквы опущены): ![]() ![]() a … d … g … s aaasdf dfgbv ghghhj sdfdsf asdser sdfgf Нетрудно заметить, что в столбце ‘a’ мы храним все слова начинающиеся с буквы ‘a’ и т.д. И теперь для того, чтобы найти слово asdser нам необходимо просмотреть столбик ‘a’ , а это уже 2 сравнения. P.S. В данном примере мы использовали хеширование по первой букве, но есть уйма других способов хеширования, например по контрольной сумме. Но это уже другая тема. |
Сообщ.
#2
,
|
|
|
Продолжаю эту интересную тему.
Итак, существует громадное количество hash-функций. Для чисел это может быть сумма цифр, а для строк - сумма кодов символов, умноженных на их позицию в строке (например, для строки 'Вася' hash-функция будет выглядеть так: Ord('В') * 1 + Ord('а') * 2 + Ord('с') * 3 + Ord('я') * 4). Вот модуль, в котором реализованы простейшие операции хеширования. Идея такая: создается несколько независимых групп (точнее, списков), в которые будут добавляться элементы. Hash-функция будет определять, в какой список следует добавлять элемент. Реализовано все через ООП. Замечание: класс THash надо наследовать! В нем описана абстрактная функция HashFunction, которую надо "перекрыть". ![]() ![]() { Hash operations for Borland Pascal 7.0 } Unit Hash; Interface Const HashGroups = 1000; Type HashElement = Integer; HashKey = String; PList = ^TList; TList = Record Key: HashKey; Value: HashElement; Removed: Boolean; Next: PList; End; THash = Object Data: Array[1..HashGroups] Of PList; Public Constructor Init; Function HashFunction(Key:HashKey):Longint; Virtual;{Must be overrided} Procedure AddValue(Key:HashKey;Value:HashElement); Function FindValue(Key:HashKey;Var Found:Boolean):HashElement; Procedure DeleteValue(Key:HashKey); Destructor Done; Virtual; Private Procedure AddToList(P:PList;Key:HashKey;Value:HashElement); Procedure DeleteGroup(P:PList); End; Implementation Uses Objects; Constructor THash.Init; Var I:Integer; Begin For I:=1 To HashGroups Do Data[I]:=Nil; End; Destructor THash.Done; Var I:Integer; Begin For I:=1 To HashGroups Do DeleteGroup(Data[I]); End; Function THash.HashFunction(Key:HashKey):Longint; Begin Abstract; End; Procedure THash.AddValue(Key:HashKey;Value:HashElement); Var B:Boolean; Begin FindValue(Key,B); If B Then Exit; AddToList(Data[HashFunction(Key)],Key,Value); End; Procedure THash.AddToList(P:PList;Key:HashKey;Value:HashElement); Var N,O:PList; Begin While O <> Nil Do Begin If (O^.Key = Key) And (O^.Removed) Then Begin O^.Removed:=False; O^.Value:=Value; Exit; End; O:=O^.Next; End; New(N); N^.Key:=Key; N^.Value:=Value; N^.Next:=P; N^.Removed:=False; Data[HashFunction(Key)]:=N; End; Procedure THash.DeleteGroup(P:PList); Begin If P = Nil Then Exit; If P^.Next = Nil Then Dispose(P) Else DeleteGroup(P^.Next); End; Function THash.FindValue(Key:HashKey;Var Found:Boolean):HashElement; Var Func: Longint; P:PList; Begin Func:=HashFunction(Key); P:=Data[Func]; While P <> Nil Do Begin If (Key = P^.Key) And (Not P^.Removed) Then Begin Found:=True; FindValue:=P^.Value; Exit; End; P:=P^.Next; End; Found:=False; End; Procedure THash.DeleteValue(Key:HashKey); Var P,O:PList; Func:Longint; Begin Func:=HashFunction(Key); P:=Data[Func]; While P <> Nil Do Begin If Key = P^.Key Then P^.Removed:=True; P:=P^.Next; End; End; End. Вот пример использования модуля (создается объект, перекрывается метод HashFunction): ![]() ![]() Uses Hash; Type TMyHash = Object(THash) Function HashFunction(Key:HashKey):Longint; Virtual; End; Function TMyHash.HashFunction(Key:HashKey):Longint; Var I:Integer; Sum:Integer; Begin Sum:=0; For I:=1 To Length(Key) Do Sum:=Sum + (Ord(Key[I]) * I); HashFunction:=(Sum Mod HashGroups) + 1; End; Var H:TMyHash; B:Boolean; V:HashElement; Begin Writeln('----'); Writeln(MemAvail); H.Init; H.AddValue('chislo',5); H.DeleteValue('chislo1'); V:=H.FindValue('chislo',B); If B Then Writeln(V) Else Writeln('No element'); H.Done; Writeln(MemAvail); End. |
Сообщ.
#3
,
|
|
|
Хэш на Pascal.
Реализация - готовая лаба, в ней, на мой скромный взгляд, проще разбираться.. Прикреплённый файл ![]() |