I am trying to implement a hashtable in C#. Here's what I have so far:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace GenericHashMap.hashtable
{
class GenericHashtable<T>
{
private List<Node<T>> array;
private int capacity;
public GenericHashtable(int capacity)
{
this.capacity = capacity;
array = new List<Node<T>>(capacity);
for (int i = 0; i < capacity; i++)
{
array.Insert(i, null);
}
}
public class Node<E>
{
private E info;
private Node<E> next;
public Node(E info, Node<E> next)
{
this.info = info;
this.next = next;
}
public E Info
{
get
{
return this.info;
}
set
{
this.info = value;
}
}
public Node<E> Next
{
get
{
return this.next;
}
set
{
this.next = value;
}
}
}
public bool IsEmpty()
{
if (array.Count == 0)
{
return true;
}
return false;
}
public void Add(T element)
{
int index = Math.Abs(element.GetHashCode() % capacity);
Node<T> ToAdd = new Node<T>(element, null);
Console.WriteLine("index = " + index);
if (array.ElementAt(index) == null)
{
array.Insert(index, ToAdd);
Console.WriteLine("The element " + array.ElementAt(index).Info.ToString() + " was found at index " + index);
}
else
{
Node<T> cursor = array.ElementAt(index);
while (cursor.Next != null)
{
cursor = cursor.Next;
}
if (cursor.Next == null)
{
cursor.Next = ToAdd;
Console.WriteLine("The element " + array.ElementAt(index).Info.ToString() + " was found at index " + index);
}
}
}
public bool Search(T key)
{
int index = Math.Abs(key.GetHashCode() % capacity);
Console.WriteLine("Index = " + index);
Console.WriteLine("The element " + array.ElementAt(index).Info.ToString());
if (array.ElementAt(index) == null)
{
return false;
}
else
{
if (array.ElementAt(index).Equals(key))
{
Console.WriteLine("The element " + key + "exists in the map at index " + index);
return true;
}
else
{
Node<T> cursor = array.ElementAt(index);
while (cursor != null && !(cursor.Info.Equals(key)))
{
cursor = cursor.Next;
}
if (cursor.Info.Equals(key))
{
Console.WriteLine("The " + key + "exists in the map");
return true;
}
}
}
return false;
}
public void PrintElements()
{
for (int i = 0; i < capacity; i++)
{
Node<T> cursor = array.ElementAt(i);
while (cursor != null)
{
Console.WriteLine(cursor.Info.ToString());
cursor = cursor.Next;
}
}
}
}
}
Now, I add the following strings in the table:
GenericHashtable<string> table = new GenericHashtable<string>(11);
table.Add("unu"); -> index 3
table.Add("doi"); -> index 0
table.Add("trei"); -> index 6
table.Add("patru"); -> index 7
table.Add("cinci"); -> index 2
table.Add("sase"); -> index 0
Now, everything's fine, the elements are added. But when I'm trying to search the element "unu" it is not found because it's index is not 3 anymore, it's 5. The index for "trei" is not 6, it's 7... I don't understand why the elements are changing their indexes. I suppose that something is wrong when the elements are added in the Add() method, but I can't figure out myself what. Any answers?
This is the problem, in your Add
method:
array.Insert(index, ToAdd);
Your array
variable isn't actually an array - it's a list. And you're inserting elements into it, rather than just setting the existing element. That will affect all the existing elements which have a later index - increasing their index.
I would suggest using an array instead, and just use the indexers:
private Node<T>[] nodes;
Then:
Node<T> node = nodes[index];
if (node == null)
{
nodes[index] = newNode;
}
...
(There are various other oddities about the code to be honest, but that's the reason for the current problem.)
See more on this question at Stackoverflow