Hashtable
Written by: maffelu , 2009-09-28 11:52:29
Prologue
A hashtable is a collection object that hold data in pairs; key and value. Every value is stored with a key which can be used to extract the value. In a hashtable the key is always a hash code.
This article will show the use of overriding the GetHashCode and Equals methods when working with the HashTable class.
GetHashCode
Every object in C# inherits from the Object class which holds four methods that every object will have, these methods are:
- • Equals
- • GetHashCode
- • GetType
- • ToString
The GetHashCode method returns an object instances (integer) hash code. That hashcode can be used as a key in the HashTable. This, however, makes it important to look at the implementation of the GetHashCode method. The base GetHashCode implementation returns a integer representation based upon the objects identity (where it’s located in memory).
The GetHashCode returns the same hash code for all instances that are the same.
If you have two String objects both containing the word “hello” they will return the same hash code since the String objects override of GetHashCode is based upon the integer value of the string.
This means that a custom Student object instance s1 does not return the same hash code as Student object s2 unless the GetHashCode method has been overridden to do so.
Consider the following class:
class Student {
//Student name, such as John, Jessica or Bill
public String Name { get; set; }
//Student id
public int Id { get; set; }
//Student school, such as Leet High, or Stanford
public String School { get; set; }
/// <summary>
/// The most basic identifiable elements of a student must
/// be set when creating a Student object
/// </summary>
/// <param name="name">The name of the student</param>
/// <param name="id">The id number of the student</param>
/// <param name="school">The name of the school where the school is currently enrolled</param>
public Student(String name, int id, String school) {
this.Name = name;
this.Id = id;
this.School = school;
}
}
If a Student object is created it must, due to constructor constraints, contain a name, an id number and a school. A hash code in this case should be based upon the id number as it is unique, and name is not. Overriding the GetHashCode method may be done like this:
public override int GetHashCode() {
return this.Id;
}
What we do is that we simply return the Id number since a student id must be unique. Returning the integer representation of the String property Name would not create a unique hash code since many people can have the same name.
Equals
The default implementation of the Equals method is also based on the same object identity principle as GetHashCode which means that when creating your custom class and overriding GetHashCode it might be considered odd not to override Equals.
Continuing with our Student class from above we might implement Equals as follows:
public override bool Equals(object obj) {
if (!(obj is Student))
return false;
Student p = obj as Student;
return p.Id == this.Id ;
}
We make sure that the Equals is applied the same way as GetHashCode is; based on the Student Id. This way we make sure that if p1.Equals(p2) == true then p1.GetHashCode() == p2.GetHashCode().
Why
If we don’t override the GetHashCode and Equals methods we will have a problem using the HashTable.
The HashTable will not accept the same key twice. This can be both useful and devastating depending on the implementation of the GetHashCode method.
If the implementation of a custom class has not been overridden then the hash code returned will be unique for every instance. This example will show why this might not be desirable.
using System;
namespace MorkaExample {
class Student {
//Student name, such as John, Jessica or Bill
public String Name { get; set; }
//Student id
public int Id { get; set; }
//Student school, such as Leet High, or Stanford
public String School { get; set; }
/// <summary>
/// The most basic identifiable elements of a student must
/// be set when creating a Student object
/// </summary>
/// <param name="name">The name of the student</param>
/// <param name="id">The id number of the student</param>
/// <param name="school">The name of the school where the school is currently enrolled</param>
public Student(String name, int id, String school) {
this.Name = name;
this.Id = id;
this.School = school;
}
public override bool Equals(object obj) {
if (!(obj is Student))
return false;
Student p = obj as Student;
return p.Id == this.Id ;
}
public override int GetHashCode() {
return this.Id;
}
}
}
class Program {
static void Main(string[] args) {
//Create people!
//Syntax: new Student(Name, Id)
Student s1 = new Student("John Jennings", 14, "Lund University");
Student s2 = new Student("John James", 159, "Princeton");
Student s3 = new Student("John Jennings", 14, "Harvard");
Hashtable studentHashTable = new Hashtable();
//Add the Student objects to the HashTable
//Syntax: hashtable.Add(key, value)
studentHashTable.Add(s1.GetHashCode(), s1);
studentHashTable.Add(s2.GetHashCode(), s2);
studentHashTable.Add(s3.GetHashCode(), s3); //ERROR: Item has already been added. Key in dictionary: '14' Key being added: '14'
}
}
Now. What we did here was creating three students that all had a name, id and the name of their school.
We have overridden the GetHashCode method to return the student id as hashcode since it will always be unique to the student. If we hadn’t done this, the hash code would have been based on the object instance, and all three objects are unique giving them different hash codes. Student s3 would then have been accepted as going to two schools at the same time.
That’s why it is important to consider overriding the GetHashCode method.
The HashTable
As mentioned earlier, the HashTable collection stores all elements with a key. The key is a hash code and the HashTable object can be visualized like this:
Whereas a normal array only has a Value, the HashTable has the HashCode as well giving it a unique identifier to use when extracting a value.
The extracting works just like a normal collection but instead of an index, a key is given:
Usually an index is given, but in a hashtable a key is given instead. The key is a hashcode. The hashtable does, however, implement the IEnumerable interface which makes it possible to use a foreach loop to run through it.
The following code will demonstrate how to use a hashtable with a custom class and extract the values either with a foreach loop or directly with a key:
using System;
namespace MorkaExample {
class Student {
//Student name, such as John, Jessica or Bill
public String Name { get; set; }
//Student id
public int Id { get; set; }
//Student school, such as Leet High, or Stanford
public String School { get; set; }
/// <summary>
/// The most basic identifiable elements of a student must
/// be set when creating a Student object
/// </summary>
/// <param name="name">The name of the student</param>
/// <param name="id">The id number of the student</param>
/// <param name="school">The name of the school where the school is currently enrolled</param>
public Student(String name, int id, String school) {
this.Name = name;
this.Id = id;
this.School = school;
}
public override bool Equals(object obj) {
if (!(obj is Student))
return false;
Student p = obj as Student;
return p.Id == this.Id ;
}
public override int GetHashCode() {
return this.Id;
}
}
}
using System;
using System.Collections;
namespace MorkaExample {
class Program {
static void Main(string[] args) {
//Create people!
//Syntax: new Person(Name, Id)
Student s1 = new Student("John Jennings", 14, "Lund University");
Student s2 = new Student("John James", 159, "Princeton");
Hashtable studentHashTable = new Hashtable();
//Add the Person objects to the HashTable
//Syntax: hashtable.Add(key, value)
studentHashTable.Add(s1.GetHashCode(), s1);
studentHashTable.Add(s2.GetHashCode(), s2);
//Output each object hash code
foreach (object o in studentHashTable) {
Console.WriteLine("Object hashcode: {0}", o.GetHashCode());
}
Console.WriteLine();
//Output each person
Student student1 = (Student)studentHashTable[s1.GetHashCode()];
Student student2 = (Student)studentHashTable[s2.GetHashCode()];
Console.WriteLine("{0, -15} {1, -15} {2, -15}", "Name", "Id", "School");
Console.WriteLine("{0, -15} {1, -15} {2, -15}", student1.Name, student1.Id, student1.School);
Console.WriteLine("{0, -15} {1, -15} {2, -15}", student2.Name, student2.Id, student2.School);
Console.Read();
}
}
}
Running this will yield the following result:
There are no comments on this article.
Leave a message!
If you have any question or just want to leave a message, just fill out the form below!
Your e-mail will not be visible in your post, it is for validation reasons only
Maffelu