해시테이블(HashTable)
키 값을 해시함수로 해싱하여 해시테이블의 특정 위치로 직접 엑세스하도록 만든 방식이다.
해시 : 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑
<해시테이블 구현>
데이터를 담을 테이블을 이미 크게 확보해 놓은 후
입력받은 키를 해싱하여 테이블 고유한 index를 계산하고 데이터를 담아 보관
해싱
┌────┐
27 ─→│ │─→ 27
385 ─→│해시│─→ 192
581 ─→│함수│─→ 2
1031 ─→│ │─→ 66
└────┘
[0] [1] [2] [27] [66] [191] [192] [193]
┌─────┬─────┬─────┬─ ─┬────┬─ ─┬──────┬─ ─┬─────┬─────┬─────┐
│ │ │ 582 │....│ 27 │...│ 1031 │....│ │ 385 │ │
└─────┴─────┴─────┴─ ─┴────┴─ ─┴──────┴─ ─┴─────┴─────┴─────┘
<해시함수>
키값을 해싱하여 고유한 index를 만드는 함수
하나의 키값을 해싱하는 경우 반드시 항상 같은 결과여야 함
효율 : 해시의 결과가 분산적일수록 효율이 좋음
나눗셈법 : 데이터 % 테이블크기
자리수접기 : 데이터의 각 자리수의 합
SHA-2 : 미국 국가안보국(NSA)이 설계한 암호화 해시 함수
나눗셈법 예시 : 132031 → (132031 % 1000) = 31
자리수접기 예시 : "hash" → h(104) + a(97) + s(115) + h(104) = 420
<해시테이블 주의점 - 충돌>
해시함수가 서로 다른 입력 값에 대해 동일한 해시테이블 주소를 반환하는 것
모든 입력 값에 대해 고유한 해시 값을 만드는 것은 불가능하며 충돌은 피할 수 없음
해싱
┌────┐
274 ─→│해시│─→ 81
660 ─→│함수│─→ 81
└────┘
[0] [1] [2] [81] [191] [192] [193]
┌─────┬─────┬─────┬─ ─┬─────────┬─ ─┬─────┬─────┬─────┐
│ │ │ │...│ 274 660 │...│ │ │ │
└─────┴─────┴─────┴─ ─┴─────────┴─ ─┴─────┴─────┴─────┘
<충돌해결방안 - 체이닝>
해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식
장점 : 해시테이블에 자료가 많아지더라도 성능저하가 적음
단점 : 해시테이블 외 추가적인 저장공간이 필요
해싱
┌────┐
274 ─→│해시│─→ 81
660 ─→│함수│─→ 81
└────┘
[0] [1] [2] [81] [191] [192] [193]
┌─────┬─────┬─────┬─ ─┬─────┬─ ─┬─────┬─────┬─────┐
│ │ │ │...│ │ │...│ │ │ │
└─────┴─────┴─────┴─ ─┴──│──┴─ ─┴─────┴─────┴─────┘
↓
┌─────┬─┐ ┌─────┬─┐
│ 274 │──→│ 660 │ │
└─────┴─┘ └─────┴─┘
<충돌해결방안 - 개방주소법> C#에서 사용
해시 충돌이 발생하면 다른 빈 공간에 데이터를 삽입하는 방식
해시 충돌시 선형탐색, 제곱탐색, 이중해시 등을 통해 다른 빈 공간을 선정
장점 : 추가적인 저장공간이 필요하지 않음, 삽입삭제시 오버헤드가 적음
단점 : 해시테이블에 자료가 많아질수록 성능저하가 많음
개방주소법 해시테이블의 공간 사용률이 높을 경우(통계적으로 70% 이상) 급격한 성능저하가 발생
이런 경우 재해싱을 통해 공간 사용률을 낮추어 다시 효율을 확보함
재해싱 : 해시테이블의 크기를 늘리고 테이블 내의 모든 데이터를 다시 해싱하여 보관
해싱
┌────┐
274 ─→│해시│─→ 81
660 ─→│함수│─→ 81
└────┘
[0] [1] [2] [81] [82] [191] [192] [193]
┌─────┬─────┬─────┬─ ─┬─────┬─────┬─ ─┬─────┬─────┬─────┐
│ │ │ │....│ 274 │ │....│ │ │ │
└─────┴─────┴─────┴─ ─┴─────┴─────┴─ ─┴─────┴─────┴─────┘
↑660(충돌)
[0] [1] [2] [81] [82] [191] [192] [193]
┌─────┬─────┬─────┬─ ─┬─────┬─────┬─ ─┬─────┬─────┬─────┐
│ │ │ │....│ 274 │ 660 │....│ │ │ │
└─────┴─────┴─────┴─ ─┴─────┴─────┴─ ─┴─────┴─────┴─────┘
↑(다음위치에 저장)
<해시테이블의 시간복잡도>
접근 탐색 삽입 삭제(*삭제된 위치 재사용불가)
X O(1) O(1) O(1)
충돌하는 특성으로 인해 삽입, 삭제에 불리하다.
static void Main(string[] args)
{
// 해시테이블 기반의 HashSet 자료구조
// 중복이 없는 해시기반의 저장소
//HashSet 0(1) 입력순서 출력// SortedSet(logN) 정렬 출력
//둘 다 값을 중복 없이 모아두는 저장소로 활용
HashSet<string> set = new HashSet<string>();
// 삽입
set.Add("D");
set.Add("B");
set.Add("B"); //중복추가 무시
set.Add("C");
set.Add("A");
set.Add("A");
set.Add("A");
set.Add("E");
// 삭제
set.Remove("B");
// 탐색
set.Contains("A"); // 포함 확인
// 순서대로 출력시 포함된 순서대로 결과 확인
foreach (string value in set)
{
Console.Write(value); // output : DCAE
}
Console.WriteLine();
// 해시테이블 기반의 Dictionary 자료구조
// 중복을 허용하지 않는 key를 기준으로 해시기반의 value 저장소
// Dictionary 0(1) 입력순서출력 // SortedDictionary(logN)정렬출력
Dictionary<int, string> dictionary = new Dictionary<int, string>();
// 삽입
dictionary.Add(2, "A");
dictionary.Add(1, "B");
dictionary.Add(4, "C");
dictionary.Add(3, "D");
dictionary.Add(5, "E");
// dictionary.Add(4, "F"); // error : Dictionary는 중복을 허용하지 않음
dictionary.TryAdd(4, "E"); // SortedDictionary와 같은 명령어들 사용가능
// 삭제
dictionary.Remove(5);
// 탐색
dictionary.ContainsKey(3); // 포함 확인
dictionary.TryGetValue(3, out string dicValue); // 탐색 시도
dictionary[4] = "F";
// 순서대로 출력시 정렬된 결과 확인
foreach (string value in dictionary.Values)
{
Console.Write(value); // output : ABCD
}
Console.WriteLine();
dictionary.TryGetValue(4,out string ivalue);
Console.WriteLine(ivalue); // output: F
}
<해시테이블(HashTable)기능 구현>
namespace DataStructure
{ //Dictionary 클래스 생성<key,value 자료형 일반화>
//key 값을 비교할 필요가 없기 때문에 IComparable이 아닌
//키 값이 같은지 다른지 비교하는 where TKey : IEquatable<TKey>
public class Dictionary<TKey, TValue> where TKey : IEquatable<TKey>
{
private const int DefaultCapacity = 1000; //기본 크기 설정(소수로 설정 시 효율 증가)
private struct Entry //구조체 Entry
{
public enum State { None, Using, Deleted } //Entry의 상태를 구별하는 열거형
public State state; //state값
public TKey key; //key값
public TValue value; //value값
}
private Entry[] table; //key와 value, state를 가진 테이블 배열 생성
private int usedCount; //사용중인 갯수
public Dictionary()
{
table = new Entry[DefaultCapacity]; //테이블 기본크기
usedCount = 0; //갯수 0
}
public TValue this[TKey key] //this 인덱서, dictionary[4] = "F"; 구현
{
get //가져오기
{
if (Find(key, out int index)) //키값 찾았을 때
{
return table[index].value; //값 확인
}
else //키값 못 찾았을 때
{
throw new KeyNotFoundException(); //예외처리
}
}
set //갱신하기
{
if (Find(key, out int index)) //키값 찾았을 때
{
table[index].value = value; //value값 인덱스 위치에 입력
}
else //키값 못 찾았을 때
{
Add(key, value); //비어있는 위치에 키,데이터 입력
//table[index].key = key;
//table[index].value = value;
table[index].state = Entry.State.Using; //인덱스위치를 사용중으로 상태변경
usedCount++; //갯수 증가
}
}
}
public void Add(TKey key, TValue value) //값 입력 함수 Add
{
if (Find(key, out int index)) //입력한 키값이 있다면
{
throw new InvalidOperationException("Already exist key"); //예외처리
}
else // 입력한 키값이 없다면
{
if (usedCount > table.Length * 0.7f) // 테이블의 70%이상 사용중이라면
{
ReHashing(); //테이블 크기 증가
}
table[index].key = key; //지금 key값 현재인덱스key값에 입력
table[index].value = value; // 지금 value값 현재인덱스 value값에 입력
table[index].state = Entry.State.Using; //값을 추가했으니 사용중으로 상태변경
usedCount++; //갯수 증가
}
}
public void Clear()
{
table = new Entry[DefaultCapacity];
usedCount = 0;
}
public bool ContainsKey(TKey key) //키값으로 데이터 확인하는 함수
{
if (Find(key, out int index)) //찾는 키값이 있을때
{
return true;
}
else //찾는 키값이 없을때
{
return false;
}
}
public bool Remove(TKey key) //키값을 찾아 삭제하는 함수 구현
{
if (Find(key, out int index)) //찾는 키값이 있다면
{
table[index].state = Entry.State.Deleted; //삭제된 것으로 상태변경
return true; //완료
}
else //찾는 키값이 없다면
{
return false; //실패
}
}
private bool Find(TKey key, out int index) //key값이 있는지 확인하는 bool함수
{
if (key == null) //key값이 없으면
throw new ArgumentNullException(); //예외처리
index = Hash(key); //key값을 해싱하여 index입력
for (int i = 0; i < table.Length; i++) //빈자리를 발견할 때까지 반복
{
if (table[index].state == Entry.State.None) //테이블 인덱스위치가 비어있는 경우
{
return false; //찾지 못했으니 false
}
else if (table[index].state == Entry.State.Using) //테이블 인덱스위치가 사용중인 경우
{
if (key.Equals(table[index].key)) //현재 키 값이 테이블에 있는 키 값과 같은지 확인
{
return true; //같으면 true
}
else // 같지 않다면
{
// 다음칸으로
index = Hash2(index);
}
}
else // if(table[index].state==Entry.state.Deleted) 테이블 인덱스 위치가 지워진 상태일 때
{
//다음칸으로
index = Hash2(index);
}
}
index = -1; //빈칸이 없을경우, 인덱스를 찾을 수 없다는 표현
throw new InvalidOperationException();
}
private int Hash(TKey key) //key값으로 해싱하는 함수
{
return Math.Abs(key.GetHashCode() % table.Length); //key값을 받아서 테이블크기로 나눠서 나머지, 절댓값으로 고정, 나눗셈법 구현
}
private int Hash2(int index) //충돌했을 떄 선형탐사하는 함수
{
// 선형 탐사
return (index + 1) % table.Length; //다음 인덱스에 나눗셈법하여 입력
// 제곱 탐사
// return (index + 1) * (index + 1) % table.Length;
// 이중 해싱
// return Math.Abs((index + 1).GetHashCode() % table.Length);
}
private void ReHashing() //데이터가 일정 부분 채워지면 크기 변경
{
Entry[] oldTable = table; //기존 테이블을 변수에 저장
table = new Entry[table.Length * 2]; //기존테이블의 2배 크기로 인스턴스 생성
usedCount = 0; //갯수 초기화
for (int i = 0; i < oldTable.Length; i++) //기존테이블을 전부 확인
{
Entry entry = oldTable[i]; //인덱스 위치를 순서대로 넣고
if (entry.state == Entry.State.Using) // 사용중인 위치가 있다면
{
Add(entry.key, entry.value); // 입력해준다.
}
}
}
}
}
기록하는 것이 기억된다.