Hash.ulam

enum TKeyAgain { kaEnable, kaException, kaSkip, kaOverwrite };

class HashTable<K,V>
{
public:
struct HashItem{
  uint hash;
  K key;
  V value;
  HashItem *next;
}

private:
  unit FSize;
  unit FCapacity
  HashItem *[]FTab;
  instantiation uint FHashFunc(K key);
public:
  TKeyAgain KeyAgain;
  HashTable(uint ACapacity=256);
  ~HashTable();
  void Clear();
}


instantiation<K is TValue> uint FHashFunc(K key);
{
   return H(&key, sizeof(key));
}

instantiation<K is TArray> uint FHashFunc(K key);
{
   return H(&key[], Length(key)*sizeof(key[]));
}


HashTable::Clear()
{
 for (int i=0; i<FCapacity; ++)
 {
    HashItem* item := FTab[i];
    while (item != null)
    {
      HashItem* p = item;
      item = item.next;
      delete p;
    }
 }
}

HashTable::HashTable(uint ACapacity=256)
{
  KeyAgain = kaEnable;
  SetLength(FTab, FCapacity);
}

HashTable::~HashTable()
{
   Clear();
}


uint H(byte*p, uint ByteCount: LongWord);
{
  result = 0xFFFFFFFF;
  if (ByteCount > 0)
    for (int i = 0; i<ByteCount; i++)
    {
      // new processors fast multiplies by constant
      result = (result ^ p*) * 134775813 + 1;
      p++;
    }
}

void HashTable::Put(K key, V value)
{
  uint hash := FHashFunc(key);
  int bucketIdx := hash % Capacity;
  HashItem* item;
  new item;
  item.hash = hash;
  item.key = key;
  item.value = value;
  item.next = FTab[bucketIdx];
  FTab[bucketIdx] = item;
}

bool HashTable::RemoveKey(K key)
{
  result = false;
  uint hash = FHashFunc(key);
  int bucketIdx = hash % Capacity;
  HashItem* item = FTab[bucketIdx];
  HashItem* prevItem = null;
  while (item != null)
  {
    if ((item.hash == hash) && (item.key == key))
    {
      HashItem* nextItem = item.next;
      if (prevItem==null)
        FTab[bucketIdx] = item.next;
      else
        prevItem.next = item.next;
      delete item;
      item = nextItem;
      result = true;
    }
    else
    {
      prevItem = item;
      item = item.next;
    }
  }
  if (result) FSize--;
  item = FTab[bucketIdx];
  while (item != null)
  {
    Assert(item.key != key);
    item = item.next;
  }
}

HashItem* HashTable::Get(K key)
{
  uint hash = FHashFunc(key);
  bucketIdx := hash % Capacity;
  result := FTab[bucketIdx];
  while (result != nil)
  {
    if ((result.hash == hash) && (result.key == key))
      return;
    result := result.next;
  }
}

HashItem* HashTableII::GetPrior(HashItem* item)
{
  uint hash = item.hash;
  K key = item.key;
  result = item.next;
  while (result != nil)
  {
    if (result.hash == hash) and (result.key == key)
      return;
    result = result.next;
  }
}
---------------------------

HashTable<string,string> hashTable = new HashTable()
hashTable.Put("abc","def");
hashTable.Put("123","456");
HashTable<string,string>.HashItem *item = hashTable.Get("abc");