Simple C# HashTable Implementation

Haven't put one of these together since college. How does this look overall?

```
public class HashTable
{
private LinkedList>[] _items;
private int _fillFactor = 3;
private int _size;

public HashTable()
{
_items = new LinkedList>[4];
}

public void Add(T key, TU value)
{
var pos = GetPosition(key, _items.Length);
if (_items[pos] == null)
{
_items[pos] = new LinkedList>();
}
if (_items[pos].Any(x=>x.Item1.Equals(key)))
{
throw new Exception("Duplicate key, cannot insert.");
}
_size++;
if (NeedToGrow())
{
GrowAndReHash();
}
pos = GetPosition(key, _items.Length);
if (_items[pos] == null)
{
_items[pos] = new LinkedList>();
}
_items[pos].AddFirst(new Tuple(key, value));
}

public void Remove(T key)
{
var pos = GetPosition(key, _items.Length);
if (_items[pos] != null)
{
var objToRemove = _items[pos].FirstOrDefault(item => item.Item1.Equals(key));
if (objToRemove == null) return;
_items[pos].Remove(objToRemove);
_size--;
}
else
{
throw new Exception("Value not in HashTable.");
}
}

public TU Get(T key)
{
var pos = GetPosition(key, _items.Length);
foreach (var item in _items[pos].Where(item => item.Item1.Equals(key)))
{
return item.Item2;
}
throw new Exception("Key does not exist in HashTable.");
}

private void GrowAndReHash()
{
_fillFactor *= 2;
var newItems = new LinkedList>[_items.Length * 2];
for

A few small points:

public class HashTable

Use more mnemonic names, like TKey, TValue here.

public class HashTable

The name indicates how the class is implemented; name it after what it does logically. This is a map, or a dictionary, or a key-value store, or whatever you want to call it. That it is a hash table is a mechanism; name classes after their semantics.

public class HashTable

I would expect a map to implement appropriate generic interfaces IDictionary, IEnumerable, ICollection, and so on.

private int _fillFactor = 3;

Why 3? Explain to the reader what is going on here.

_items = new LinkedList>[4];

Why 4?

throw new Exception("Duplicate key, cannot insert.");

Throw more specific exceptions.

if (_items[pos] == null)
        {
            _items[pos] = new LinkedList>();
        }
        if (_items[pos].Any(x=>x.Item1.Equals(key)))
        {

That could be an else if.

if (NeedToGrow())
        {
            GrowAndReHash();
        }

You never call NeedToGrow and GrowAndRehash separately, which indicates to me that they are the same thing. You could make one method called GrowAndRehashIfNecessary().

public TU Get(T key)
public void Add(T key, TU value)

You might also implement an indexer.

var newItems = new LinkedList>[_items.Length * 2];

The number of array slots will always be a power of two, and therefore you are taking the bottom n bits of the hash as your hash key. Depending on how the data is distributed and the quality of the hash codes given to you, that might lead to a fair number of collisions. You'd want to try this out on real data and see how it goes.

public void Add(T key, TU value)
public void Remove(T key)

Add resizes and rehashes if the table gets too full, but Remove does not resize and rehash if the table gets too empty. Apparently you have made the implicit and undocumented design decision that many adds are more likely than many removes, and that in the case where many removes happen, it is OK to waste memory. Was that decision intentional, or an accident?

Finally, consider studying the implementation of the Dictionary type; the .NET sources are available and the dictionary hash table implementation is entertaining reading. You get a sense of how feature-complete and robust these things really have to be to be a workhorse of the base class libraries.

StackExchange Code Review Q#126247, answer score: 14