자료구조 : 해시테이블 (Hash Table)
해시(Hash)는 키 값을 해시 함수(Hash function)으로 해싱하여 해시테이블의 특정 위치로 직접 엑세스하도록 만든 방식이다.
키 값을 통해 직접 엑세스하기 위해서 모든 가능한 키 값을 갖는 배열을 만들면, 배열크기가 엄청나게 커지게 된다. 예를 들어, 주민등록번호를 키 값으로 하는 경우, 000000-0000000 부터 999999-9999999까지 10의 13승의 배열 공간이 필요한데, 만약 회원수가 1000명인 경우, 1000명을 저장하기 위해 10^13의 엄청난 배열 공간이 필요하게 된다. 이렇게 낭비되는 공간을 줄이기 위해 해시 함수를 사용하게 되는데, 이 함수는 적은 공간 안에서 모든 키를 직접 찾아갈 수 있도록 해준다.
하지만 경우에 따라 서로 다른 키가 동일한 해시테이블 버켓 위치를 가리킬 수 있는데, 이를 해결하기 위해 여러 Collision Resolution 방식이 사용된다. Collision Resolution의 방식으로 Chaining을 비롯하여 Linear Probing, Quadratic Probing, Double Hashing 등 여러가지가 있다. 해시테이블 자료구조는 추가, 삭제, 검색에서 O(1)의 시간이 소요된다.
키 값을 통해 직접 엑세스하기 위해서 모든 가능한 키 값을 갖는 배열을 만들면, 배열크기가 엄청나게 커지게 된다. 예를 들어, 주민등록번호를 키 값으로 하는 경우, 000000-0000000 부터 999999-9999999까지 10의 13승의 배열 공간이 필요한데, 만약 회원수가 1000명인 경우, 1000명을 저장하기 위해 10^13의 엄청난 배열 공간이 필요하게 된다. 이렇게 낭비되는 공간을 줄이기 위해 해시 함수를 사용하게 되는데, 이 함수는 적은 공간 안에서 모든 키를 직접 찾아갈 수 있도록 해준다.
하지만 경우에 따라 서로 다른 키가 동일한 해시테이블 버켓 위치를 가리킬 수 있는데, 이를 해결하기 위해 여러 Collision Resolution 방식이 사용된다. Collision Resolution의 방식으로 Chaining을 비롯하여 Linear Probing, Quadratic Probing, Double Hashing 등 여러가지가 있다. 해시테이블 자료구조는 추가, 삭제, 검색에서 O(1)의 시간이 소요된다.
Hashtable 클래스
.NET에 해시테이블을 구현한 Non-generic 클래스로 Hashtable 클래스가 있다. Hashtable은 Key값과 Value값 모두 object 타입을 받아들이며, 박싱/언박싱을 하게 된다. Hashtable은 Double Hashing 방식을 사용하여 Collision Resolution을 하게 된다. 즉, 해시함수를 사용하여 Key가 충돌(Collision)이 발생하면, 다른 해시함수를 계속 사용하여 빈 버켓을 찾게된다. 이 자료구조는 추가, 삭제, 검색에서 O(1)의 시간이 소요된다.
예제
Hashtable ht = new Hashtable();
ht.Add("irina", "Irina SP");
ht.Add("tom", "Tom Cr");
if (ht.Contains("tom"))
{
Console.WriteLine(ht["tom"]);
}
ht.Add("irina", "Irina SP");
ht.Add("tom", "Tom Cr");
if (ht.Contains("tom"))
{
Console.WriteLine(ht["tom"]);
}
Dictionary<Tkey,TValue> 클래스
.NET에 Generic방식으로 해시테이블을 구현한 클래스로 Dictionary<Tkey,TValue> 클래스가 있다. Dictionary는 Key값과 Value값 모두 Strong type을 받아들이며, 박싱/언박싱을 일으키지 않는다. Dictionary는 Chaining 방식을 사용하여 Collision Resolution을 하게 된다. 이 자료구조는 추가, 삭제, 검색에서 O(1)의 시간이 소요된다.
예제
Dictionary<int, string> emp = new Dictionary<int, string>();
emp.Add(1001, "Jane");
emp.Add(1002, "Tom");
emp.Add(1003, "Cindy");
string name = emp[1002];
Console.WriteLine(name);
emp.Add(1001, "Jane");
emp.Add(1002, "Tom");
emp.Add(1003, "Cindy");
string name = emp[1002];
Console.WriteLine(name);
ConcurrentDictionary<Tkey,TValue> 클래스
.NET 4.0 부터 멀티쓰레딩 환경에서 Dictionary를 보다 간편하게 사용할 수 있는 새로운 클래스인 ConcurrentDictionary<Tkey,TValue> 가 제공되었다. ConcurrentDictionary 클래스에서는 기본적으로 데이타를 추가하기 위해 TryAdd() 메서드를 사용하고, 키값을 읽기 위해서는 TryGetValue() 메서드를 사용한다. 또한 기존 키값을 갱신하기 위해서 TryUpdate() 메서드를, 기존 키를 지우기 위해서는 TryRemove() 메서드를 사용한다.
아래 예제는 하나의 쓰레드가 ConcurrentDictionary 에 Key를 1부터 100까지 계속 집어 넣을 때, 동시에 다른 쓰레드에서는 계속 그 해시테이블에서 Key가 1부터 100까지인 데이타를 빼내 (순차적으로) 읽어 오는 작업을 하는 샘플 코드이다.
아래 예제는 하나의 쓰레드가 ConcurrentDictionary 에 Key를 1부터 100까지 계속 집어 넣을 때, 동시에 다른 쓰레드에서는 계속 그 해시테이블에서 Key가 1부터 100까지인 데이타를 빼내 (순차적으로) 읽어 오는 작업을 하는 샘플 코드이다.
예제
using System;
using System.Collections;
using System.Collections.Concurrent; // ConcurrentDictionary
using System.Threading;
using System.Threading.Tasks;
namespace ConcurrentApp
{
class Program
{
static void Main(string[] args)
{
var dict = new ConcurrentDictionary<int, string>();
Task t1 = Task.Factory.StartNew(() =>
{
int key = 1;
while (key <= 100)
{
if (dict.TryAdd(key, "D" + key))
{
key++;
}
Thread.Sleep(100);
}
});
Task t2 = Task.Factory.StartNew(() =>
{
int key = 1;
string val;
while (key <= 100)
{
if (dict.TryGetValue(key, out val))
{
Console.WriteLine("{0},{1}", key, val);
key++;
}
Thread.Sleep(100);
}
});
Task.WaitAll(t1, t2);
}
}
}
using System.Collections;
using System.Collections.Concurrent; // ConcurrentDictionary
using System.Threading;
using System.Threading.Tasks;
namespace ConcurrentApp
{
class Program
{
static void Main(string[] args)
{
var dict = new ConcurrentDictionary<int, string>();
Task t1 = Task.Factory.StartNew(() =>
{
int key = 1;
while (key <= 100)
{
if (dict.TryAdd(key, "D" + key))
{
key++;
}
Thread.Sleep(100);
}
});
Task t2 = Task.Factory.StartNew(() =>
{
int key = 1;
string val;
while (key <= 100)
{
if (dict.TryGetValue(key, out val))
{
Console.WriteLine("{0},{1}", key, val);
key++;
}
Thread.Sleep(100);
}
});
Task.WaitAll(t1, t2);
}
}
}
C#으로 간단한 해시테이블 구현
해시테이블은 기본적으로 배열을 저장 장소로 사용한다. 아래의 간단한 해시테이블 구현에서도 buckets라는 배열을 기본 데이타 멤버로 사용하고 있다. 해시함수를 사용하여 정해진 배열내에서 특정 배열요소 위치를 계산하게 되며, 만약 키 중복이 발생하는 경우 Chaining방식을 사용하여 링크드 리스트로 연결하여 저장하게 된다. 이 예제는 기본 개념을 예시하기 위한 것으로 많은 기능들이 생략되어 있다.
예제
namespace MyHash
{
public class SimpleHashTable
{
private const int INITIAL_SIZE = 16;
private int size;
private Node[] buckets;
public SimpleHashTable()
{
this.size = INITIAL_SIZE;
this.buckets = new Node[size];
}
public SimpleHashTable(int capacity)
{
this.size = capacity;
this.buckets = new Node[size];
}
public void Put(object key, object value)
{
int index = HashFunction(key);
if (buckets[index] == null)
{
buckets[index] = new Node(key, value);
}
else
{
Node newNode = new Node(key, value);
newNode.Next = buckets[index];
buckets[index] = newNode;
}
}
public object Get(object key)
{
int index = HashFunction(key);
if (buckets[index] != null)
{
for (Node n = buckets[index]; n != null; n = n.Next)
{
if (n.Key == key)
{
return n.Value;
}
}
}
return null;
}
public bool Contains(object key)
{
int index = HashFunction(key);
if (buckets[index] != null)
{
for (Node n = buckets[index]; n != null; n = n.Next)
{
if (n.Key == key)
{
return true;
}
}
}
return false;
}
protected virtual int HashFunction(object key)
{
return Math.Abs(key.GetHashCode() + 1 +
(((key.GetHashCode() >> 5) + 1) % (size))) % size;
}
private class Node
{
public object Key { get; set; }
public object Value { get; set; }
public Node Next { get; set; }
public Node(object key, object value)
{
this.Key = key;
this.Value = value;
this.Next = null;
}
}
}
class Program
{
static void Main(string[] args)
{
// Chaining 테스트를 위해
// capacity를 1로 셋팅할 수 있음
//SimpleHashTable ht = new SimpleHashTable(1);
SimpleHashTable ht = new SimpleHashTable();
ht.Put("Kim D", "Sales 01");
ht.Put("Lee K", "Sales 02");
ht.Put("Park S", "IT 03");
ht.Put("Shin O", "IT 04");
Console.WriteLine(ht.Get("Lee K"));
Console.WriteLine(ht.Get("Shin O"));
Console.WriteLine(ht.Contains("Unknown"));
}
}
}
{
public class SimpleHashTable
{
private const int INITIAL_SIZE = 16;
private int size;
private Node[] buckets;
public SimpleHashTable()
{
this.size = INITIAL_SIZE;
this.buckets = new Node[size];
}
public SimpleHashTable(int capacity)
{
this.size = capacity;
this.buckets = new Node[size];
}
public void Put(object key, object value)
{
int index = HashFunction(key);
if (buckets[index] == null)
{
buckets[index] = new Node(key, value);
}
else
{
Node newNode = new Node(key, value);
newNode.Next = buckets[index];
buckets[index] = newNode;
}
}
public object Get(object key)
{
int index = HashFunction(key);
if (buckets[index] != null)
{
for (Node n = buckets[index]; n != null; n = n.Next)
{
if (n.Key == key)
{
return n.Value;
}
}
}
return null;
}
public bool Contains(object key)
{
int index = HashFunction(key);
if (buckets[index] != null)
{
for (Node n = buckets[index]; n != null; n = n.Next)
{
if (n.Key == key)
{
return true;
}
}
}
return false;
}
protected virtual int HashFunction(object key)
{
return Math.Abs(key.GetHashCode() + 1 +
(((key.GetHashCode() >> 5) + 1) % (size))) % size;
}
private class Node
{
public object Key { get; set; }
public object Value { get; set; }
public Node Next { get; set; }
public Node(object key, object value)
{
this.Key = key;
this.Value = value;
this.Next = null;
}
}
}
class Program
{
static void Main(string[] args)
{
// Chaining 테스트를 위해
// capacity를 1로 셋팅할 수 있음
//SimpleHashTable ht = new SimpleHashTable(1);
SimpleHashTable ht = new SimpleHashTable();
ht.Put("Kim D", "Sales 01");
ht.Put("Lee K", "Sales 02");
ht.Put("Park S", "IT 03");
ht.Put("Shin O", "IT 04");
Console.WriteLine(ht.Get("Lee K"));
Console.WriteLine(ht.Get("Shin O"));
Console.WriteLine(ht.Contains("Unknown"));
}
}
}