11
\$\begingroup\$

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

public class HashTable<T, TU>
    {
        private LinkedList<Tuple<T, TU>>[] _items;
        private int _fillFactor = 3;
        private int _size;

        public HashTable()
        {
            _items = new LinkedList<Tuple<T, TU>>[4];
        }

        public void Add(T key, TU value)
        {
            var pos = GetPosition(key, _items.Length);
            if (_items[pos] == null)
            {
                _items[pos] = new LinkedList<Tuple<T, TU>>();
            }
            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<Tuple<T, TU>>();
            }
            _items[pos].AddFirst(new Tuple<T, TU>(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<Tuple<T, TU>>[_items.Length * 2];
            foreach (var item in _items.Where(x=>x != null))
            {
                foreach (var value in item)
                {
                    var pos = GetPosition(value.Item1, newItems.Length);
                    if (newItems[pos] == null)
                    {
                        newItems[pos] = new LinkedList<Tuple<T, TU>>();
                    }
                    newItems[pos].AddFirst(new Tuple<T, TU>(value.Item1, value.Item2));
                }
            }
            _items = newItems;
        }

        private int GetPosition(T key, int length)
        {
            var hash = key.GetHashCode();
            var pos = Math.Abs(hash % length);
            return pos;
        }

        private bool NeedToGrow()
        {
            return _size >= _fillFactor;
        }
    }
\$\endgroup\$
  • 7
    \$\begingroup\$ Hash tables are not built in a vacuum; they are intended for particular usage patterns. Can you describe a bit more about your goals for this hash table? It is hard to criticize something when you don't know what it is for. For example, is it intended to be a map, or a cache? Is it intended to be threadsafe? Is it intended to be robust and performant even when extremely large amounts of data are inserted? Or removed? Are there particular patterns to the insertions and removals? Do we know that the data is from a trustworthy source, or might it be hostile? And so on. \$\endgroup\$ – Eric Lippert Apr 20 '16 at 16:30
  • 1
    \$\begingroup\$ Great questions, and really, I was just making one to go over in my head how they are built at a core level because I haven't done it in a while :) Wasn't worrying about threading whatsoever in this case. I was treating this more as just a map. \$\endgroup\$ – user103053 Apr 20 '16 at 17:45
14
\$\begingroup\$

A few small points:

public class HashTable<T, TU>

Use more mnemonic names, like TKey, TValue here.

public class HashTable<T, TU>

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<T, TU>

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<Tuple<T, TU>>[4];

Why 4?

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

Throw more specific exceptions.

        if (_items[pos] == null)
        {
            _items[pos] = new LinkedList<Tuple<T, TU>>();
        }
        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<Tuple<T, TU>>[_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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Awesome points (mine plus a couple extra good ones!) - quick question, would a KeyValuePair<TKey,Tvalue> struct not be a better choice than a Tuple<T1,T2> class here? \$\endgroup\$ – Mathieu Guindon Apr 20 '16 at 16:44
  • \$\begingroup\$ @Mat'sMug: Good one, yes. \$\endgroup\$ – Eric Lippert Apr 20 '16 at 16:47
  • \$\begingroup\$ Eric, these are awesome tips as well. I actually thought about re-hashing on removes as well, I wasn't sure if that was something I should do. I think I may add this in because I definitely did not want to make the assumption that this would only grow. Thank you! \$\endgroup\$ – user103053 Apr 20 '16 at 17:48
  • 1
    \$\begingroup\$ Here is the source for Dictionary<TKey,TValue> that was referenced: referencesource.microsoft.com/#mscorlib/system/collections/… \$\endgroup\$ – Zack Apr 20 '16 at 18:33
6
\$\begingroup\$
public class HashTable<T, TU>

Convention for naming generic type parameters, is to either start them with the letter T (e.g. TKey, TValue), or to name the first one T, and the second one U (more parameters than that, go with TMeaningfulName instead). TU looks like a combination of the two guidelines, minus the "meaningful name" part.

I would warmly recommend renaming them TKey and TValue, so this:

public void Add(T key, TU value)

Could read as pleasantly as this:

public void Add(TKey key, TValue value)

I'm not sure why you went with a Tuple<TKey, TValue> class, when a KeyValuePair<TKey,TValue> struct would have been more appropriate, at least at first glance (it's good enough for a Dictionary, right?). It would have made this:

if (_items[pos].Any(x=>x.Item1.Equals(key)))

Read like this instead:

if (_items[pos].Any(item => item.Key.Equals(key)))

Notice the whitespace around the => lambda operator, and the descriptive identifier, together with the more meaningful KeyValuePair.Key (vs. Tuple.Item1) make it much easier on the eye.


This is a red flag:

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

Don't throw System.Exception. Throw the most meaningful existing exception instead, or make your own. I believe an ArgumentException would be perfect here, since that's that Dictionary throws when you try to add a duplicate key.

Might as well check for a null key as well, and throw an ArgumentNullException there.

Same here:

throw new Exception("Key does not exist in HashTable.");

Throw a KeyNotFoundException instead.

\$\endgroup\$
  • \$\begingroup\$ Thank you so much! These are awesome tips. The KeyValuePair one especially. Do you think the logic looks alright? \$\endgroup\$ – user103053 Apr 20 '16 at 17:46
  • \$\begingroup\$ @Scott Eric's answer highlights what I'd deem important issues with removing items and resizing. Other than that, not much to add ;-) \$\endgroup\$ – Mathieu Guindon Apr 20 '16 at 17:49
4
\$\begingroup\$

It looks fine for what it is. You would expect a HashTable to implement some of the collections interfaces like IEnumerable, so it's definitely incomplete. There are really only two things I might change.

  • I think you're misusing the term "fill factor" here, the variable with that name acts more like max capacity.
  • In the Add function, I wouldn't increment _size until you've successfully inserted the item. I don't see how the rehashing could fail, but I would take the paranoid approach and not increment until the work has been done. That does mean that NeedToGrow uses the current size.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy