adthash.pas.mcp

(* This file is a part of the PascalAdt library, which
   provides commonly used algorithms and data structures for
   the FPC and Delphi compilers.
   
   Copyright (C) 2004, 2005 by Lukasz Czajka
   
   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public License
   as published by the Free Software Foundation; either version 2.1 of
   the License, or (at your option) any later version.
   
   This library is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.
   
   You should have received a copy of the GNU Lesser General Public
   License along with this library; if not, write to the Free Software
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
   02110-1301 USA *)

unit adthash;

{ This unit provides implementations of a hash table (@<THashTable>)
  and of a scatter table (@<TScatterTable>). Scatter tables are
  sometimes called closed hash tables, the first container metioned is
  sometimes also called an open hash table or a chained hash
  table. @<THashTable> uses lists to resolve collisions, whereas
  @<TScatterTable> uses pseudo-random probing technique and keeps all
  items in one array. They both perform all set operations in average
  O(1) time and worst-case O(n). However, for most uses @<THashTable>
  is recommended as it is slightly faster (better constant
  factors). On the other hand, @<TScatterTable> consumes less
  memory. }

interface

uses
   adtcont, adtmem, adthashfunct, adtfunct, adtcontbase, adtdarray, adtiters;

&include adtdefs.inc
   
&_mcp_generic_include(adthash.i)

implementation

uses
   SysUtils, adtutils, adtmsg, adtlog;

const
   { initial FTableSize of THashTable (must be >= htMinTableSize) }
   htInitialTableSize = 6;
   { minimal FTableSize of THashTable }
   htMinTableSize = 3;
   { log2 from the number by which FMaxFillRatio and FMinFillRAtio are
     multiplied }
   htRatioFactor = 7;
   htDefaultMaxFillRatio = 80;
   htDefaultMinFillRatio = 10;
   
   stRatioFactor = htRatioFactor;
   { initial FTableSize of TScatterTable (must be >= stMinTableSize) }
   stInitialTableSize = 6;
   { minimal FTableSize of TScatterTable }
   stMinTableSize = 3;
   { 'magic' values used in the generation of semi-random sequences of
     probes when a collision occurs in TScatterTable }
   stMagicTable : array[3..31] of UnsignedType =
      (3, 3, 5, 3, 3, 29, 17, 9, 5, 83, 27, 43, 3, 45, 9, 39, 39, 9, 5, 3, 33,
       27, 9, 71, 39, 9, 5, 83, 9);
   { value used to mark deleted cells }
   &macro stDeleted
      &_mcp_secondary_special_value
   &endm
   &macro stFree
      &_mcp_special_value
   &endm
   stDefaultMaxFillRatio = 70;
   stDefaultMinFillRatio = 10;
   
&_mcp_generic_include(adthash_impl.i)

end.