Psst.. new poll here.
Psst.. new forums here.
Microsoft is blocking us again (TY IP Reputation!) so just use oauth login instead. :)
Paste
Pasted as C# by chatte ( 17 years ago )
using System;
namespace HashTable
{
public enum CollisionResolutionType
{
linearProbing,
doubleHashing,
quadraticProbing
}
public class HashtableWithOpenAddressing<K, V> : Hashtable<K, V>
{
private const int INITIAL_SIZE = 10;
private const double MAX_LOAD_FACTOR = 0.75;
private const double TABLE_SIZE_DELTA = 1.5;
private const int CONST1 = 0;
private const int CONST2 = 1;
private readonly CollisionResolutionType type;
private readonly HashFunction<K> hashFunction;
private readonly HashFunction<K> secondHashFunction;
private Node[] data = new Node[INITIAL_SIZE];
private int size = 0;
private class Node
{
public K key;
public V value;
public Node(K key, V value)
{
this.key = key;
this.value = value;
}
}
public HashtableWithOpenAddressing(HashFunction<K> function, CollisionResolutionType collisionResolutionType,
HashFunction<K> func)
{
type = collisionResolutionType;
hashFunction = function;
secondHashFunction = func;
}
private int LoadFactor
{
get { return size/data.Length; }
}
private int FindSlot(K key)
{
switch (type)
{
case CollisionResolutionType.linearProbing:
return LinearFindSlot(hashFunction.Hash(key, data.Length));
case CollisionResolutionType.doubleHashing:
return DoubleFindSlot(hashFunction.Hash(key, data.Length), secondHashFunction.Hash(key, data.Length));
case CollisionResolutionType.quadraticProbing:
return QuadraticFindSlot(hashFunction.Hash(key, data.Length));
default:
throw new ArgumentException();
}
}
private bool PlaceFound(int place)
{
K key = data[place].key;
return data[place] == null || data[place].key.Equals(key);
}
private int LinearFindSlot (int initialHash)
{
while (!PlaceFound(initialHash))
initialHash = (initialHash + 1) % data.Length;
return initialHash;
}
private int DoubleFindSlot(int initialHash, int secondHash)
{
while (!PlaceFound(initialHash))
initialHash = (initialHash + secondHash) % data.Length;
return initialHash;
}
private int QuadraticFindSlot(int initialHash)
{
int h = initialHash;
for (int i = 0; !PlaceFound(initialHash); i++)
initialHash = (h + i*CONST1 + i*i*CONST2) % data.Length;
return initialHash;
}
public void RehashIfNeccessary()
{
if (LoadFactor > MAX_LOAD_FACTOR)
{
int newSize = (int) (size*TABLE_SIZE_DELTA);
Node[] oldData = data;
data = new Node[newSize];
foreach (Node node in oldData)
{
int newHash = hashFunction.Hash(node.key, newSize);
if (data[newHash] != null && data[newHash] != node)
newHash = FindSlot(node.key);
data[newHash] = node;
}
}/*switch (type) { case CollisionResolutionType.linearProbing:foreach (Node node in data) {int newHash = hashFunction.Hash(node.key, newSize); newData[newHash] = node; } break; case CollisionResolutionType.quadraticProbing: foreach(Node node in data) { int newHash = hashFunction.Hash() } break; }*/
}
public bool Remove(K key)
{
int i = FindSlot(key);
if (data[i] == null)
return false;
int j = i;
while (true)
{
j = (j + 1)?ta.Length;
if (data[j] == null) break;
int k = hashFunction.Hash(data[j].key, data.Length);
if ((j > i && (k <= i || k > j)) || (j < i && (k <= i || k > j)))
data[i] = data[j];
i = j;
}
data[i] = null;
return true;
}
public void Put(K key, V value)
{
int index = FindSlot(key);
if (data[index] == null)
{
data[index] = new Node(key, value);
}
else
{
data[index].key = key;
data[index].value = value;
size++;
RehashIfNeccessary();
}
}
public V Get(K key)
{
int index = FindSlot(key);
if (data[index] == null)
throw new ArgumentException("Cannot find element with key " + key);
return data[index].value;
}
}
}
Revise this Paste